DBScholar

Back to papers

Finding and Approximating Top-k Answers in Keyword Proximity Search

Summary: Under data complexity, an efficient top-1 algorithm for keyword-proximity Q-fragments yields polynomial-delay algorithms for ranked enumeration and top-k computation. With query-and-data complexity, a θ-approximate top-1 yields (θ+1)-approximate ranked enumeration and top-k, giving the first provable approximate enumeration/top-k algorithms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
ha3fe2fad87a54b90
Venue
PODS
Year
2006
Pagerank
0.0001063035
Overall Rank
1,445 | 90.29%
DOI
10.1145/1142351.1142377

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kimelfeld_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Finding and Approximating Top-k Answers in Keyword Proximity Search}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142377},
        doi = {10.1145/1142351.1142377},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kimelfeld, Benny and Sagiv, Yehoshua},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank Citing Paper Year Venue Pagerank
270 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022599109
942 SPARK: Top-k Keyword Query in Relational Databases 2007 SIGMOD 0.00012956137
1,476 Diversifying Top-K Results 2012 VLDB 0.00010551487
1,501 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00010461358
1,565 Keyword Proximity Search in Complex Data Graphs 2008 SIGMOD 0.00010220855
1,616 Efficient Enumeration of Maximal k-Plexes 2015 SIGMOD 0.00010066712
2,414 Structured Search Result Differentiation 2009 VLDB 8.5081277e-05
2,888 DB&IR: Both Sides Now (Extended Abstract) 2007 SIGMOD 7.9072366e-05
3,003 Gestural Query Specification 2014 VLDB 7.7645915e-05
3,088 Learning to Create Data-Integrating Queries 2008 VLDB 7.6596008e-05
3,312 Keyword Search on Structured and Semi-Structured Data 2009 SIGMOD 7.4385614e-05
3,656 Best Position Algorithms for Top-k Queries 2007 VLDB 7.1256193e-05
4,806 Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers 2014 VLDB 6.4082256e-05
5,531 Efficient and Progressive Group Steiner Tree Search 2016 SIGMOD 6.0935114e-05
5,845 Effective Keyword-based Selection of Relational Databases 2007 SIGMOD 5.9729417e-05
7,323 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.5524474e-05
7,668 The Complexity of Mining Maximal Frequent Subgraphs 2013 PODS 5.4772833e-05
8,154 Optimizing and Parallelizing Ranked Enumeration 2011 VLDB 5.3889102e-05
8,494 Understanding Queries in a Search Database System 2010 PODS 5.3309392e-05
9,829 Finding a Minimal Tree Pattern Under Neighborhood Constraints 2011 PODS 5.1249899e-05
11,732 Efficient Approximation Framework for Attribute Recommendation 2023 SIGMOD 4.9793485e-05
11,830 Linear-Delay Enumeration for Minimal Steiner Problems 2022 PODS 4.9793485e-05
12,699 Transducing Markov Sequences 2010 PODS 4.9793485e-05
12,725 Exploratory Keyword Search on Data Graphs 2010 SIGMOD 4.9793485e-05
12,752 Ten Thousand SQLs: Parallel Keyword Queries Computing 2010 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010679641
38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00047394041
293 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021943678
1,953 DBXplorer: Enabling Keyword Search over Relational Databases 2002 SIGMOD 9.3183947e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,812 Efficient Algorithms for Answering the m-Closest Keywords Query 2015 SIGMOD
2 2,731 Keyword Search in Graphs: Finding r-cliques 2011 VLDB
3 8,058 Optimizing Index for Taxonomy Keyword Search 2012 SIGMOD
4 12,599 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
5 7,323 Nearest Keyword Search in XML Documents 2011 SIGMOD
6 7,934 A System for Keyword Proximity Search on XML Databases 2003 VLDB
7 7,075 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD
8 8,662 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB
9 303 Proximity Search in Databases 1998 VLDB
10 1,565 Keyword Proximity Search in Complex Data Graphs 2008 SIGMOD