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: 4220
Venue: SIGMOD
Year: 2009
Pagerank: 9.9707165e-05
Overall Rank: 1,701 | 88.34%
DOI: 10.1145/1559845.1559919

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)
2. Raghav Kaushik (Microsoft)

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,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.2782094e-05
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
3,534	Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency	2011	SIGMOD	7.3347488e-05
3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.1663952e-05
4,048	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD	6.9372074e-05
5,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.3673276e-05
5,667	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	6.1279762e-05
6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.8665833e-05
6,862	DBease: Making Databases User-friendly and Easily Accessible	2011	CIDR	5.7514733e-05
7,031	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.72252e-05
7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	5.5664611e-05
9,705	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB	5.2351259e-05
10,085	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.1559617e-05
10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	5.1559617e-05
10,505	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	5.093636e-05
11,851	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	5.093636e-05
12,186	MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data	2014	VLDB	5.093636e-05

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.0010828372
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
254	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00023199211
314	Making Database Systems Usable	2007	SIGMOD	0.00021574636
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
1,305	Assisted Querying using Instant-Response Interfaces	2007	SIGMOD	0.00011235196
2,176	Effective Phrase Prediction	2007	VLDB	9.0172465e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,306	On Indexing Error-Tolerant Set Containment	2010	SIGMOD
2	107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB
3	3,147	Auto-Detect: Data-Driven Error Detection in Tables	2018	SIGMOD
4	8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
5	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
6	2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB
7	2,176	Effective Phrase Prediction	2007	VLDB
8	11,851	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD
9	7,031	Efficient Error-tolerant Query Autocompletion	2013	VLDB
10	9,705	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB