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.00012118832
Overall Rank
1,411 | 90.20%
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,938 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025547
1,948 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 9.9938634e-05
2,216 Skew in Parallel Query Processing 2014 PODS 9.2693784e-05
2,332 Optimizing Graph Algorithms on Pregel-like Systems 2014 VLDB 9.0173968e-05
2,856 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0120856e-05
3,371 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.1634294e-05
3,831 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 6.7146681e-05
3,983 The Myria Big Data Management and Analytics System and Cloud Service 2017 CIDR 6.5588011e-05
4,026 Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures 2016 PODS 6.5166769e-05
4,077 Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially 2019 VLDB 6.4634641e-05
4,560 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.0788254e-05
4,641 Algorithmic Aspects of Parallel Query Processing 2018 SIGMOD 6.0215749e-05
4,709 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.9744219e-05
5,650 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.3887172e-05
5,840 Topology Dependent Bounds For FAQs 2019 PODS 5.3062554e-05
6,691 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 4.9573939e-05
6,699 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 4.9534535e-05
7,046 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8471584e-05
7,826 Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture 2014 PODS 4.6381971e-05
7,952 Efficient Matrix Sketching over Distributed Data 2017 PODS 4.6089395e-05
8,213 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5533861e-05
8,458 Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale 2020 CIDR 4.5013189e-05
9,577 Querying Shared Data with Security Heterogeneity 2020 SIGMOD 4.3206631e-05
10,856 CloudGlide: Deconstructing the Landscape of Cloud-Based Analytics 2025 VLDB 4.1905499e-05
10,915 Topology-aware Parallel Joins 2024 PODS 4.1905499e-05
10,929 Parallel Communication Obliviousness: One Round and Beyond 2024 PODS 4.1905499e-05
11,439 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.1905499e-05
11,776 Communication Cost in Parallel Query Evaluation: A Tutorial 2017 PODS 4.1905499e-05
11,839 Logical Aspects of Massively Parallel and Distributed Systems 2016 PODS 4.1905499e-05
11,890 Parallel Evaluation of Multi-Semi-Joins 2016 VLDB 4.1905499e-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.0024217964
70 Hive - A Warehousing Solution Over a Map-Reduce Framework 2009 VLDB 0.00059744625
109 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00048217028
503 Worst-case Optimal Join Algorithms 2012 PODS 0.00021517145
1,114 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013871948
1,312 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.00012650678
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,129 Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources 1997 VLDB 7.5132501e-05
4,855 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8698466e-05
1,674 Scheduling Problems in Parallel Query Optimization 1995 PODS 0.00010939926
1,114 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013871948
9,838 Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems 1981 SIGMOD 4.269862e-05
8,213 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5533861e-05
4,320 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2822407e-05
11,776 Communication Cost in Parallel Query Evaluation: A Tutorial 2017 PODS 4.1905499e-05
2,216 Skew in Parallel Query Processing 2014 PODS 9.2693784e-05
2,856 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0120856e-05