Efficient Top-k Algorithms for Approximate Substring Matching

Summary: Proposes top-k approximate substring matching over long strings under edit-distance with containment search. It uses novel filtering based on q-grams and inverted q-gram indexes to prune distance computations, achieving scalable, efficient performance on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4731
Venue: SIGMOD
Year: 2013
Pagerank: 4.6721808e-05
Overall Rank: 7,708 | 46.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Younghoon Kim
2. Kyuseok Shim

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,936	Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning	2020	VLDB	5.2654071e-05
6,726	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9484027e-05
7,474	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	4.7194345e-05
9,726	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD	4.2943379e-05
10,216	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
1,202	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00013326298
2,073	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6142791e-05
2,171	Selectivity Estimation For Boolean Queries	2000	PODS	9.3807165e-05
2,376	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9424361e-05
3,226	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.3433307e-05
3,578	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	6.9503858e-05
4,026	Flexible String Matching Against Large Databases in Practice	2004	VLDB	6.5169976e-05
4,438	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.1898903e-05
5,073	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	5.7177424e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,226	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.3433307e-05
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
6,983	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	4.8732757e-05
6,726	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9484027e-05
4,333	An Efficient Index Structure for String Databases	2001	VLDB	6.2805237e-05
1,234	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013122499
9,932	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	4.2500258e-05
8,143	Approximate Substring Matching over Uncertain Strings	2011	VLDB	4.5768015e-05
9,933	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	4.2500258e-05