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: 11370
Venue: VLDB
Year: 2016
Pagerank: 4.3254416e-05
Overall Rank: 9,567 | 33.45%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,668	Human-in-the-loop Data Integration	2017	VLDB	4.6834075e-05
9,876	Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation	2023	SIGMOD	4.2667743e-05
11,239	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.1945683e-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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
155	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00040637896
1,234	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013122499
2,073	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6142791e-05
2,376	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9424361e-05
2,592	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4795761e-05
3,570	Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency	2011	SIGMOD	6.958427e-05
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
4,216	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3521675e-05
4,414	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD	6.2056993e-05
6,726	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9484027e-05
7,141	Efficient Error-tolerant Query Autocompletion	2013	VLDB	4.8197901e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,933	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	4.2500258e-05
4,216	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3521675e-05
12,365	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD	4.1945683e-05
4,988	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	5.783959e-05
4,838	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	5.8887949e-05
7,708	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6721808e-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
7,141	Efficient Error-tolerant Query Autocompletion	2013	VLDB	4.8197901e-05