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.00011410373
Overall Rank: 1,231 | 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,249	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011340141
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011152286
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1406885e-05
2,338	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	8.6124366e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
2,796	Demonstration of the Myria Big Data Management Service	2014	SIGMOD	7.9971623e-05
3,685	The Myria Big Data Management and Analytics System and Cloud Service	2017	CIDR	7.0988339e-05
3,755	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.0452836e-05
3,977	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.8850687e-05
4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6541797e-05
4,460	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.5894687e-05
4,463	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5877664e-05
5,595	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0727701e-05
6,044	Topology Dependent Bounds For FAQs	2019	PODS	5.9055665e-05
6,386	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.8040725e-05
6,525	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.756805e-05
7,303	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5598057e-05
8,052	Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture	2014	PODS	5.3990042e-05
8,434	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3350162e-05
8,550	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.3168829e-05
8,614	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	5.3024208e-05
9,886	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	5.1166963e-05
11,433	CloudGlide: Deconstructing the Landscape of Cloud-Based Analytics	2025	VLDB	4.9793485e-05
11,480	Topology-aware Parallel Joins	2024	PODS	4.9793485e-05
11,493	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9793485e-05
11,941	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.9793485e-05
12,194	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9793485e-05
12,271	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.9793485e-05
12,327	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9793485e-05
12,375	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9793485e-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.001052036
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049839909
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043160717
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
977	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012731794
1,545	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010302384

Semantically Similar Papers

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