Efficient set joins on similarity predicates
Summary: General, scalable algorithm for set joins on similarity predicates (intersect size, Jaccard, cosine, edit distance) extending beyond simple containment. Inverted-index probing with staged optimizations, memory-efficient partitioning, and index compression enabling in-memory operation; generalizes to weighted/unweighted partial word overlap. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Sunita Sarawagi (Indian Institute of Technology Mumbai)
- 2. Alok Kirpal (Indian Institute of Technology Mumbai; Yahoo)
BibTeX Citation
@inproceedings{sarawagi_sigmod04,
title = {{Efficient set joins on similarity predicates}},
author = {Sarawagi, Sunita and Kirpal, Alok},
series = {{SIGMOD} '04},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/1007568.1007652},
url = {https://dl.acm.org/doi/10.1145/1007568.1007652},
year = {2004}
}Incoming Citations (Sorted by Pagerank)
Showing 4 of 54 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 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,993 | Bridging the Application and DBMS Profiling Divide for Database Application Developers | 2007 | VLDB | 4.9605343e-05 |
| 13,009 | Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing | 2007 | VLDB | 4.9605343e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 29 | Fast Algorithms for Mining Association Rules | 1994 | VLDB | 0.00051028332 |
| 108 | Approximate String Joins in a Database (Almost) for Free | 2001 | VLDB | 0.00032945275 |
| 162 | Robust and Efficient Fuzzy Match for Online Data Cleaning | 2003 | SIGMOD | 0.00027626077 |
| 220 | An Evaluation of Non-Equijoin Algorithms | 1991 | VLDB | 0.00024275691 |
| 308 | Eliminating Fuzzy Duplicates in Data Warehouses | 2002 | VLDB | 0.0002143466 |
| 1,173 | Set Containment Joins: The Good, The Bad and The Ugly | 2000 | VLDB | 0.00011659702 |
| 1,598 | Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates | 1997 | VLDB | 0.00010096339 |
| 1,628 | Efficient Processing of Joins on Set-valued Attributes | 2003 | SIGMOD | 0.00010020209 |
| 2,105 | Selectivity Estimation For Boolean Queries | 2000 | PODS | 9.0253094e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,400 | Extensible and Robust Evaluation of Similarity Queries | 2025 | VLDB |
| 2 | 359 | Efficient Parallel Set-Similarity Joins Using MapReduce | 2010 | SIGMOD |
| 3 | 8,434 | Fast Approximate Similarity Join in Vector Databases | 2025 | SIGMOD |
| 4 | 7,035 | Efficient Similarity Join and Search on Multi-Attribute Data | 2015 | SIGMOD |
| 5 | 3,604 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD |
| 6 | 3,359 | An Efficient Partition Based Method for Exact Set Similarity Joins | 2016 | VLDB |
| 7 | 169 | Efficient Exact Set-Similarity Joins | 2006 | VLDB |
| 8 | 1,628 | Efficient Processing of Joins on Set-valued Attributes | 2003 | SIGMOD |
| 9 | 2,514 | An Empirical Evaluation of Set Similarity Join Techniques | 2016 | VLDB |
| 10 | 2,933 | Leveraging Set Relations in Exact Set Similarity Join | 2017 | VLDB |