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: 10704
Venue: VLDB
Year: 2013
Pagerank: 4.8151659e-05
Overall Rank: 7,142 | 50.37%
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,152	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	5.6550754e-05
6,730	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9436522e-05
9,566	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB	4.3212967e-05
9,933	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	4.245954e-05
11,241	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.1905499e-05
11,661	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	4.1905499e-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.00044946098
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
2,077	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6038296e-05
2,235	Effective Phrase Prediction	2007	VLDB	9.2208486e-05
2,588	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4872437e-05
2,665	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.3505169e-05
3,583	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	6.944299e-05
3,779	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7709545e-05
5,806	SOCQET: Semantic OLAP with Compressed Cube and Summarization	2003	SIGMOD	5.3193543e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,933	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	4.245954e-05
9,934	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	4.245954e-05
7,707	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6676985e-05
4,215	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3464157e-05
7,775	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	4.6494306e-05
3,779	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7709545e-05
5,624	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4049016e-05
11,661	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	4.1905499e-05
2,077	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6038296e-05
9,566	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB	4.3212967e-05