Efficient and Effective KNN Sequence Search with Approximate n-grams

Summary: Proposes KNN sequence search under edit distance using longer approximate n-grams for pruning with a two-level index. CA-based filtering with a frequency queue reduces false positives, enabling progressive results and early termination; parallel execution scales. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10949
Venue: VLDB
Year: 2014
Pagerank: 5.1559617e-05
Overall Rank: 10,086 | 30.81%
DOI: 10.14778/2732232.2732236

Incoming Non-self Citations Over Time

Authors

1. Xiaoli Wang (National University of Singapore)
2. Xiaofeng Ding (Huazhong University of Science and Technology; University of South Australia)
3. Anthony K.H. Tung (National University of Singapore)
4. Zhenjie Zhang (Advanced Digital Sciences Center)

BibTeX Citation

@article{wang_vldb14,
        title = {{Efficient and Effective KNN Sequence Search with Approximate n-grams}},
        author = {Wang, Xiaoli and Ding, Xiaofeng and Tung, Anthony K.H. and Zhang, Zhenjie},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {1},
        pages = {1--12},
        doi = {10.14778/2732232.2732236},
        url = {https://doi.org/10.14778/2732232.2732236},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-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
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
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
2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.1621686e-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
3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.1663952e-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	911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB
3	1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
4	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
5	3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
6	796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD
7	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
8	6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB
9	6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB
10	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD