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.7448851e-05
Overall Rank
1,739 | 88.32%
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,074 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 9.0821759e-05
3,256 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4855571e-05
3,605 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 7.1667859e-05
3,817 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 7.0039415e-05
4,141 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.7822757e-05
5,210 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 6.2243094e-05
5,797 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9898117e-05
6,608 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.73402e-05
6,983 DBease: Making Databases User-friendly and Easily Accessible 2011 CIDR 5.6261545e-05
7,175 Efficient Error-tolerant Query Autocompletion 2013 VLDB 5.5915423e-05
7,846 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.4400167e-05
9,886 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 5.115241e-05
10,303 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.0394806e-05
10,304 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.0394806e-05
10,701 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.9769913e-05
12,157 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD 4.9769913e-05
12,483 MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data 2014 VLDB 4.9769913e-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.0010679903
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.0005758001
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033040246
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027151132
262 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00022811258
319 Making Database Systems Usable 2007 SIGMOD 0.00021155013
929 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013014029
1,311 Assisted Querying using Instant-Response Interfaces 2007 SIGMOD 0.00011061025
2,215 Effective Phrase Prediction 2007 VLDB 8.8154455e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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