DBScholar

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
8964
Venue
VLDB
Year
2001
Pagerank
0.00033511706
Overall Rank
107 | 99.27%
DOI
-

Incoming Non-self Citations Over Time

Authors

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 27 of 77 citing papers.

Rank Citing Paper Year Venue Pagerank
6,484 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.8665833e-05
6,496 Reference-Based Indexing of Sequence Databases 2006 VLDB 5.8632988e-05
6,780 Discovering Longest-lasting Correlation in Sequence Databases 2013 VLDB 5.7766335e-05
6,827 Sampling Dirty Data for Matching Attributes 2010 SIGMOD 5.7616041e-05
6,906 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 5.7418509e-05
7,031 Efficient Error-tolerant Query Autocompletion 2013 VLDB 5.72252e-05
7,476 SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins 2023 VLDB 5.6090634e-05
7,575 Scalable Column Concept Determination for Web Tables Using Large Knowledge Bases 2013 VLDB 5.5937684e-05
7,692 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.5664611e-05
8,078 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 5.492543e-05
8,088 Customizable and Scalable Fuzzy Join for Big Data 2019 VLDB 5.4900832e-05
8,114 Approximate Substring Matching over Uncertain Strings 2011 VLDB 5.484341e-05
8,542 Online Windowed Subsequence Matching over Probabilistic Sequences 2012 SIGMOD 5.4119882e-05
9,613 On-the-Fly Token Similarity Joins in Relational Databases 2014 SIGMOD 5.2447096e-05
9,979 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 5.1845938e-05
10,002 COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics 2021 VLDB 5.1814573e-05
10,085 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.1559617e-05
10,086 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.1559617e-05
10,505 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 5.093636e-05
10,951 Extensible and Robust Evaluation of Similarity Queries 2025 VLDB 5.093636e-05
11,149 Similarity Joins of Sparse Features 2024 SIGMOD 5.093636e-05
11,504 TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching 2023 VLDB 5.093636e-05
11,929 ZigZag: Supporting Similarity Queries on Vector Space Models 2018 SIGMOD 5.093636e-05
12,177 Similarity Joins for Uncertain Strings 2014 SIGMOD 5.093636e-05
12,186 MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data 2014 VLDB 5.093636e-05
12,737 SPIDER: Flexible Matching in Databases 2005 SIGMOD 5.093636e-05
12,775 LexEQUAL: Multilexical Matching Operator in SQL 2004 SIGMOD 5.093636e-05
Previous Page 2 / 2 Next

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
160 Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity 1998 SIGMOD 0.0002802209
210 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024797689
592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00016029789
784 Near Neighbor Search in Large Metric Spaces 1995 VLDB 0.00014069958
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,610 Merging the Results of Approximate Match Operations 2004 VLDB
2 2,899 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB
3 3,731 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB
4 8,078 Indexing Mixed Types for Approximate Retrieval 2005 VLDB
5 911 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB
6 9,584 Approximate Joins: Concepts and Techniques 2005 VLDB
7 9,702 Towards a Unified Framework for String Similarity Joins 2019 VLDB
8 12,177 Similarity Joins for Uncertain Strings 2014 SIGMOD
9 7,692 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD
10 4,743 Probabilistic String Similarity Joins 2010 SIGMOD