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: 8661
Venue: VLDB
Year: 2000
Pagerank: 0.00014457009
Overall Rank: 1,048 | 92.72%
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
98	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050023808
250	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030661988
266	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029718727
1,234	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013122499
1,763	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010638276
4,353	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.263585e-05
5,536	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	5.4532734e-05
5,553	On the Complexity of Join Predicates	2001	PODS	5.439162e-05
5,834	Efficient Detection of Empty-Result Queries	2006	VLDB	5.3103189e-05
5,902	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.2796864e-05
7,724	On the complexity of division and set joins in the relational algebra	2005	PODS	4.6673705e-05
8,230	You Say 'What', I Hear 'Where' and 'Why' - (Mis-)Interpreting SQL to Derive Fine-Grained Provenance	2018	VLDB	4.5541444e-05
9,850	COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics	2021	VLDB	4.2721228e-05
12,092	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	4.1945683e-05
12,603	Symmetric Relations and Cardinality-Bounded Multisets in Database Systems	2004	VLDB	4.1945683e-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.0014279444
30	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00078672446
68	The Database Language GEM	1983	SIGMOD	0.00060795269
153	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00040784455
871	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00015767786
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
1,562	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011356744
2,105	A Performance Evaluation of Pointer-Based Joins	1990	SIGMOD	9.5347454e-05
3,979	The BUCKY Object-Relational Benchmark	1997	SIGMOD	6.5681058e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,050	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	6.4953612e-05
3,490	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.0465856e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
5,553	On the Complexity of Join Predicates	2001	PODS	5.439162e-05
441	Computing Joins Of Relations	1975	SIGMOD	0.00023058395
1,562	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011356744
250	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030661988
7,724	On the complexity of division and set joins in the relational algebra	2005	PODS	4.6673705e-05
12,741	Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases	1998	VLDB	4.1945683e-05
1,763	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010638276