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.0727701e-05
Overall Rank: 5,595 | 62.39%
DOI: 10.1145/3452021.3458319

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu (Duke University)

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,531	Query Evaluation by Circuits	2022	PODS	5.754708e-05
6,573	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	5.7455776e-05
9,950	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.1038322e-05
11,225	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9793485e-05
11,480	Topology-aware Parallel Joins	2024	PODS	4.9793485e-05
11,493	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9793485e-05
11,942	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.9793485e-05

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.00059752575
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020020639
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
977	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012731794
1,231	Communication Steps for Parallel Query Processing	2013	PODS	0.00011410373
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020855
2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1406885e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
4,463	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5877664e-05
4,475	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.5838041e-05
5,069	Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration	2015	PODS	6.2890683e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
2	2,043	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,202	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD
6	4,475	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS
7	7,608	On the Complexity of Join Predicates	2001	PODS
8	11,942	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS
9	3,660	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
10	4,463	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS