Efficient Approximate Search on String Collections (Tutorial)

Summary: Tutorial survey of efficient approximate search in string collections. Comprehensive coverage: indexes, search algorithms, filtering, selectivity estimation, and related work; analyzes merits/limits and offers synthesis for scalable, practical design. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hef5c6f5988c248e5
Venue: VLDB
Year: 2009
Pagerank: 5.9898117e-05
Overall Rank: 5,797 | 61.04%
DOI: 10.14778/1687553.1687623

Incoming Non-self Citations Over Time

Authors

1. Marios Hadjieleftheriou (AT&T)
2. Chen Li (University of California Irvine)

BibTeX Citation

@article{hadjieleftheriou_vldb09,
        title = {{Efficient Approximate Search on String Collections (Tutorial)}},
        author = {Hadjieleftheriou, Marios and Li, Chen},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687553.1687623},
        url = {https://doi.org/10.14778/1687553.1687623},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,256	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4855571e-05
5,338	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	6.1722273e-05
10,303	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.0394806e-05
12,610	ColumbuScout: Towards Building Local Search Engines over Large Databases	2012	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033040246
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027151132
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025319937
262	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00022811258
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013014029
1,062	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012208031
1,581	Example-driven Design of Efficient Record Matching Queries	2007	VLDB	0.0001017553
1,643	Relaxing Join and Selection Queries	2006	VLDB	0.00010001728
1,739	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.7448851e-05
2,147	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9566452e-05
2,354	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.5872598e-05
2,461	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.4279724e-05
2,969	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.7993378e-05
3,501	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.2497317e-05
4,118	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.7927394e-05
4,141	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD	6.7822757e-05
4,441	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	6.5966903e-05
7,877	Incorporating String Transformations in Record Matching	2008	SIGMOD	5.4336352e-05
8,251	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	5.3669582e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,304	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
2	4,441	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
3	8,251	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
4	12,785	Worst-Case Efficient Range Search Indexing	2009	PODS
5	4,893	An Efficient Index Structure for String Databases	2001	VLDB
6	2,706	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
7	2,147	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD
8	9,119	On Searching Compressed String Collections Cache-Obliviously	2008	PODS
9	7,846	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
10	10,303	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD