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
4158
Venue
SIGMOD
Year
2009
Pagerank
9.6142791e-05
Overall Rank
2,073 | 85.59%
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,376 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 8.9424361e-05
3,570 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 6.958427e-05
3,774 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7757301e-05
4,216 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.3521675e-05
4,414 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.2056993e-05
5,151 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 5.6609851e-05
5,887 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2879769e-05
6,726 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 4.9484027e-05
6,855 DBease: Making Databases User-friendly and Easily Accessible 2011 CIDR 4.9062505e-05
7,141 Efficient Error-tolerant Query Autocompletion 2013 VLDB 4.8197901e-05
7,708 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6721808e-05
9,567 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 4.3254416e-05
9,932 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 4.2500258e-05
9,933 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.2500258e-05
10,216 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.1945683e-05
11,656 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD 4.1945683e-05
11,988 MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data 2014 VLDB 4.1945683e-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
7 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015496097
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044847972
257 Making Database Systems Usable 2007 SIGMOD 0.00030223397
266 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029718727
322 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00027518768
994 Assisted Querying using Instant-Response Interfaces 2007 SIGMOD 0.00014755845
1,234 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013122499
2,232 Effective Phrase Prediction 2007 VLDB 9.2293508e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,536 On Indexing Error-Tolerant Set Containment 2010 SIGMOD 5.4532734e-05
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044847972
2,506 Auto-Detect: Data-Driven Error Detection in Tables 2018 SIGMOD 8.6335464e-05
7,777 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.653704e-05
7,708 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6721808e-05
3,226 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.3433307e-05
2,232 Effective Phrase Prediction 2007 VLDB 9.2293508e-05
11,656 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD 4.1945683e-05
7,141 Efficient Error-tolerant Query Autocompletion 2013 VLDB 4.8197901e-05
9,567 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 4.3254416e-05