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.9926463e-05
Overall Rank: 5,795 | 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,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4890984e-05
5,333	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	6.1750986e-05
10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.0418674e-05
12,604	ColumbuScout: Towards Building Local Search Engines over Large Databases	2012	SIGMOD	4.9793485e-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.0003305531
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
262	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00022821392
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
1,061	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012213729
1,581	Example-driven Design of Efficient Record Matching Queries	2007	VLDB	0.00010180038
1,643	Relaxing Join and Selection Queries	2006	VLDB	0.00010006399
1,737	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.7494976e-05
2,144	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9608583e-05
2,354	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.5896515e-05
2,461	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.4319356e-05
2,967	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.8029216e-05
3,501	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.2531528e-05
4,117	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.7958711e-05
4,140	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD	6.7854783e-05
4,439	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	6.5998035e-05
7,871	Incorporating String Transformations in Record Matching	2008	SIGMOD	5.4362081e-05
8,245	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	5.3694945e-05

Semantically Similar Papers

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