DBScholar

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
h26fbbcaa70e01b11
Venue
SIGMOD
Year
2009
Pagerank
9.7128647e-05
Overall Rank
1,751 | 88.27%
DOI
10.1145/1559845.1559919

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{chaudhuri_sigmod09,
        title = {{Extending Autocompletion To Tolerate Errors}},
        author = {Chaudhuri, Surajit and Kaushik, Raghav},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559919},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559919},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
2,084 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 9.0533042e-05
3,270 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4613275e-05
3,613 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 7.1431207e-05
3,822 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.9814064e-05
4,156 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.7602028e-05
5,233 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 6.2049921e-05
5,811 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9701598e-05
6,617 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.7150599e-05
7,004 DBease: Making Databases User-friendly and Easily Accessible 2011 CIDR 5.6075521e-05
7,197 Efficient Error-tolerant Query Autocompletion 2013 VLDB 5.5730532e-05
7,863 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.4220286e-05
9,919 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 5.0983269e-05
10,331 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.0228171e-05
10,332 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.0228171e-05
10,762 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.9605343e-05
12,200 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD 4.9605343e-05
12,526 MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data 2014 VLDB 4.9605343e-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
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010688884
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00057610161
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00032945275
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027077763
264 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.0002276412
321 Making Database Systems Usable 2007 SIGMOD 0.00021093212
934 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00012973416
1,312 Assisted Querying using Instant-Response Interfaces 2007 SIGMOD 0.00011061014
2,232 Effective Phrase Prediction 2007 VLDB 8.7867154e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,348 On Indexing Error-Tolerant Set Containment 2010 SIGMOD
2 108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB
3 2,960 Auto-Detect: Data-Driven Error Detection in Tables 2018 SIGMOD
4 8,267 Indexing Mixed Types for Approximate Retrieval 2005 VLDB
5 7,863 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD
6 2,981 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB
7 2,232 Effective Phrase Prediction 2007 VLDB
8 12,200 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD
9 7,197 Efficient Error-tolerant Query Autocompletion 2013 VLDB
10 9,919 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB