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: 1606
Venue: PODS
Year: 2013
Pagerank: 0.00011663155
Overall Rank: 1,207 | 91.73%
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,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011504088
1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011166426
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,998	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.3363505e-05
2,295	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	8.7932254e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
2,804	Demonstration of the Myria Big Data Management Service	2014	SIGMOD	8.1075524e-05
3,618	The Myria Big Data Management and Analytics System and Cloud Service	2017	CIDR	7.2523695e-05
3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.2030591e-05
3,892	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	7.0430255e-05
4,244	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.8062787e-05
4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.7407122e-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
5,923	Topology Dependent Bounds For FAQs	2019	PODS	6.0411129e-05
6,332	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.9107433e-05
6,403	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.8859374e-05
7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.6873519e-05
7,884	Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture	2014	PODS	5.5229059e-05
8,268	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.4574671e-05
8,394	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.4349805e-05
8,446	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.4240058e-05
9,716	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	5.2336921e-05
11,076	CloudGlide: Deconstructing the Landscape of Cloud-Based Analytics	2025	VLDB	5.093636e-05
11,132	Topology-aware Parallel Joins	2024	PODS	5.093636e-05
11,145	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	5.093636e-05
11,634	Algorithms for a Topology-aware Massively Parallel Computation Model	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
12,032	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	5.093636e-05
12,082	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	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
6	Pig Latin: A Not-So-Foreign Language for Data Processing	2008	SIGMOD	0.0010686205
32	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00050111008
51	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004291425
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,514	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010527649

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,341	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB
2	3,046	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB
3	2,068	Scheduling Problems in Parallel Query Optimization	1995	PODS
4	954	Parallel Evaluation of Conjunctive Queries	2011	PODS
5	9,987	Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems	1981	SIGMOD
6	8,446	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS
7	4,773	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
8	11,973	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS
9	1,448	Skew in Parallel Query Processing	2014	PODS
10	1,998	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS