Database Paper Browser

Back to papers

Skew in Parallel Query Processing

Summary: Tight one-round communication bounds for computing conjunctive queries on p servers characterized by fractional edge packings when only relation cardinalities are known (skew-free), matching up to polylog p. For skewed data with known heavy hitters/frequencies, matching upper/lower bounds via packings of residual queries obtained by fixing heavy hitters, with information-theoretic bit lower bounds even under unbounded local computation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1634
Venue
PODS
Year
2014
Pagerank
9.2771827e-05
Overall Rank
2,212 | 84.62%
DOI
10.1145/2594538.2594558

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 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,849 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0195487e-05
3,474 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.0625972e-05
3,528 Distributed Data Deduplication 2016 VLDB 7.0066139e-05
3,833 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 6.7173578e-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,619 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 4.9910152e-05
6,690 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 4.9621556e-05
7,122 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 4.8252188e-05
7,153 Submodularity of Distributed Join Computation 2018 SIGMOD 4.8153963e-05
7,836 NOCAP: Near-Optimal Correlation-Aware Partitioning Joins 2023 SIGMOD 4.6380835e-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
8,957 Adaptive Quotient Filters 2024 SIGMOD 4.4211093e-05
9,330 Parallel Query Processing: To Separate Communication from Computation 2022 SIGMOD 4.3556432e-05
9,693 ROME: Robust Query Optimization via Parallel Multi-Plan Execution 2024 SIGMOD 4.3027391e-05
9,744 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2897489e-05
10,544 Jodes: Efficient Oblivious Join in the Distributed Setting 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
10,981 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1945683e-05
11,436 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.1945683e-05
11,437 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS 4.1945683e-05
11,479 Vertex-centric Parallel Computation of SQL Queries 2021 SIGMOD 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,835 An Efficient MapReduce Cube Algorithm for Varied Data Distributions 2016 SIGMOD 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
542 Shark: SQL and Rich Analytics at Scale 2013 SIGMOD 0.00020595648
861 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00015848554
1,308 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.00012661651
1,411 Communication Steps for Parallel Query Processing 2013 PODS 0.0001212565
1,915 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010104123
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,674 Adaptive Parallel Aggregation Algorithms 1995 SIGMOD 0.0001094787
8,215 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5577562e-05
1,915 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010104123
861 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00015848554
1,365 Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning 1991 VLDB 0.00012368421
1,110 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013968198
11,768 Communication Cost in Parallel Query Evaluation: A Tutorial 2017 PODS 4.1945683e-05
1,411 Communication Steps for Parallel Query Processing 2013 PODS 0.0001212565
588 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00019604754
2,849 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0195487e-05