Leveraging Set Relations in Exact Set Similarity Join

Summary: Leverages index- and answer-level set relations to improve exact set similarity join beyond standard filtering-verification. Index-blocking reduces filtering to linear cost; incremental answer reuse across similar sets yields speedups on 21 real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11773
Venue: VLDB
Year: 2017
Pagerank: 7.8262287e-05
Overall Rank: 3,040 | 79.15%
DOI: 10.14778/3099622.3099624

Incoming Non-self Citations Over Time

Authors

1. Xubo Wang (University of New South Wales)
2. Lu Qin (University of Technology Sydney)
3. Xuemin Lin (University of New South Wales)
4. Ying Zhang (University of Technology Sydney)
5. Lijun Chang (University of New South Wales)

BibTeX Citation

@article{wang_vldb17,
        title = {{Leveraging Set Relations in Exact Set Similarity Join}},
        author = {Wang, Xubo and Qin, Lu and Lin, Xuemin and Zhang, Ying and Chang, Lijun},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {9},
        pages = {925--936},
        doi = {10.14778/3099622.3099624},
        url = {https://doi.org/10.14778/3099622.3099624},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
779	JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes	2019	SIGMOD	0.00014092047
3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1715735e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
7,745	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	5.5534781e-05
8,522	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD	5.4119882e-05
8,733	FINEX: A Fast Index for Exact & Flexible Density-Based Clustering	2023	SIGMOD	5.3766157e-05
10,533	SeDA: Bridging the Gap between Efficient Syntactic and Precise Semantic Search of Similar Passages in Large Text Corpora	2026	VLDB	5.093636e-05
10,567	FB*: A Compact Index for Efficient and Exact Density-based Clustering	2026	VLDB	5.093636e-05
10,951	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	5.093636e-05
11,447	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	5.093636e-05
11,504	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB	5.093636e-05
11,702	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.093636e-05
11,929	ZigZag: Supporting Similarity Queries on Vector Space Models	2018	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
160	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.0002802209
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
196	CrowdER: Crowdsourcing Entity Resolution	2012	VLDB	0.00025780596
356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020303289
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
991	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012793339
1,415	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010840141
1,935	ATLAS: A Probabilistic Algorithm for High Dimensional Similarity Search	2011	SIGMOD	9.4560124e-05
2,501	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.4975661e-05
2,567	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	8.4098241e-05
3,041	Spatio-Textual Similarity Joins	2013	VLDB	7.8254399e-05
3,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.4122197e-05
3,474	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3859271e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD
2	975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD
3	1,592	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD
4	9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
5	6,906	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
6	3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
7	3,474	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB
8	169	Efficient Exact Set-Similarity Joins	2006	VLDB
9	200	Efficient set joins on similarity predicates	2004	SIGMOD
10	2,501	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB