Communication Steps for Parallel Query Processing

Summary: Tight single-round communication-space tradeoff for MPC: any 1-round algorithm needs replication exponent ε ≥ 1 - 1/τ*, where τ* is the fractional vertex cover of query q, with matching algorithms for certain database instances. First multi-round lower bounds under tuple-based routing, yielding a rounds-vs-ε tradeoff for tree-like conjunctive queries and implying transitive-closure cannot be done in O(1) rounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h16288a9dd96b0e29
Venue: PODS
Year: 2013
Pagerank: 0.00011372366
Overall Rank: 1,242 | 91.68%
DOI: 10.1145/2463664.2465224

Incoming Non-self Citations Over Time

Authors

1. Paul Beame (University of Washington)
2. Paraschos Koutris (University of Washington)
3. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{beame_pods13,
        address = {New York, NY, USA},
        series = {{PODS} '13},
        title = {{Communication Steps for Parallel Query Processing}},
        url = {https://dl.acm.org/doi/10.1145/2463664.2465224},
        doi = {10.1145/2463664.2465224},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Beame, Paul and Koutris, Paraschos and Suciu, Dan},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,253	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011316982
1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011119184
1,483	Skew in Parallel Query Processing	2014	PODS	0.00010500209
2,052	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1064522e-05
2,350	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	8.5846492e-05
2,475	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.3947133e-05
2,804	Demonstration of the Myria Big Data Management Service	2014	SIGMOD	7.96944e-05
3,693	The Myria Big Data Management and Analytics System and Cloud Service	2017	CIDR	7.0738965e-05
3,761	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.0186907e-05
3,985	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.8649592e-05
4,357	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6290396e-05
4,484	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.5645708e-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,059	Topology Dependent Bounds For FAQs	2019	PODS	5.8832527e-05
6,397	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.7822506e-05
6,539	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.7351897e-05
7,324	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5387994e-05
8,075	Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture	2014	PODS	5.3786044e-05
8,459	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3148581e-05
8,576	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.2968015e-05
8,643	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.2823858e-05
9,243	CloudGlide: Deconstructing the Landscape of Cloud-Based Analytics	2025	VLDB	5.1864799e-05
9,927	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	5.0974575e-05
11,538	Topology-aware Parallel Joins	2024	PODS	4.9605343e-05
11,551	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9605343e-05
11,991	Algorithms for a Topology-aware Massively Parallel Computation Model	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
12,376	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9605343e-05
12,424	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	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
6	Pig Latin: A Not-So-Foreign Language for Data Processing	2008	SIGMOD	0.0010494385
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049707539
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043085722
397	Worst-case Optimal Join Algorithms	2012	PODS	0.0001911958
982	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012687016
1,547	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010268377

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,993	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB
2	5,472	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB
3	2,115	Scheduling Problems in Parallel Query Optimization	1995	PODS
4	982	Parallel Evaluation of Conjunctive Queries	2011	PODS
5	9,393	Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems	1981	SIGMOD
6	8,643	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS
7	4,912	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
8	12,320	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS
9	1,483	Skew in Parallel Query Processing	2014	PODS
10	2,052	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS