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: hd1dcfc1ef5d511b8
Venue: VLDB
Year: 2013
Pagerank: 5.5941906e-05
Overall Rank: 7,172 | 51.79%
DOI: 10.14778/2536336.2536337

Incoming Non-self Citations Over Time

Authors

1. Chuan Xiao (Nagoya University)
2. Jianbin Qin (University of New South Wales)
3. Wei Wang (University of New South Wales)
4. Yoshiharu Ishikawa (Nagoya University)
5. Koji Tsuda (Japan Science and Technology Agency; National Institute of Advanced Industrial Science and Technology)
6. Kunihiko Sadakane (National Institute of Informatics)

BibTeX Citation

@article{xiao_vldb13,
        title = {{Efficient Error-tolerant Query Autocompletion}},
        author = {Xiao, Chuan and Qin, Jianbin and Wang, Wei and Ishikawa, Yoshiharu and Tsuda, Koji and Sadakane, Kunihiko},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {6},
        pages = {373--384},
        doi = {10.14778/2536336.2536337},
        url = {https://doi.org/10.14778/2536336.2536337},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,207	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.2272365e-05
6,605	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.7367357e-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
11,752	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.9793485e-05
12,151	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	4.9793485e-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
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027254612
1,737	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.7494976e-05
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
2,214	Effective Phrase Prediction	2007	VLDB	8.8195986e-05
2,256	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.7438759e-05
3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4890984e-05
3,512	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.2439455e-05
5,947	SOCQET: Semantic OLAP with Compressed Cube and Summarization	2003	SIGMOD	5.9373787e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD
2	10,299	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
3	7,842	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
4	3,816	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
5	8,245	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
6	3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
7	6,973	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
8	12,151	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD
9	1,737	Extending Autocompletion To Tolerate Errors	2009	SIGMOD
10	9,879	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB