DBScholar

Back to papers

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.00011659702
Overall Rank
1,173 | 92.14%
DOI
-

Incoming Non-self Citations Over Time

Authors

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.0003567995
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027077763
202 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025244506
934 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00012973416
1,628 Efficient Processing of Joins on Set-valued Attributes 2003 SIGMOD 0.00010020209
3,604 Overlap Set Similarity Joins with Theoretical Guarantees 2018 SIGMOD 7.1548073e-05
5,348 On Indexing Error-Tolerant Set Containment 2010 SIGMOD 6.1551499e-05
6,136 The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication 2015 PODS 5.8578818e-05
6,224 Efficient Detection of Empty-Result Queries 2006 VLDB 5.828372e-05
7,630 On the Complexity of Join Predicates 2001 PODS 5.4642768e-05
7,840 You Say ‘What’, I Hear ‘Where’ and ‘Why’ — (Mis-)Interpreting SQL to Derive Fine-Grained Provenance 2018 VLDB 5.4260988e-05
7,917 On the complexity of division and set joins in the relational algebra 2005 PODS 5.4113016e-05
10,225 COMPARE: Accelerating Groupwise Comparison in Relational Databases for Data Analytics 2021 VLDB 5.0460607e-05
12,629 Efficient Implementation of Generalized Quantification in Relational Query Languages 2013 VLDB 4.9605343e-05
13,133 Symmetric Relations and Cardinality-Bounded Multisets in Database Systems 2004 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

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.00081781676
83 Hashing Methods and Relational Algebra Operations 1984 VLDB 0.00035942723
97 The Database Language GEM 1983 SIGMOD 0.00034172656
141 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00029191386
760 Partition Based Spatial-Merge Join 1996 SIGMOD 0.0001419395
999 Spatial Hash-Joins 1996 SIGMOD 0.00012590189
1,549 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010257684
1,598 Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates 1997 VLDB 0.00010096339
2,121 A Performance Evaluation of Pointer-Based Joins 1990 SIGMOD 8.9972659e-05
4,582 The BUCKY Object-Relational Benchmark 1997 SIGMOD 6.5092695e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,359 An Efficient Partition Based Method for Exact Set Similarity Joins 2016 VLDB
2 855 Hash-Partitioned Join Method Using Dynamic Destaging Strategy 1988 VLDB
3 1,603 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB
4 7,630 On the Complexity of Join Predicates 2001 PODS
5 1,516 Computing Joins Of Relations 1975 SIGMOD
6 1,598 Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates 1997 VLDB
7 202 Efficient set joins on similarity predicates 2004 SIGMOD
8 7,917 On the complexity of division and set joins in the relational algebra 2005 PODS
9 13,271 Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases 1998 VLDB
10 1,628 Efficient Processing of Joins on Set-valued Attributes 2003 SIGMOD