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: 1705
Venue: PODS
Year: 2017
Pagerank: 9.3363505e-05
Overall Rank: 1,998 | 86.30%
DOI: 10.1145/3034786.3034788

Incoming Non-self Citations Over Time

Authors

1. Bas Ketsman (Hasselt University; Transnational University of Limburg)
2. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{ketsman_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3034788},
        doi = {10.1145/3034786.3034788},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ketsman, Bas and Suciu, Dan},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
4,244	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.8062787e-05
4,371	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.738679e-05
5,463	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.2086169e-05
6,398	Query Evaluation by Circuits	2022	PODS	5.8867918e-05
7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.6915726e-05
8,394	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.4349805e-05
9,478	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.2634238e-05
10,519	Bifrost: A Much Simpler Secure Two-Party Data Join Protocol for Secure Data Analytics	2026	VLDB	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,634	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	5.093636e-05
11,635	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	5.093636e-05
11,894	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	5.093636e-05
11,973	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	5.093636e-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
594	Massive Graph Triangulation	2013	SIGMOD	0.00015979077
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
4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.7233577e-05
8,446	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.4240058e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB
2	9,718	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD
3	9,987	Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems	1981	SIGMOD
4	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
5	2,678	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
6	11,973	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS
7	954	Parallel Evaluation of Conjunctive Queries	2011	PODS
8	1,448	Skew in Parallel Query Processing	2014	PODS
9	8,446	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS
10	1,207	Communication Steps for Parallel Query Processing	2013	PODS