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: 10694
Venue: VLDB
Year: 2013
Pagerank: 0.00012661651
Overall Rank: 1,308 | 90.91%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
2,162	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	9.3964337e-05
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.2717602e-05
2,336	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	9.0109891e-05
2,997	Subgraph Matching: on Compression and Computation	2018	VLDB	7.7559339e-05
3,129	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.5008242e-05
4,021	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5225987e-05
4,689	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	5.9980099e-05
10,925	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.1945683e-05
11,768	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1945683e-05
11,831	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.1945683e-05
11,835	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.1945683e-05
11,882	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.1945683e-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
447	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00022900171
1,074	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014260096
1,110	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013968198
1,334	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.0001250413
1,440	Provenance for Generalized Map and Reduce Workflows	2011	CIDR	0.00011961469
1,825	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	0.00010401739
4,603	Inspector Gadget: A Framework for Custom Monitoring and Debugging of Distributed Dataflows	2011	VLDB	6.0554018e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
868	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB	0.00015789681
11,630	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	4.1945683e-05
10,925	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.1945683e-05
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
3,129	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.5008242e-05
11,976	Anti-Combining for MapReduce	2014	SIGMOD	4.1945683e-05
13,380	Job Scheduling with Minimizing Data Communication Costs	2015	SIGMOD	-
1,615	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00011132319
3,703	Multi-Query Optimization in MapReduce Framework	2014	VLDB	6.8289978e-05
2,674	Minimal MapReduce Algorithms	2013	SIGMOD	8.3328645e-05