DBScholar

Back to papers

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.00011404978
Overall Rank
1,233 | 91.72%
DOI
10.1145/2463664.2465224

Incoming Non-self Citations Over Time

Authors

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,252 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011334813
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011147959
1,482 Skew in Parallel Query Processing 2014 PODS 0.00010534147
2,045 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 9.1363731e-05
2,340 Optimizing Graph Algorithms on Pregel-like Systems 2014 VLDB 8.6083649e-05
2,464 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 8.4221003e-05
2,796 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.9934519e-05
3,687 The Myria Big Data Management and Analytics System and Cloud Service 2017 CIDR 7.0954736e-05
3,757 Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures 2016 PODS 7.0419501e-05
3,978 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.8818094e-05
4,337 Algorithmic Aspects of Parallel Query Processing 2018 SIGMOD 6.6510297e-05
4,462 Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially 2019 VLDB 6.5863493e-05
4,466 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.584648e-05
5,596 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 6.0698953e-05
6,046 Topology Dependent Bounds For FAQs 2019 PODS 5.9027709e-05
6,389 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.8014043e-05
6,528 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 5.7540798e-05
7,306 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.5571749e-05
8,058 Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture 2014 PODS 5.3964484e-05
8,443 Efficient Matrix Sketching over Distributed Data 2017 PODS 5.3324907e-05
8,557 Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale 2020 CIDR 5.314366e-05
8,623 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 5.2999107e-05
9,893 Querying Shared Data with Security Heterogeneity 2020 SIGMOD 5.1142741e-05
11,439 CloudGlide: Deconstructing the Landscape of Cloud-Based Analytics 2025 VLDB 4.9769913e-05
11,486 Topology-aware Parallel Joins 2024 PODS 4.9769913e-05
11,499 Parallel Communication Obliviousness: One Round and Beyond 2024 PODS 4.9769913e-05
11,947 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.9769913e-05
12,200 Distributed Statistical Estimation of Matrix Products with Applications 2018 PODS 4.9769913e-05
12,277 Communication Cost in Parallel Query Evaluation: A Tutorial 2017 PODS 4.9769913e-05
12,333 Logical Aspects of Massively Parallel and Distributed Systems 2016 PODS 4.9769913e-05
12,381 Parallel Evaluation of Multi-Semi-Joins 2016 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

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.0010515896
31 Hive - A Warehousing Solution Over a Map-Reduce Framework 2009 VLDB 0.00049821554
49 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.0004314366
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019095982
978 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00012725823
1,546 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.0001029751
Previous Page 1 / 1 Next

Semantically Similar Papers

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