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: h953d44a23c080ae6
Venue: PODS
Year: 2017
Pagerank: 9.1064522e-05
Overall Rank: 2,052 | 86.25%
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
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
2,475	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.3947133e-05
4,357	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6290396e-05
4,487	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5628751e-05
5,610	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0498245e-05
6,545	Query Evaluation by Circuits	2022	PODS	5.7329641e-05
7,313	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5428538e-05
8,576	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.2968015e-05
9,695	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.1258854e-05
10,775	Bifrost: A Much Simpler Secure Two-Party Data Join Protocol for Secure Data Analytics	2026	VLDB	4.9605343e-05
11,289	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9605343e-05
11,538	Topology-aware Parallel Joins	2024	PODS	4.9605343e-05
11,991	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.9605343e-05
11,992	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.9605343e-05
12,243	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9605343e-05
12,320	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.9605343e-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
599	Massive Graph Triangulation	2013	SIGMOD	0.00015700433
982	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012687016
1,242	Communication Steps for Parallel Query Processing	2013	PODS	0.00011372366
1,483	Skew in Parallel Query Processing	2014	PODS	0.00010500209
4,497	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.5592387e-05
8,643	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.2823858e-05

Semantically Similar Papers

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