Database Paper Browser

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
1389
Venue
PODS
Year
2006
Pagerank
0.00014264992
Overall Rank
1,073 | 92.54%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank Citing Paper Year Venue Pagerank
301 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00028370644
1,201 SPARK: Top-k Keyword Query in Relational Databases 2007 SIGMOD 0.0001334371
1,445 Diversifying Top-K Results 2012 VLDB 0.00011945231
1,453 Keyword Proximity Search in Complex Data Graphs 2008 SIGMOD 0.00011917976
1,564 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00011350495
1,650 Efficient Enumeration of Maximal k-Plexes 2015 SIGMOD 0.00011013428
1,667 Structured Search Result Differentiation 2009 VLDB 0.00010960247
2,012 DB&IR: Both Sides Now (Extended Abstract) 2007 SIGMOD 9.7951657e-05
3,110 Learning to Create Data-Integrating Queries 2008 VLDB 7.5475982e-05
3,188 Gestural Query Specification 2014 VLDB 7.4117439e-05
3,450 Keyword Search on Structured and Semi-Structured Data 2009 SIGMOD 7.0824082e-05
4,186 Best Position Algorithms for Top-k Queries 2007 VLDB 6.3764858e-05
4,838 Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers 2014 VLDB 5.8887949e-05
5,043 The Complexity of Mining Maximal Frequent Subgraphs 2013 PODS 5.7411631e-05
5,323 Optimizing and Parallelizing Ranked Enumeration 2011 VLDB 5.5693009e-05
5,672 Effective Keyword-based Selection of Relational Databases 2007 SIGMOD 5.3784128e-05
5,683 Efficient and Progressive Group Steiner Tree Search 2016 SIGMOD 5.3723969e-05
7,315 Nearest Keyword Search in XML Documents 2011 SIGMOD 4.7645064e-05
8,029 Understanding Queries in a Search Database System 2010 PODS 4.6028544e-05
9,441 Finding a Minimal Tree Pattern Under Neighborhood Constraints 2011 PODS 4.3415167e-05
11,217 Efficient Approximation Framework for Attribute Recommendation 2023 SIGMOD 4.1945683e-05
11,322 Linear-Delay Enumeration for Minimal Steiner Problems 2022 PODS 4.1945683e-05
12,213 Transducing Markov Sequences 2010 PODS 4.1945683e-05
12,239 Exploratory Keyword Search on Data Graphs 2010 SIGMOD 4.1945683e-05
12,266 Ten Thousand SQLs: Parallel Keyword Queries Computing 2010 VLDB 4.1945683e-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
7 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015496097
54 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00066047203
336 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00027020919
1,679 DBXplorer: Enabling Keyword Search over Relational Databases 2002 SIGMOD 0.00010932603
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,925 Efficient Algorithms for Answering the m-Closest Keywords Query 2015 SIGMOD 5.8226582e-05
2,770 Keyword Search in Graphs: Finding r-cliques 2011 VLDB 8.1437191e-05
7,475 Optimizing Index for Taxonomy Keyword Search 2012 SIGMOD 4.7191809e-05
12,111 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD 4.1945683e-05
7,315 Nearest Keyword Search in XML Documents 2011 SIGMOD 4.7645064e-05
7,609 A System for Keyword Proximity Search on XML Databases 2003 VLDB 4.6966255e-05
7,277 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 4.7794907e-05
8,505 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB 4.4958064e-05
186 Proximity Search in Databases 1998 VLDB 0.00036215179
1,453 Keyword Proximity Search in Complex Data Graphs 2008 SIGMOD 0.00011917976