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

Summary: Partitioning Set Join Algorithm (PSJ) for set containment joins on set-valued attributes; novel replicating multilevel partitioning based on elements and signatures. Implemented in Paradise, PSJ outperforms prior set-join methods across diverse data sets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8662
Venue: VLDB
Year: 2000
Pagerank: 0.00014468616
Overall Rank: 1,043 | 92.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
99	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050043993
248	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030888982
264	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029950264
1,232	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013133604
1,757	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010659352
4,350	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.2576191e-05
5,544	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	5.4481372e-05
5,561	On the Complexity of Join Predicates	2001	PODS	5.4346872e-05
5,846	Efficient Detection of Empty-Result Queries	2006	VLDB	5.3052255e-05
5,905	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.2746158e-05
7,722	On the complexity of division and set joins in the relational algebra	2005	PODS	4.6628934e-05
8,228	You Say 'What', I Hear 'Where' and 'Why' - (Mis-)Interpreting SQL to Derive Fine-Grained Provenance	2018	VLDB	4.549777e-05
9,850	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	4.2680295e-05
12,100	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	4.1905499e-05
12,612	Symmetric Relations and Cardinality-Bounded Multisets in Database Systems	2004	VLDB	4.1905499e-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
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.001426258
30	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00078665259
68	The Database Language GEM	1983	SIGMOD	0.00060817676
153	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00040759404
862	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00015798065
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
1,559	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011368746
2,107	A Performance Evaluation of Pointer-Based Joins	1990	SIGMOD	9.5285135e-05
3,980	The BUCKY Object-Relational Benchmark	1997	SIGMOD	6.5617607e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,461	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.0696567e-05
549	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00020348047
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
5,561	On the Complexity of Join Predicates	2001	PODS	5.4346872e-05
445	Computing Joins Of Relations	1975	SIGMOD	0.00023029279
1,559	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011368746
248	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030888982
7,722	On the complexity of division and set joins in the relational algebra	2005	PODS	4.6628934e-05
12,750	Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases	1998	VLDB	4.1905499e-05
1,757	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010659352