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.3887172e-05
Overall Rank: 5,650 | 60.74%
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.8556471e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
10,498	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	4.1905499e-05
10,553	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.1905499e-05
10,915	Topology-aware Parallel Joins	2024	PODS	4.1905499e-05
10,929	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.1905499e-05
11,440	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1905499e-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.00078516827
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
2,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
2,856	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0120856e-05
3,831	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7146681e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
4,709	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.9744219e-05
4,783	Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration	2015	PODS	5.9215677e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,029	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.598451e-05
2,856	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0120856e-05
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
11,703	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	4.1905499e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
5,561	On the Complexity of Join Predicates	2001	PODS	5.4346872e-05
11,440	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1905499e-05
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
4,709	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.9744219e-05