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: 10891
Venue: VLDB
Year: 2013
Pagerank: 5.72252e-05
Overall Rank: 7,031 | 51.77%
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,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.3673276e-05
6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.8665833e-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
11,439	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	5.093636e-05
11,851	Autocompletion for Prefix-Abbreviated Input	2019	SIGMOD	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
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
1,701	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.9707165e-05
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
2,176	Effective Phrase Prediction	2007	VLDB	9.0172465e-05
2,318	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.7588859e-05
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
3,446	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.4087786e-05
5,836	SOCQET: Semantic OLAP with Compressed Cube and Summarization	2003	SIGMOD	6.0719042e-05

Semantically Similar Papers

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