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
10174
Venue
VLDB
Year
2009
Pagerank
6.1279762e-05
Overall Rank
5,667 | 61.13%
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,193 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.649474e-05
5,306 On Indexing Error-Tolerant Set Containment 2010 SIGMOD 6.2731936e-05
10,085 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.1559617e-05
12,313 ColumbuScout: Towards Building Local Search Engines over Large Databases 2012 SIGMOD 5.093636e-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
107 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033511706
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.0002743469
200 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025597287
254 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00023199211
911 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013283031
1,040 VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams 2007 VLDB 0.00012466499
1,560 Example-driven Design of Efficient Record Matching Queries 2007 VLDB 0.00010361222
1,636 Relaxing Join and Selection Queries 2006 VLDB 0.00010156479
1,701 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.9707165e-05
2,103 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.1621686e-05
2,308 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.7738996e-05
2,410 Leveraging Aggregate Constraints For Deduplication 2007 SIGMOD 8.6126774e-05
2,899 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.97814e-05
3,442 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 7.4122197e-05
4,035 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.9439151e-05
4,048 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.9372074e-05
4,359 Incremental Maintenance of Length Normalized Indexes for Approximate String Matching 2009 SIGMOD 6.7451753e-05
7,714 Incorporating String Transformations in Record Matching 2008 SIGMOD 5.5608517e-05
8,078 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 5.492543e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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