Database Paper Browser

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
1607
Venue
PODS
Year
2013
Pagerank
0.0001212565
Overall Rank
1,411 | 90.19%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 30 of 30 citing papers.

Rank Citing Paper Year Venue Pagerank
1,939 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025655
1,953 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 9.9665955e-05
2,212 Skew in Parallel Query Processing 2014 PODS 9.2771827e-05
2,336 Optimizing Graph Algorithms on Pregel-like Systems 2014 VLDB 9.0109891e-05
2,849 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0195487e-05
3,377 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.1624478e-05
3,833 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 6.7173578e-05
3,982 The Myria Big Data Management and Analytics System and Cloud Service 2017 CIDR 6.5651188e-05
4,021 Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures 2016 PODS 6.5225987e-05
4,083 Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially 2019 VLDB 6.4638932e-05
4,562 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.0846728e-05
4,689 Algorithmic Aspects of Parallel Query Processing 2018 SIGMOD 5.9980099e-05
4,708 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.980172e-05
5,639 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.393897e-05
5,828 Topology Dependent Bounds For FAQs 2019 PODS 5.3113542e-05
6,690 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 4.9621556e-05
6,695 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 4.9582125e-05
7,054 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8496866e-05
7,822 Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture 2014 PODS 4.6426494e-05
7,949 Efficient Matrix Sketching over Distributed Data 2017 PODS 4.613363e-05
8,215 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5577562e-05
8,462 Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale 2020 CIDR 4.5056381e-05
9,578 Querying Shared Data with Security Heterogeneity 2020 SIGMOD 4.3248081e-05
10,852 CloudGlide: Deconstructing the Landscape of Cloud-Based Analytics 2025 VLDB 4.1945683e-05
10,911 Topology-aware Parallel Joins 2024 PODS 4.1945683e-05
10,925 Parallel Communication Obliviousness: One Round and Beyond 2024 PODS 4.1945683e-05
11,436 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.1945683e-05
11,768 Communication Cost in Parallel Query Evaluation: A Tutorial 2017 PODS 4.1945683e-05
11,831 Logical Aspects of Massively Parallel and Distributed Systems 2016 PODS 4.1945683e-05
11,882 Parallel Evaluation of Multi-Semi-Joins 2016 VLDB 4.1945683e-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
3 Pig Latin: A Not-So-Foreign Language for Data Processing 2008 SIGMOD 0.0024183614
70 Hive - A Warehousing Solution Over a Map-Reduce Framework 2009 VLDB 0.00059533166
109 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00048186983
502 Worst-case Optimal Join Algorithms 2012 PODS 0.00021526612
1,110 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013968198
1,308 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.00012661651
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,124 Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources 1997 VLDB 7.5201555e-05
4,852 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8764777e-05
1,672 Scheduling Problems in Parallel Query Optimization 1995 PODS 0.00010949448
1,110 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013968198
9,839 Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems 1981 SIGMOD 4.2739573e-05
8,215 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5577562e-05
4,288 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2891396e-05
11,768 Communication Cost in Parallel Query Evaluation: A Tutorial 2017 PODS 4.1945683e-05
2,212 Skew in Parallel Query Processing 2014 PODS 9.2771827e-05
2,849 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0195487e-05