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: 1814
Venue: PODS
Year: 2021
Pagerank: 5.393897e-05
Overall Rank: 5,639 | 60.78%
DOI: 10.1145/3452021.3458319

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,017	Query Evaluation by Circuits	2022	PODS	4.8603097e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
10,488	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	4.1945683e-05
10,544	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.1945683e-05
10,911	Topology-aware Parallel Joins	2024	PODS	4.1945683e-05
10,925	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.1945683e-05
11,437	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1945683e-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
31	Provenance Semirings	2007	PODS	0.0007857786
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
1,110	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013968198
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
2,849	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0195487e-05
3,833	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7173578e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
4,708	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.980172e-05
4,779	Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration	2015	PODS	5.9271735e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,028	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.6028646e-05
2,849	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0195487e-05
1,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
11,698	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	4.1945683e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
5,553	On the Complexity of Join Predicates	2001	PODS	5.439162e-05
11,437	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1945683e-05
3,515	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0220813e-05
4,708	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.980172e-05