Efficient Error-tolerant Query Autocompletion

Summary: Proposes IncNGTrie, a neighborhood-generation–based autocompletion algorithm for edit-distance tolerance. Keeps few active nodes, supports quick duplicate removal, and reduces index size; experiments show up to 100× speedup vs. prior methods on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10703
Venue: VLDB
Year: 2013
Pagerank: 4.8197901e-05
Overall Rank: 7,141 | 50.33%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,151	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	5.6609851e-05
6,726	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9484027e-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
11,239	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.1945683e-05
11,656	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	4.1945683e-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
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
2,073	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6142791e-05
2,232	Effective Phrase Prediction	2007	VLDB	9.2293508e-05
2,592	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4795761e-05
2,662	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.3532302e-05
3,578	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	6.9503858e-05
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
5,795	SOCQET: Semantic OLAP with Compressed Cube and Summarization	2003	SIGMOD	5.3244898e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
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
7,708	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6721808e-05
4,216	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3521675e-05
7,777	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	4.653704e-05
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
5,615	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4101086e-05
11,656	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	4.1945683e-05
2,073	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6142791e-05
9,567	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB	4.3254416e-05