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.0120856e-05
Overall Rank: 2,856 | 80.16%
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,831	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7146681e-05
4,641	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.0215749e-05
4,709	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.9744219e-05
5,650	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	5.3887172e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8556471e-05
7,117	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	4.8205884e-05
8,458	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	4.5013189e-05
9,335	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	4.351469e-05
10,231	Bifrost: A Much Simpler Secure Two-Party Data Join Protocol for Secure Data Analytics	2026	VLDB	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
11,439	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.1905499e-05
11,440	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.1905499e-05
11,776	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1905499e-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
588	Massive Graph Triangulation	2013	SIGMOD	0.00019588834
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
8,213	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5533861e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,948	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9938634e-05
9,582	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	4.3185789e-05
9,838	Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems	1981	SIGMOD	4.269862e-05
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
11,776	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1905499e-05
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
8,213	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5533861e-05
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832