DBScholar

Back to papers

Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins

Summary: Instance-dependent MPC algorithm for α-acyclic joins with closed-form worst-case load (bounded relation sizes) characterized by the fractional edge covering number and shown worst-case optimal. For certain cyclic joins, prove strictly higher MPC lower bounds via the fractional edge packing number that match algorithms, revealing a separation from RAM/AGM-based bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h9e26fcc609e938c1
Venue
PODS
Year
2021
Pagerank
6.0698953e-05
Overall Rank
5,596 | 62.39%
DOI
10.1145/3452021.3458319

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{hu_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458319},
        doi = {10.1145/3452021.3458319},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiao},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank Citing Paper Year Venue Pagerank
6,533 Query Evaluation by Circuits 2022 PODS 5.7519838e-05
6,576 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7428578e-05
9,958 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 5.1014161e-05
11,233 Jodes: Efficient Oblivious Join in the Distributed Setting 2025 VLDB 4.9769913e-05
11,486 Topology-aware Parallel Joins 2024 PODS 4.9769913e-05
11,499 Parallel Communication Obliviousness: One Round and Beyond 2024 PODS 4.9769913e-05
11,948 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank Cited Paper Year Venue Pagerank
17 Provenance Semirings 2007 PODS 0.00059813669
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019095982
978 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00012725823
1,233 Communication Steps for Parallel Query Processing 2013 PODS 0.00011404978
1,482 Skew in Parallel Query Processing 2014 PODS 0.00010534147
1,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020376
2,045 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 9.1363731e-05
2,464 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 8.4221003e-05
4,466 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.584648e-05
4,477 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.580699e-05
5,072 Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration 2015 PODS 6.2860922e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS
2 2,045 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS
3 1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD
4 402 Worst-case Optimal Join Algorithms 2012 PODS
5 12,208 Tighter Upper Bounds for Join Cardinality Estimates 2018 SIGMOD
6 4,477 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS
7 7,615 On the Complexity of Join Predicates 2001 PODS
8 11,948 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS
9 3,661 Scalable Computation of Acyclic Joins (Extended Abstract) 2006 PODS
10 4,466 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS