Back to papers
Submodularity of Distributed Join Computation
Summary: Distributed equi-join under join-attribute skew; fine-grained partitioning trades input duplication for reduced load variance. Minimizing load variance under an average constraint is a monotone submodular knapsack problem, enabling near-optimal greedy solutions; works for general load models and deterministic assignment with experiments.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 5449
- Venue
- SIGMOD
- Year
- 2018
- Pagerank
- 4.8107765e-05
- Overall Rank
- 7,154 | 50.28%
- DOI
-
10.1145/3183713.3183728
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 26 of 26 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 77 |
Multiprocessor Hash-Based Join Algorithms |
1985 |
VLDB |
0.00056488357 |
| 230 |
A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment |
1989 |
SIGMOD |
0.00032145125 |
| 442 |
Efficient Parallel Set-Similarity Joins Using MapReduce |
2010 |
SIGMOD |
0.00023095823 |
| 548 |
Practical Skew Handling in Parallel Joins |
1992 |
VLDB |
0.00020369531 |
| 852 |
A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins |
1991 |
VLDB |
0.00015896035 |
| 866 |
Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs |
2011 |
VLDB |
0.00015771189 |
| 962 |
A Comparison of Join Algorithms for Log Processing in MapReduce |
2010 |
SIGMOD |
0.00015003834 |
| 1,063 |
Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines |
1990 |
VLDB |
0.00014352292 |
| 1,073 |
Processing Theta-Joins using MapReduce* |
2011 |
SIGMOD |
0.00014255717 |
| 1,219 |
Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC) |
1990 |
VLDB |
0.00013215689 |
| 1,339 |
SkewTune: Mitigating Skew in MapReduce Applications |
2012 |
SIGMOD |
0.00012492978 |
| 1,355 |
Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning |
1991 |
VLDB |
0.00012417228 |
| 1,919 |
Handling Data Skew in Parallel Joins in Shared-Nothing Systems |
2008 |
SIGMOD |
0.00010097452 |
| 1,927 |
Efficient Processing of k Nearest Neighbor Joins using MapReduce |
2012 |
VLDB |
0.00010062395 |
| 1,938 |
From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System |
2015 |
SIGMOD |
0.00010025547 |
| 2,216 |
Skew in Parallel Query Processing |
2014 |
PODS |
9.2693784e-05 |
| 2,518 |
Track Join: Distributed Joins with Minimal Network Traffic |
2014 |
SIGMOD |
8.6052941e-05 |
| 3,139 |
ClusterJoin: A Similarity Joins Framework using Map-Reduce |
2014 |
VLDB |
7.4915127e-05 |
| 3,384 |
Scalable and Adaptive Online Joins |
2014 |
VLDB |
7.153329e-05 |
| 3,526 |
Distributed Data Deduplication |
2016 |
VLDB |
7.0056559e-05 |
| 3,896 |
Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing |
1996 |
VLDB |
6.6526869e-05 |
| 4,128 |
Advanced Join Strategies for Large-Scale Distributed Computation |
2014 |
VLDB |
6.4214449e-05 |
| 4,130 |
Exploiting MapReduce-based Similarity Joins |
2012 |
SIGMOD |
6.4205218e-05 |
| 5,116 |
AdaptDB: Adaptive Partitioning for Distributed Joins |
2017 |
VLDB |
5.6805476e-05 |
| 5,961 |
Skew-Aware Join Optimization for Array Databases |
2015 |
SIGMOD |
5.2510172e-05 |
| 6,240 |
Scaling Similarity Joins over Tree-Structured Data |
2015 |
VLDB |
5.1362097e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 6,655 |
Fast and Effective Distribution-Key Recommendation for Amazon Redshift |
2020 |
VLDB |
4.9693109e-05 |
| 11,805 |
Runtime Optimization of Join Location in Parallel Data Management Systems |
2017 |
VLDB |
4.1905499e-05 |
| 3,896 |
Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing |
1996 |
VLDB |
6.6526869e-05 |
| 8,065 |
Efficient Computation of Quantiles over Joins |
2023 |
PODS |
4.5899218e-05 |
| 2,928 |
Shared Workload Optimization |
2014 |
VLDB |
7.881485e-05 |
| 9,582 |
Sharing Aggregate Computation for Distributed Queries |
2007 |
SIGMOD |
4.3185789e-05 |
| 4,398 |
Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor |
1991 |
VLDB |
6.2137073e-05 |
| 1,948 |
Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows |
2018 |
VLDB |
9.9938634e-05 |
| 11,898 |
Let's Rethink Join Optimization in Distributed Systems |
2015 |
CIDR |
4.1905499e-05 |
| 6,618 |
Near-Optimal Distributed Band-Joins through Recursive Partitioning |
2020 |
SIGMOD |
4.9864636e-05 |