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: 10695
Venue: VLDB
Year: 2013
Pagerank: 0.00012650678
Overall Rank: 1,312 | 90.89%
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.00012118832
1,948	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9938634e-05
2,172	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	9.37776e-05
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
2,219	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.2653868e-05
2,332	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	9.0173968e-05
2,963	Subgraph Matching: on Compression and Computation	2018	VLDB	7.8061004e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
4,026	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5166769e-05
4,641	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.0215749e-05
10,929	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.1905499e-05
11,776	Communication Cost in Parallel Query Evaluation: A Tutorial	2017	PODS	4.1905499e-05
11,839	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.1905499e-05
11,843	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.1905499e-05
11,890	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.1905499e-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
442	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00023095823
1,073	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014255717
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
1,339	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00012492978
1,441	Provenance for Generalized Map and Reduce Workflows	2011	CIDR	0.00011950114
1,826	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	0.00010392071
4,604	Inspector Gadget: A Framework for Custom Monitoring and Debugging of Distributed Dataflows	2011	VLDB	6.0497655e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
866	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB	0.00015771189
11,634	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	4.1905499e-05
10,929	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.1905499e-05
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
11,984	Anti-Combining for MapReduce	2014	SIGMOD	4.1905499e-05
13,393	Job Scheduling with Minimizing Data Communication Costs	2015	SIGMOD	-
1,615	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00011137225
3,709	Multi-Query Optimization in MapReduce Framework	2014	VLDB	6.8211506e-05
2,714	Minimal MapReduce Algorithms	2013	SIGMOD	8.2426646e-05