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.7494976e-05
Overall Rank
1,737 | 88.33%
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,072 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 9.0864612e-05
3,255 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4890984e-05
3,605 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 7.1701802e-05
3,816 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 7.0072547e-05
4,140 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.7854783e-05
5,207 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 6.2272365e-05
5,795 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9926463e-05
6,605 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.7367357e-05
6,980 DBease: Making Databases User-friendly and Easily Accessible 2011 CIDR 5.6288191e-05
7,172 Efficient Error-tolerant Query Autocompletion 2013 VLDB 5.5941906e-05
7,842 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.4425932e-05
9,879 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB 5.1176637e-05
10,298 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.0418674e-05
10,299 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.0418674e-05
10,691 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.9793485e-05
12,151 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD 4.9793485e-05
12,477 MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data 2014 VLDB 4.9793485e-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.0010679641
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00057568153
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.0003305531
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027163517
262 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00022821392
319 Making Database Systems Usable 2007 SIGMOD 0.00021164857
929 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013020115
1,311 Assisted Querying using Instant-Response Interfaces 2007 SIGMOD 0.00011065979
2,214 Effective Phrase Prediction 2007 VLDB 8.8195986e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,333 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,245 Indexing Mixed Types for Approximate Retrieval 2005 VLDB
5 7,842 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD
6 2,967 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB
7 2,214 Effective Phrase Prediction 2007 VLDB
8 12,151 Autocompletion for Prefix-Abbreviated Input 2019 SIGMOD
9 7,172 Efficient Error-tolerant Query Autocompletion 2013 VLDB
10 9,879 META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion 2016 VLDB