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.00027163517
Overall Rank: 168 | 98.88%
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,397	Human-in-the-loop Data Integration	2017	VLDB	5.7989499e-05
6,491	Nexus: Correlation Discovery over Collections of Spatio-Temporal Tabular Data	2024	SIGMOD	5.7674551e-05
6,605	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.7367357e-05
7,226	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5810344e-05
7,619	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.4832111e-05
7,709	Scalable Column Concept Determination for Web Tables Using Large Knowledge Bases	2013	VLDB	5.4717883e-05
7,871	Incorporating String Transformations in Record Matching	2008	SIGMOD	5.4362081e-05
7,998	Set Similarity Join on Probabilistic Data	2010	VLDB	5.4104124e-05
8,219	Customizable and Scalable Fuzzy Join for Big Data	2019	VLDB	5.3761699e-05
8,658	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2933372e-05
8,689	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD	5.2905577e-05
9,126	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.22387e-05
9,262	Comparative evaluation of entity resolution approaches with FEVER	2009	VLDB	5.2056825e-05
9,495	Set Similarity Search for Skewed Data	2018	PODS	5.1708619e-05
9,741	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.1349531e-05
9,788	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.1272311e-05
9,814	Streaming Similarity Self-Join	2016	VLDB	5.1257999e-05
9,905	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.1103839e-05
10,189	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	5.0651993e-05
10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.0418674e-05
10,299	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	5.0418674e-05
10,859	Pail: Efficient kNN Search on Set-Valued Attributes	2026	VLDB	4.9793485e-05
11,339	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9793485e-05
11,497	Similarity Joins of Sparse Features	2024	SIGMOD	4.9793485e-05
11,615	Dealing with Acronyms, Abbreviations, and Typos in Real-World Entity Matching	2024	VLDB	4.9793485e-05
11,696	Grouping Time Series for Efficient Columnar Storage	2023	SIGMOD	4.9793485e-05
11,759	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	4.9793485e-05
11,813	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB	4.9793485e-05
12,228	ZigZag: Supporting Similarity Queries on Vector Space Models	2018	SIGMOD	4.9793485e-05
12,468	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.9793485e-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.00057568153
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
60	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.000394583
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
161	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00027718195
162	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.00027536748
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
230	Reference Reconciliation in Complex Information Spaces	2005	SIGMOD	0.00023871933
307	Eliminating Fuzzy Duplicates in Data Warehouses	2002	VLDB	0.00021499031
595	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015798582
1,171	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011702886
1,618	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010056773

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
2	4,274	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB
3	11,497	Similarity Joins of Sparse Features	2024	SIGMOD
4	7,998	Set Similarity Join on Probabilistic Data	2010	VLDB
5	2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB
6	201	Efficient set joins on similarity predicates	2004	SIGMOD
7	2,513	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB
8	3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
9	2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
10	3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB