Set Containment Joins: The Good, The Bad and The Ugly

Summary: Introduces PSJ, a partition-based set containment join using multilevel replication over elements and signatures. A Paradise implementation and extensive study show it consistently outperforms prior set-join algorithms across diverse datasets. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: ha64da76d05cb9941
Venue: VLDB
Year: 2000
Pagerank: 0.00011702886
Overall Rank: 1,171 | 92.13%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Karthikeyan Ramasamy (University of Wisconsin)
2. Jignesh M. Patel (University of Michigan-Ann Arbor)
3. Jeffrey F. Naughton (University of Wisconsin)
4. Raghav Kaushik (University of Wisconsin)

BibTeX Citation

@article{ramasamy_vldb00,
        title = {{Set Containment Joins: The Good, The Bad and The Ugly}},
        author = {Ramasamy, Karthikeyan and Patel, Jignesh M. and Naughton, Jeffrey F. and Kaushik, Raghav},
        journal = {PVLDB},
        series = {{VLDB} '00},
        pages = {351},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
86	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00035810622
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
1,618	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010056773
3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1790375e-05
5,333	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	6.1750986e-05
6,121	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.8800995e-05
6,208	Efficient Detection of Empty-Result Queries	2006	VLDB	5.8497045e-05
7,608	On the Complexity of Join Predicates	2001	PODS	5.4849468e-05
7,819	You Say ‘What’, I Hear ‘Where’ and ‘Why’ — (Mis-)Interpreting SQL to Derive Fine-Grained Provenance	2018	VLDB	5.4466474e-05
7,896	On the complexity of division and set joins in the relational algebra	2005	PODS	5.4318255e-05
10,189	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	5.0651993e-05
12,580	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	4.9793485e-05
13,086	Symmetric Relations and Cardinality-Bounded Multisets in Database Systems	2004	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081992507
82	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00036053776
96	The Database Language GEM	1983	SIGMOD	0.00034286345
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029294114
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
1,546	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010294163
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010133792
2,107	A Performance Evaluation of Pointer-Based Joins	1990	SIGMOD	9.03108e-05
4,562	The BUCKY Object-Relational Benchmark	1997	SIGMOD	6.5337025e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB
2	2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
3	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
4	7,608	On the Complexity of Join Predicates	2001	PODS
5	1,514	Computing Joins Of Relations	1975	SIGMOD
6	1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB
7	201	Efficient set joins on similarity predicates	2004	SIGMOD
8	7,896	On the complexity of division and set joins in the relational algebra	2005	PODS
9	13,224	Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases	1998	VLDB
10	1,618	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD