Database Paper Browser

Back to papers

Extending Autocompletion To Tolerate Errors

Summary: Extends autocompletion to tolerate typing errors by modeling input with edit distance and error-aware prefix matching. Shows naïve per-step offline edit-distance search is costly; proposes more efficient algorithms and validates them empirically. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4159
Venue
SIGMOD
Year
2009
Pagerank
9.6038296e-05
Overall Rank
2,077 | 85.57%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
2,387 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 8.9075095e-05
3,561 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 6.9693906e-05
3,779 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7709545e-05
4,215 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.3464157e-05
4,410 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.2012075e-05
5,152 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 5.6550754e-05
5,892 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2829767e-05
6,730 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 4.9436522e-05
6,854 DBease: Making Databases User-friendly and Easily Accessible 2011 CIDR 4.901546e-05
7,142 Efficient Error-tolerant Query Autocompletion 2013 VLDB 4.8151659e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05
9,566 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 4.3212967e-05
9,933 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 4.245954e-05
9,934 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.245954e-05
10,216 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.1905499e-05
11,661 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD 4.1905499e-05
11,996 MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data 2014 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
8 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015436578
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
257 Making Database Systems Usable 2007 SIGMOD 0.00030237174
264 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029950264
321 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00027524716
994 Assisted Querying using Instant-Response Interfaces 2007 SIGMOD 0.00014745808
1,232 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013133604
2,235 Effective Phrase Prediction 2007 VLDB 9.2208486e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,544 On Indexing Error-Tolerant Set Containment 2010 SIGMOD 5.4481372e-05
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
2,507 Auto-Detect: Data-Driven Error Detection in Tables 2018 SIGMOD 8.6254741e-05
7,775 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.6494306e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05
3,229 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.3390133e-05
2,235 Effective Phrase Prediction 2007 VLDB 9.2208486e-05
11,661 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD 4.1905499e-05
7,142 Efficient Error-tolerant Query Autocompletion 2013 VLDB 4.8151659e-05
9,566 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 4.3212967e-05