A Two-Level Signature Scheme for Stable Set Similarity Joins

Summary: TwoL: a two-level hybrid signature framework for exact set similarity joins that detects unselective primary signatures and substitutes more selective secondary signatures to improve pruning. A cost model trades overhead vs selectivity; Jaccard and Hamming implementations give consistent SOTA gains on 13 diverse datasets. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13301
Venue: VLDB
Year: 2023
Pagerank: 5.093636e-05
Overall Rank: 11,447 | 21.47%
DOI: 10.14778/3611479.3611480

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Daniel Schmitt (University of Salzburg)
2. Daniel Kocher (University of Salzburg)
3. Nikolaus Augsten (University of Salzburg)
4. Willi Mann (Celonis)
5. Alexander Miller (University of Salzburg)

BibTeX Citation

@article{schmitt_vldb23,
        title = {{A Two-Level Signature Scheme for Stable Set Similarity Joins}},
        author = {Schmitt, Daniel and Kocher, Daniel and Augsten, Nikolaus and Mann, Willi and Miller, Alexander},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {11},
        pages = {2686--2698},
        doi = {10.14778/3611479.3611480},
        url = {https://doi.org/10.14778/3611479.3611480},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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,951	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	5.093636e-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
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
779	JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes	2019	SIGMOD	0.00014092047
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
2,501	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.4975661e-05
3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8262287e-05
3,041	Spatio-Textual Similarity Joins	2013	VLDB	7.8254399e-05
3,474	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3859271e-05
3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1715735e-05
4,052	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.935988e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
8,791	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	5.3717005e-05
9,317	Set Similarity Search for Skewed Data	2018	PODS	5.289545e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,806	On the Complexity of Inner Product Similarity Join	2016	PODS
2	9,702	Towards a Unified Framework for String Similarity Joins	2019	VLDB
3	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
4	169	Efficient Exact Set-Similarity Joins	2006	VLDB
5	11,504	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB
6	200	Efficient set joins on similarity predicates	2004	SIGMOD
7	7,476	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB
8	3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
9	2,501	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB
10	3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB