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.5716049e-05
Overall Rank: 7,259 | 51.20%
DOI: 10.1145/3183713.3183728

Incoming Non-self Citations Over Time

Authors

1. Rundong Li (Northeastern University)
2. Mirek Riedewald (Northeastern University)
3. Xinyan Deng (Northeastern University)

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,721	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6981399e-05
7,923	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4260253e-05
8,550	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.3168829e-05
12,167	Block as a Value for SQL over NoSQL	2019	VLDB	4.9793485e-05

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.00028522117
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023175253
360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020009936
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
753	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB	0.00014237583
799	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00013889081
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013583955
865	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.0001338765
920	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013081835
1,212	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00011513842
1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011330673
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011152286
1,351	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00010934347
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
1,670	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9318041e-05
1,995	Track Join: Distributed Joins with Minimal Network Traffic	2014	SIGMOD	9.2169073e-05
2,176	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	8.9159001e-05
2,577	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	8.2738285e-05
2,948	Distributed Data Deduplication	2016	VLDB	7.8230494e-05
2,953	Scalable and Adaptive Online Joins	2014	VLDB	7.8137255e-05
3,636	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.1471007e-05
3,691	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD	7.0935524e-05
3,967	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.8905715e-05
4,533	AdaptDB: Adaptive Partitioning for Distributed Joins	2017	VLDB	6.5565658e-05
5,666	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	6.0462129e-05
6,137	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.8736299e-05

Semantically Similar Papers

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