DBScholar

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
h50e4f9cd6b195ecc
Venue
SIGMOD
Year
2018
Pagerank
5.5689674e-05
Overall Rank
7,266 | 51.17%
DOI
10.1145/3183713.3183728

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{li_sigmod18,
        title = {{Submodularity of Distributed Join Computation}},
        author = {Li, Rundong and Riedewald, Mirek and Deng, Xinyan},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3183728},
        url = {https://dl.acm.org/doi/10.1145/3183713.3183728},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
6,725 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 5.6954425e-05
7,927 NOCAP: Near-Optimal Correlation-Aware Partitioning Joins 2023 SIGMOD 5.4234567e-05
8,557 Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale 2020 CIDR 5.314366e-05
12,173 Block as a Value for SQL over NoSQL 2019 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

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
156 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00028509887
249 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD 0.0002316492
360 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00020001237
490 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00017433989
754 Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs 2011 VLDB 0.00014231311
799 A Comparison of Join Algorithms for Log Processing in MapReduce 2010 SIGMOD 0.00013882649
833 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00013577649
866 Processing Theta-Joins using MapReduce* 2011 SIGMOD 0.00013381756
920 Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines 1990 VLDB 0.00013075939
1,213 Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC) 1990 VLDB 0.00011508483
1,256 Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning 1991 VLDB 0.00011325515
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011147959
1,351 SkewTune: Mitigating Skew in MapReduce Applications 2012 SIGMOD 0.00010929229
1,482 Skew in Parallel Query Processing 2014 PODS 0.00010534147
1,671 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 9.9271979e-05
1,997 Track Join: Distributed Joins with Minimal Network Traffic 2014 SIGMOD 9.2126022e-05
2,175 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 8.918268e-05
2,577 ClusterJoin: A Similarity Joins Framework using Map-Reduce 2014 VLDB 8.2699584e-05
2,949 Distributed Data Deduplication 2016 VLDB 7.8193962e-05
2,956 Scalable and Adaptive Online Joins 2014 VLDB 7.8100535e-05
3,637 Advanced Join Strategies for Large-Scale Distributed Computation 2014 VLDB 7.1437959e-05
3,694 Exploiting MapReduce-based Similarity Joins 2012 SIGMOD 7.0902387e-05
3,969 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8874168e-05
4,534 AdaptDB: Adaptive Partitioning for Distributed Joins 2017 VLDB 6.5535468e-05
5,668 Skew-Aware Join Optimization for Array Databases 2015 SIGMOD 6.0433507e-05
6,140 Scaling Similarity Joins over Tree-Structured Data 2015 VLDB 5.8708494e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,280 Fast and Effective Distribution-Key Recommendation for Amazon Redshift 2020 VLDB
2 12,304 Runtime Optimization of Join Location in Parallel Data Management Systems 2017 VLDB
3 3,969 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB
4 7,438 Efficient Computation of Quantiles over Joins 2023 PODS
5 2,225 Shared Workload Optimization 2014 VLDB
6 9,897 Sharing Aggregate Computation for Distributed Queries 2007 SIGMOD
7 4,757 Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor 1991 VLDB
8 1,252 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB
9 12,389 Let's Rethink Join Optimization in Distributed Systems 2015 CIDR
10 6,725 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD