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)
Incoming Non-self Citations Over Time
Authors
- 1. Luis Gravano (Columbia University)
- 2. Panagiotis G. Ipeirotis (Columbia University)
- 3. H. V. Jagadish (University of Michigan)
- 4. Nick Koudas (AT&T)
- 5. S. Muthukrishnan (AT&T)
- 6. Divesh Srivastava (AT&T)
BibTeX Citation
@article{gravano_vldb01,
title = {{Approximate String Joins in a Database (Almost) for Free}},
author = {Gravano, Luis and Ipeirotis, Panagiotis G. and Jagadish, H. V. and Koudas, Nick and Muthukrishnan, S. and Srivastava, Divesh},
journal = {PVLDB},
series = {{VLDB} '01},
year = {2001}
}Incoming Citations (Sorted by Pagerank)
Showing 28 of 78 citing papers.
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.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 162 | Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity | 1998 | SIGMOD | 0.00027536748 |
| 220 | An Evaluation of Non-Equijoin Algorithms | 1991 | VLDB | 0.00024344086 |
| 597 | Distance-Based Indexing For High-Dimensional Metric Spaces | 1997 | SIGMOD | 0.00015766567 |
| 802 | Near Neighbor Search in Large Metric Spaces | 1995 | VLDB | 0.00013847746 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,593 | Merging the Results of Approximate Match Operations | 2004 | VLDB |
| 2 | 2,967 | Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance | 2007 | VLDB |
| 3 | 3,816 | Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints | 2010 | VLDB |
| 4 | 8,245 | Indexing Mixed Types for Approximate Retrieval | 2005 | VLDB |
| 5 | 929 | Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints | 2008 | VLDB |
| 6 | 9,761 | Approximate Joins: Concepts and Techniques | 2005 | VLDB |
| 7 | 9,878 | Towards a Unified Framework for String Similarity Joins | 2019 | VLDB |
| 8 | 12,468 | Similarity Joins for Uncertain Strings | 2014 | SIGMOD |
| 9 | 7,842 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD |
| 10 | 4,849 | Probabilistic String Similarity Joins | 2010 | SIGMOD |