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: 1846
Venue: PODS
Year: 2021
Pagerank: 6.2086169e-05
Overall Rank: 5,463 | 62.52%
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,398	Query Evaluation by Circuits	2022	PODS	5.8867918e-05
6,444	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	5.8774519e-05
10,765	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.093636e-05
10,816	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	5.093636e-05
11,132	Topology-aware Parallel Joins	2024	PODS	5.093636e-05
11,145	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	5.093636e-05
11,635	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	5.093636e-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.00059843817
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
1,998	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.3363505e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
4,371	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.738679e-05
4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.7233577e-05
4,949	Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration	2015	PODS	6.4314032e-05

Semantically Similar Papers

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