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
- 9984
- Venue
- VLDB
- Year
- 2009
- Pagerank
- 5.2829767e-05
- Overall Rank
- 5,892 | 59.06%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
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 |
| 125 |
Approximate String Joins in a Database (Almost) for Free |
2001 |
VLDB |
0.00044946098 |
| 248 |
Efficient set joins on similarity predicates |
2004 |
SIGMOD |
0.00030888982 |
| 264 |
Efficient Exact Set-Similarity Joins |
2006 |
VLDB |
0.00029950264 |
| 321 |
Record Linkage: Similarity Measures and Algorithms |
2006 |
SIGMOD |
0.00027524716 |
| 1,203 |
VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams |
2007 |
VLDB |
0.00013317317 |
| 1,232 |
Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints |
2008 |
VLDB |
0.00013133604 |
| 1,530 |
Example-driven Design of Efficient Record Matching Queries |
2007 |
VLDB |
0.00011483613 |
| 1,830 |
Relaxing Join and Selection Queries |
2006 |
VLDB |
0.0001037611 |
| 2,077 |
Extending Autocompletion To Tolerate Errors |
2009 |
SIGMOD |
9.6038296e-05 |
| 2,196 |
Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently |
2008 |
SIGMOD |
9.318552e-05 |
| 2,385 |
Leveraging Aggregate Constraints For Deduplication |
2007 |
SIGMOD |
8.9167648e-05 |
| 2,779 |
Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries |
2008 |
VLDB |
8.1314377e-05 |
| 3,229 |
Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance |
2007 |
VLDB |
7.3390133e-05 |
| 3,869 |
An Efficient Filter for Approximate Membership Checking |
2008 |
SIGMOD |
6.6776679e-05 |
| 4,410 |
Efficient Type-Ahead Search on Relational Data: a TASTIER Approach |
2009 |
SIGMOD |
6.2012075e-05 |
| 4,433 |
Selectivity Estimation for Fuzzy String Predicates in Large Data Sets |
2005 |
VLDB |
6.1852739e-05 |
| 4,878 |
Incremental Maintenance of Length Normalized Indexes for Approximate String Matching |
2009 |
SIGMOD |
5.8537044e-05 |
| 7,668 |
Incorporating String Transformations in Record Matching |
2008 |
SIGMOD |
4.6788985e-05 |
| 7,775 |
Indexing Mixed Types for Approximate Retrieval |
2005 |
VLDB |
4.6494306e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 9,934 |
Efficient and Effective KNN Sequence Search with Approximate n-grams |
2014 |
VLDB |
4.245954e-05 |
| 4,878 |
Incremental Maintenance of Length Normalized Indexes for Approximate String Matching |
2009 |
SIGMOD |
5.8537044e-05 |
| 7,775 |
Indexing Mixed Types for Approximate Retrieval |
2005 |
VLDB |
4.6494306e-05 |
| 12,302 |
Worst-Case Efficient Range Search Indexing |
2009 |
PODS |
4.1905499e-05 |
| 4,330 |
An Efficient Index Structure for String Databases |
2001 |
VLDB |
6.2745131e-05 |
| 1,184 |
On Effective Multi-Dimensional Indexing for Strings |
2000 |
SIGMOD |
0.00013442644 |
| 2,196 |
Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently |
2008 |
SIGMOD |
9.318552e-05 |
| 8,657 |
On Searching Compressed String Collections Cache-Obliviously |
2008 |
PODS |
4.4682399e-05 |
| 7,707 |
Efficient Top-k Algorithms for Approximate Substring Matching |
2013 |
SIGMOD |
4.6676985e-05 |
| 9,933 |
Local Filtering: Improving the Performance of Approximate Queries on String Collections |
2015 |
SIGMOD |
4.245954e-05 |