DBScholar

Back to papers

Near-Optimal Distributed Band-Joins through Recursive Partitioning

Summary: Recursive partitioning of the join-attribute space with a split-score yields near-optimal load and duplication for band-joins. Extends to multi-attribute band-joins, matching lower bounds within ~10% and reducing optimization cost versus prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h4581ef88169265e8
Venue
SIGMOD
Year
2020
Pagerank
5.6766099e-05
Overall Rank
6,743 | 54.81%
DOI
10.1145/3318464.3389750

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{li_sigmod20,
        title = {{Near-Optimal Distributed Band-Joins through Recursive Partitioning}},
        author = {Li, Rundong and Gatterbauer, Wolfgang and Riedewald, Mirek},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389750},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389750},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
5,469 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1022571e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
7,373 A Scalable and Generic Approach to Range Joins 2022 VLDB 5.5245298e-05
7,405 Lachesis: Automatic Partitioning for UDF-Centric Analytics 2021 VLDB 5.5172664e-05
10,435 I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026 CIDR 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 26 of 26 cited papers.

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

Rank Cited Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
156 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00028431734
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024275691
249 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD 0.00023099455
491 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00017383221
799 A Comparison of Join Algorithms for Log Processing in MapReduce 2010 SIGMOD 0.00013839554
836 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00013534835
867 Processing Theta-Joins using MapReduce* 2011 SIGMOD 0.00013342302
921 Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines 1990 VLDB 0.00013036878
928 The End of Slow Networks: It's Time for a Redesign 2016 VLDB 0.00013012601
1,215 Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC) 1990 VLDB 0.0001147464
1,259 Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning 1991 VLDB 0.00011296701
1,296 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011119184
1,483 Skew in Parallel Query Processing 2014 PODS 0.00010500209
1,675 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 9.8993233e-05
2,002 Track Join: Distributed Joins with Minimal Network Traffic 2014 SIGMOD 9.189062e-05
2,581 ClusterJoin: A Similarity Joins Framework using Map-Reduce 2014 VLDB 8.2491224e-05
2,944 Efficient Multi-way Theta-Join Processing Using MapReduce 2012 VLDB 7.8126906e-05
2,972 Scalable and Adaptive Online Joins 2014 VLDB 7.7844791e-05
3,638 Advanced Join Strategies for Large-Scale Distributed Computation 2014 VLDB 7.1248634e-05
3,977 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8707656e-05
4,282 Set Similarity Joins on MapReduce: An Experimental Survey 2018 VLDB 6.6712965e-05
5,680 Skew-Aware Join Optimization for Array Databases 2015 SIGMOD 6.0233693e-05
6,168 Similarity Join over Array Data 2016 SIGMOD 5.8484846e-05
7,284 Submodularity of Distributed Join Computation 2018 SIGMOD 5.5505534e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,475 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS
2 6,291 Fast and Effective Distribution-Key Recommendation for Amazon Redshift 2020 VLDB
3 3,638 Advanced Join Strategies for Large-Scale Distributed Computation 2014 VLDB
4 3,258 Locality-aware Partitioning in Parallel Database Systems 2015 SIGMOD
5 855 Hash-Partitioned Join Method Using Dynamic Destaging Strategy 1988 VLDB
6 2,972 Scalable and Adaptive Online Joins 2014 VLDB
7 12,347 Runtime Optimization of Join Location in Parallel Data Management Systems 2017 VLDB
8 220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB
9 12,432 Let's Rethink Join Optimization in Distributed Systems 2015 CIDR
10 7,284 Submodularity of Distributed Join Computation 2018 SIGMOD