Back to papers
Approximate String Joins in a Database (Almost) for Free
Summary: Proposes approximate string joins on commercial DBs via q-grams; encodes match positions and counts, rewriting the predicate as a relational expression. Shows gains vs UDFs for full-string and substring joins; validated on real data and a prototype.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 8774
- Venue
- VLDB
- Year
- 2001
- Pagerank
- 0.00044946098
- Overall Rank
- 125 | 99.14%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 27 of 77 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 6,080 |
Pigeonring: A Principle for Faster Thresholded Similarity Search |
2019 |
VLDB |
5.219249e-05 |
| 6,458 |
Reference-Based Indexing of Sequence Databases |
2006 |
VLDB |
5.0484248e-05 |
| 6,673 |
Discovering Longest-lasting Correlation in Sequence Databases |
2013 |
VLDB |
4.962156e-05 |
| 6,730 |
A Pivotal Prefix Based Filtering Algorithm for String Similarity Search |
2014 |
SIGMOD |
4.9436522e-05 |
| 7,106 |
Efficient Similarity Join and Search on Multi-Attribute Data |
2015 |
SIGMOD |
4.8250163e-05 |
| 7,142 |
Efficient Error-tolerant Query Autocompletion |
2013 |
VLDB |
4.8151659e-05 |
| 7,215 |
SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins |
2023 |
VLDB |
4.7939964e-05 |
| 7,590 |
Scalable Column Concept Determination for Web Tables Using Large Knowledge Bases |
2013 |
VLDB |
4.6987033e-05 |
| 7,707 |
Efficient Top-k Algorithms for Approximate Substring Matching |
2013 |
SIGMOD |
4.6676985e-05 |
| 7,775 |
Indexing Mixed Types for Approximate Retrieval |
2005 |
VLDB |
4.6494306e-05 |
| 8,116 |
Customizable and Scalable Fuzzy Join for Big Data |
2019 |
VLDB |
4.5788731e-05 |
| 8,146 |
Approximate Substring Matching over Uncertain Strings |
2011 |
VLDB |
4.5724134e-05 |
| 8,300 |
Online Windowed Subsequence Matching over Probabilistic Sequences |
2012 |
SIGMOD |
4.5392079e-05 |
| 9,444 |
On-the-Fly Token Similarity Joins in Relational Databases |
2014 |
SIGMOD |
4.3382418e-05 |
| 9,831 |
Balance-Aware Distributed String Similarity-Based Query Processing System |
2019 |
VLDB |
4.2710095e-05 |
| 9,850 |
COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics |
2021 |
VLDB |
4.2680295e-05 |
| 9,933 |
Local Filtering: Improving the Performance of Approximate Queries on String Collections |
2015 |
SIGMOD |
4.245954e-05 |
| 9,934 |
Efficient and Effective KNN Sequence Search with Approximate n-grams |
2014 |
VLDB |
4.245954e-05 |
| 10,216 |
The Case For Language Model Approximated LIKE Predicate |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,714 |
Extensible and Robust Evaluation of Similarity Queries |
2025 |
VLDB |
4.1905499e-05 |
| 10,933 |
Similarity Joins of Sparse Features |
2024 |
SIGMOD |
4.1905499e-05 |
| 11,307 |
TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching |
2023 |
VLDB |
4.1905499e-05 |
| 11,730 |
ZigZag: Supporting Similarity Queries on Vector Space Models |
2018 |
SIGMOD |
4.1905499e-05 |
| 11,987 |
Similarity Joins for Uncertain Strings |
2014 |
SIGMOD |
4.1905499e-05 |
| 11,996 |
MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data |
2014 |
VLDB |
4.1905499e-05 |
| 12,553 |
SPIDER: Flexible Matching in Databases |
2005 |
SIGMOD |
4.1905499e-05 |
| 12,591 |
LexEQUAL: Multilexical Matching Operator in SQL |
2004 |
SIGMOD |
4.1905499e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 3,521 |
Merging the Results of Approximate Match Operations |
2004 |
VLDB |
7.0112669e-05 |
| 3,229 |
Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance |
2007 |
VLDB |
7.3390133e-05 |
| 4,215 |
Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints |
2010 |
VLDB |
6.3464157e-05 |
| 7,775 |
Indexing Mixed Types for Approximate Retrieval |
2005 |
VLDB |
4.6494306e-05 |
| 1,232 |
Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints |
2008 |
VLDB |
0.00013133604 |
| 9,436 |
Approximate Joins: Concepts and Techniques |
2005 |
VLDB |
4.3399748e-05 |
| 9,563 |
Towards a Unified Framework for String Similarity Joins |
2019 |
VLDB |
4.3212967e-05 |
| 11,987 |
Similarity Joins for Uncertain Strings |
2014 |
SIGMOD |
4.1905499e-05 |
| 7,707 |
Efficient Top-k Algorithms for Approximate Substring Matching |
2013 |
SIGMOD |
4.6676985e-05 |
| 4,907 |
Probabilistic String Similarity Joins |
2010 |
SIGMOD |
5.8365853e-05 |