Upper and Lower Bounds on the Cost of a Map-Reduce Computation

Summary: Presents a single-round MapReduce model with a generic lower-bound recipe tying reducer fan-in to total communication for non-embarrassingly parallel tasks. Applies it to Hamming distance 1, triangles, and matrix multiplication, delivering tight upper/lower bounds and showing two-round schemes cannot beat the best one-round bound for a fixed reducer size. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10882
Venue: VLDB
Year: 2013
Pagerank: 0.00010527649
Overall Rank: 1,514 | 89.62%
DOI: 10.14778/2535573.2535574

Incoming Non-self Citations Over Time

Authors

1. Foto N. Afrati (National Technical University of Athens)
2. Anish Das Sarma (Google)
3. Semih Salihoglu (Stanford University)
4. Jeffrey D. Ullman (Stanford University)

BibTeX Citation

@article{afrati_vldb13,
        title = {{Upper and Lower Bounds on the Cost of a Map-Reduce Computation}},
        author = {Afrati, Foto N. and Sarma, Anish Das and Salihoglu, Semih and Ullman, Jeffrey D.},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {4},
        pages = {277--288},
        doi = {10.14778/2535573.2535574},
        url = {https://doi.org/10.14778/2535573.2535574},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011504088
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,552	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010379532
2,183	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.0066814e-05
2,187	Subgraph Matching: on Compression and Computation	2018	VLDB	8.9966682e-05
2,295	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	8.7932254e-05
3,008	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.8578871e-05
3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.2030591e-05
4,244	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.8062787e-05
11,145	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	5.093636e-05
11,973	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	5.093636e-05
12,032	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	5.093636e-05
12,036	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	5.093636e-05
12,082	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020303289
843	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013666161
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,319	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00011175005
1,366	Provenance for Generalized Map and Reduce Workflows	2011	CIDR	0.00011016972
2,131	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	9.1242116e-05
4,693	Inspector Gadget: A Framework for Custom Monitoring and Debugging of Distributed Dataflows	2011	VLDB	6.560102e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	735	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB
2	11,145	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS
3	11,825	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB
4	1,448	Skew in Parallel Query Processing	2014	PODS
5	3,008	Scalable Big Graph Processing in MapReduce	2014	SIGMOD
6	12,174	Anti-Combining for MapReduce	2014	SIGMOD
7	13,581	Job Scheduling with Minimizing Data Communication Costs	2015	SIGMOD
8	1,436	The Performance of MapReduce: An In-depth Study	2010	VLDB
9	3,163	Multi-Query Optimization in MapReduce Framework	2014	VLDB
10	2,539	Minimal MapReduce Algorithms	2013	SIGMOD