Stanford InfoLab Publication Server

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

Afrati, Foto and Das Sarma, Anish and Salihoglu, Semih and Ullman, Jeffrey D. (2013) Upper and Lower Bounds on the Cost of a Map-Reduce Computation. In: international Conference on Very Large Databases, 26-30 August 2013, Riva del Garda, Italy.


PDF (Upper and Lower Bounds on the Cost of a Map-Reduce Computation) - Published Version


In this paper we study the tradeoff between parallelism and commu- nication cost in a map-reduce computation. For any problem that is not “embarrassingly parallel,” the finer we partition the work of the reducers so that more parallelism can be extracted, the greater will be the total communication between mappers and reducers. We in- troduce a model of problems that can be solved in a single round of map-reduce computation. This model enables a generic recipe for discovering lower bounds on communication cost as a function of the maximum number of inputs that can be assigned to one re- ducer. We use the model to analyze the tradeoff for three problems: finding pairs of strings at Hamming distance d, finding triangles and other patterns in a larger graph, and matrix multiplication. For finding strings of Hamming distance 1, we have upper and lower bounds that match exactly. For triangles and many other graphs, we have upper and lower bounds that are the same to within a constant factor. For the problem of matrix multiplication, we have matching upper and lower bounds for one-round map-reduce algorithms. We are also able to explore two-round map-reduce algorithms for ma- trix multiplication and show that these never have more communi- cation, for a given reducer size, than the best one-round algorithm, and often have significantly less.

Item Type:Conference or Workshop Item (Paper)
ID Code:1083
Deposited By:Semih Salihoglu
Deposited On:11 Dec 2013 19:00
Last Modified:11 Dec 2013 19:00

Download statistics

Repository Staff Only: item control page