DBScholar

Back to papers

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.9701598e-05
Overall Rank
5,811 | 61.05%
DOI
10.14778/1687553.1687623

Incoming Non-self Citations Over Time

Authors

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,270 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4613275e-05
5,348 On Indexing Error-Tolerant Set Containment 2010 SIGMOD 6.1551499e-05
10,331 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.0228171e-05
12,653 ColumbuScout: Towards Building Local Search Engines over Large Databases 2012 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

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.00032945275
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027077763
202 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025244506
264 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.0002276412
934 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00012973416
1,068 VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams 2007 VLDB 0.00012170201
1,582 Example-driven Design of Efficient Record Matching Queries 2007 VLDB 0.0001015019
1,649 Relaxing Join and Selection Queries 2006 VLDB 9.9699016e-05
1,751 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.7128647e-05
2,158 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 8.9272802e-05
2,362 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.5601252e-05
2,469 Leveraging Aggregate Constraints For Deduplication 2007 SIGMOD 8.401808e-05
2,981 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.7739779e-05
3,511 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 7.22602e-05
4,138 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7706361e-05
4,156 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.7602028e-05
4,462 Incremental Maintenance of Length Normalized Indexes for Approximate String Matching 2009 SIGMOD 6.5751733e-05
7,893 Incorporating String Transformations in Record Matching 2008 SIGMOD 5.4156783e-05
8,267 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 5.3492332e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,494 MRCSI: Compressing and Searching String Collections with Multiple References 2015 VLDB
2 4,462 Incremental Maintenance of Length Normalized Indexes for Approximate String Matching 2009 SIGMOD
3 8,267 Indexing Mixed Types for Approximate Retrieval 2005 VLDB
4 12,828 Worst-Case Efficient Range Search Indexing 2009 PODS
5 4,921 An Efficient Index Structure for String Databases 2001 VLDB
6 2,717 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD
7 2,158 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD
8 9,138 On Searching Compressed String Collections Cache-Obliviously 2008 PODS
9 7,863 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD
10 10,331 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD