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: 8852
Venue: VLDB
Year: 2000
Pagerank: 0.00011938186
Overall Rank: 1,151 | 92.11%
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
79	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00036555628
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
1,592	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010253457
3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1715735e-05
5,306	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	6.2731936e-05
5,996	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	6.0150613e-05
6,084	Efficient Detection of Empty-Result Queries	2006	VLDB	5.9830699e-05
7,467	On the Complexity of Join Predicates	2001	PODS	5.6103871e-05
7,732	On the complexity of division and set joins in the relational algebra	2005	PODS	5.5564984e-05
8,145	You Say ‘What’, I Hear ‘Where’ and ‘Why’ — (Mis-)Interpreting SQL to Derive Fine-Grained Provenance	2018	VLDB	5.4790624e-05
10,002	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	5.1814573e-05
12,289	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	5.093636e-05
12,796	Symmetric Relations and Cardinality-Bounded Multisets in Database Systems	2004	VLDB	5.093636e-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.00083340894
80	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00036536643
92	The Database Language GEM	1983	SIGMOD	0.00034759032
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,517	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010520118
1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.0001034191
2,070	A Performance Evaluation of Pointer-Based Joins	1990	SIGMOD	9.2277271e-05
4,469	The BUCKY Object-Relational Benchmark	1997	SIGMOD	6.6818543e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
2	844	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB
3	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
4	7,467	On the Complexity of Join Predicates	2001	PODS
5	1,479	Computing Joins Of Relations	1975	SIGMOD
6	1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB
7	200	Efficient set joins on similarity predicates	2004	SIGMOD
8	7,732	On the complexity of division and set joins in the relational algebra	2005	PODS
9	12,934	Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases	1998	VLDB
10	1,592	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD