Efficient Exact Set-Similarity Joins

Summary: Exact set-similarity join (SSJoin) algorithms for cross-collection sets. First to achieve both exact results and deterministic performance guarantees, surpassing prior probabilistic-guarantee methods; validated on real and synthetic datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hc4582a31a4fff87e
Venue: VLDB
Year: 2006
Pagerank: 0.00027077763
Overall Rank: 169 | 98.87%
DOI: 10.14778/1164135.1164221

Incoming Non-self Citations Over Time

Authors

1. Arvind Arasu (Microsoft)
2. Venkatesh Ganti (Microsoft)
3. Raghav Kaushik (Microsoft)

BibTeX Citation

@article{arasu_vldb06,
        title = {{Efficient Exact Set-Similarity Joins}},
        author = {Arasu, Arvind and Ganti, Venkatesh and Kaushik, Raghav},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {918--929},
        doi = {10.14778/1164135.1164221},
        url = {https://doi.org/10.14778/1164135.1164221},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 30 of 80 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,404	Human-in-the-loop Data Integration	2017	VLDB	5.7797097e-05
6,504	Nexus: Correlation Discovery over Collections of Spatio-Temporal Tabular Data	2024	SIGMOD	5.7456631e-05
6,617	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.7150599e-05
7,244	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5606514e-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,893	Incorporating String Transformations in Record Matching	2008	SIGMOD	5.4156783e-05
8,019	Set Similarity Join on Probabilistic Data	2010	VLDB	5.3900267e-05
8,241	Customizable and Scalable Fuzzy Join for Big Data	2019	VLDB	5.3560963e-05
8,683	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2733366e-05
8,717	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD	5.2705676e-05
9,158	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.2041319e-05
9,296	Comparative evaluation of entity resolution approaches with FEVER	2009	VLDB	5.1860131e-05
9,535	Set Similarity Search for Skewed Data	2018	PODS	5.151324e-05
9,778	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.115551e-05
9,825	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.1084057e-05
9,855	Streaming Similarity Self-Join	2016	VLDB	5.1064323e-05
9,947	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.0910746e-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,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,668	Dealing with Acronyms, Abbreviations, and Typos in Real-World Entity Matching	2024	VLDB	4.9605343e-05
11,748	Grouping Time Series for Efficient Columnar Storage	2023	SIGMOD	4.9605343e-05
11,809	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	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

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057610161
57	On Random Sampling over Joins	1999	SIGMOD	0.0003999751
60	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.00039343755
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
164	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.00027451323
202	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025244506
231	Reference Reconciliation in Complex Information Spaces	2005	SIGMOD	0.00023797615
308	Eliminating Fuzzy Duplicates in Data Warehouses	2002	VLDB	0.0002143466
597	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015742369
1,173	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011659702
1,628	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010020209

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,434	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
2	4,282	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB
3	11,555	Similarity Joins of Sparse Features	2024	SIGMOD
4	8,019	Set Similarity Join on Probabilistic Data	2010	VLDB
5	2,235	String Similarity Joins: An Experimental Evaluation	2014	VLDB
6	202	Efficient set joins on similarity predicates	2004	SIGMOD
7	2,514	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB
8	3,604	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
9	2,933	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
10	3,359	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB