META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion

Summary: Meta proposes a matching-based framework for error-tolerant autocompletion, replacing trie-centric active-node computation with character-level matching. It introduces a compact tree index to maintain active nodes, an incremental top-k algorithm, and achieves 1–2 orders of magnitude speedups over state-of-the-art on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11558
Venue: VLDB
Year: 2016
Pagerank: 5.2351259e-05
Overall Rank: 9,705 | 33.42%
DOI: 10.14778/2977797.2977808

Incoming Non-self Citations Over Time

Authors

1. Dong Deng (Tsinghua University)
2. Guoliang Li (Tsinghua University)
3. He Wen (Tsinghua University)
4. H. V. Jagadish (University of Michigan)
5. Jianhua Feng (Tsinghua University)

BibTeX Citation

@article{deng_vldb16,
        title = {{META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion}},
        author = {Deng, Dong and Li, Guoliang and Wen, He and Jagadish, H. V. and Feng, Jianhua},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {10},
        pages = {828--839},
        doi = {10.14778/2977797.2977808},
        url = {https://doi.org/10.14778/2977797.2977808},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,493	Human-in-the-loop Data Integration	2017	VLDB	5.6046905e-05
10,024	Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation	2023	SIGMOD	5.1757914e-05
11,439	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
158	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00028199923
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
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,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
6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.8665833e-05
7,031	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.72252e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
2	3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
3	12,558	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD
4	4,359	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
5	4,703	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB
6	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	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	7,031	Efficient Error-tolerant Query Autocompletion	2013	VLDB