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.2693784e-05
Overall Rank
2,216 | 84.61%
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,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,856 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0120856e-05
3,476 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.0560383e-05
3,526 Distributed Data Deduplication 2016 VLDB 7.0056559e-05
3,831 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 6.7146681e-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,618 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 4.9864636e-05
6,691 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 4.9573939e-05
7,117 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 4.8205884e-05
7,154 Submodularity of Distributed Join Computation 2018 SIGMOD 4.8107765e-05
7,842 NOCAP: Near-Optimal Correlation-Aware Partitioning Joins 2023 SIGMOD 4.6336361e-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
8,962 Adaptive Quotient Filters 2024 SIGMOD 4.4168718e-05
9,335 Parallel Query Processing: To Separate Communication from Computation 2022 SIGMOD 4.351469e-05
9,692 ROME: Robust Query Optimization via Parallel Multi-Plan Execution 2024 SIGMOD 4.2986161e-05
9,743 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2856385e-05
10,553 Jodes: Efficient Oblivious Join in the Distributed Setting 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
10,984 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1905499e-05
11,439 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.1905499e-05
11,440 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS 4.1905499e-05
11,483 Vertex-centric Parallel Computation of SQL Queries 2021 SIGMOD 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,843 An Efficient MapReduce Cube Algorithm for Varied Data Distributions 2016 SIGMOD 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
539 Shark: SQL and Rich Analytics at Scale 2013 SIGMOD 0.00020615453
852 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00015896035
1,312 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.00012650678
1,411 Communication Steps for Parallel Query Processing 2013 PODS 0.00012118832
1,919 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010097452
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,675 Adaptive Parallel Aggregation Algorithms 1995 SIGMOD 0.00010937908
8,213 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5533861e-05
1,919 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010097452
852 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00015896035
1,355 Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning 1991 VLDB 0.00012417228
1,114 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013871948
11,776 Communication Cost in Parallel Query Evaluation: A Tutorial 2017 PODS 4.1905499e-05
1,411 Communication Steps for Parallel Query Processing 2013 PODS 0.00012118832
548 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00020369531
2,856 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0120856e-05