A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries

Summary: Multi-round MPC algorithm achieving worst-case per-server load m / p^(1/ρ*(Q)) for any full conjunctive query over binary relations, matching the known lower bound. Proves optimality for graph queries by extending chain/cycle techniques and exploiting graph-specific properties. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1706
Venue: PODS
Year: 2017
Pagerank: 8.0195487e-05
Overall Rank: 2,849 | 80.19%
DOI: 10.1145/3034786.3034788

Incoming Non-self Citations Over Time

Authors

1. Bas Ketsman
2. Dan Suciu

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,833	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7173578e-05
4,689	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	5.9980099e-05
4,708	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.980172e-05
5,639	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	5.393897e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8603097e-05
7,122	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	4.8252188e-05
8,462	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	4.5056381e-05
9,330	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	4.3556432e-05
10,231	Bifrost: A Much Simpler Secure Two-Party Data Join Protocol for Secure Data Analytics	2026	VLDB	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
11,436	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.1945683e-05
11,437	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1945683e-05
11,768	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
589	Massive Graph Triangulation	2013	SIGMOD	0.00019576567
1,110	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013968198
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
8,215	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5577562e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
9,581	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	4.3227214e-05
9,839	Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems	1981	SIGMOD	4.2739573e-05
1,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
11,768	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1945683e-05
1,110	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013968198
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
8,215	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5577562e-05
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565