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
hee20d4f8857d69bc
Venue
VLDB
Year
2001
Pagerank
0.00032945275
Overall Rank
108 | 99.28%
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 28 of 78 citing papers.

Rank Citing Paper Year Venue Pagerank
6,617 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.7150599e-05
6,634 Reference-Based Indexing of Sequence Databases 2006 VLDB 5.7102782e-05
6,923 Discovering Longest-lasting Correlation in Sequence Databases 2013 VLDB 5.6297586e-05
6,988 Sampling Dirty Data for Matching Attributes 2010 SIGMOD 5.6110503e-05
7,035 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 5.5997831e-05
7,197 Efficient Error-tolerant Query Autocompletion 2013 VLDB 5.5730532e-05
7,640 SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins 2023 VLDB 5.4624931e-05
7,728 Scalable Column Concept Determination for Web Tables Using Large Knowledge Bases 2013 VLDB 5.4515436e-05
7,863 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.4220286e-05
8,241 Customizable and Scalable Fuzzy Join for Big Data 2019 VLDB 5.3560963e-05
8,267 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 5.3492332e-05
8,314 Approximate Substring Matching over Uncertain Strings 2011 VLDB 5.3410298e-05
8,737 Online Windowed Subsequence Matching over Probabilistic Sequences 2012 SIGMOD 5.2705676e-05
9,158 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 5.2041319e-05
9,825 On-the-Fly Token Similarity Joins in Relational Databases 2014 SIGMOD 5.1084057e-05
10,225 COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics 2021 VLDB 5.0460607e-05
10,331 Local Filtering: Improving the Performance of Approximate Queries on String Collections 2015 SIGMOD 5.0228171e-05
10,332 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.0228171e-05
10,762 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.9605343e-05
10,929 Pail: Efficient kNN Search on Set-Valued Attributes 2026 VLDB 4.9605343e-05
11,400 Extensible and Robust Evaluation of Similarity Queries 2025 VLDB 4.9605343e-05
11,555 Similarity Joins of Sparse Features 2024 SIGMOD 4.9605343e-05
11,863 TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching 2023 VLDB 4.9605343e-05
12,277 ZigZag: Supporting Similarity Queries on Vector Space Models 2018 SIGMOD 4.9605343e-05
12,517 Similarity Joins for Uncertain Strings 2014 SIGMOD 4.9605343e-05
12,526 MESA: A Map Service to Support Fuzzy Type-ahead Search over Geo-Textual Data 2014 VLDB 4.9605343e-05
13,075 SPIDER: Flexible Matching in Databases 2005 SIGMOD 4.9605343e-05
13,112 LexEQUAL: Multilexical Matching Operator in SQL 2004 SIGMOD 4.9605343e-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
164 Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity 1998 SIGMOD 0.00027451323
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024275691
598 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015711108
803 Near Neighbor Search in Large Metric Spaces 1995 VLDB 0.00013799572
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,981 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB
2 3,596 Merging the Results of Approximate Match Operations 2004 VLDB
3 3,822 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB
4 8,267 Indexing Mixed Types for Approximate Retrieval 2005 VLDB
5 934 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB
6 9,798 Approximate Joins: Concepts and Techniques 2005 VLDB
7 9,918 Towards a Unified Framework for String Similarity Joins 2019 VLDB
8 12,517 Similarity Joins for Uncertain Strings 2014 SIGMOD
9 7,863 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD
10 4,878 Probabilistic String Similarity Joins 2010 SIGMOD