Space-Round Tradeoffs for MapReduce Computations

Details Space-Round Tradeoffs for MapReduce Computations Space-Round Tradeoffs for MapReduce Computations

2011-11-09

arxiv.org/abs/1111.2228v1

Computer Science

Data Structures and Algorithms

Scientific paper

This work explores fundamental modeling and algorithmic issues arising in the well-established MapReduce framework. First, we formally specify a computational model for MapReduce which captures the functional flavor of the paradigm by allowing for a flexible use of parallelism. Indeed, the model diverges from a traditional processor-centric view by featuring parameters which embody only global and local memory constraints, thus favoring a more data-centric view. Second, we apply the model to the fundamental computation task of matrix multiplication presenting upper and lower bounds for both dense and sparse matrix multiplication, which highlight interesting tradeoffs between space and round complexity. Finally, building on the matrix multiplication results, we derive further space-round tradeoffs on matrix inversion and matching.

Affiliated with

Also associated with

No associations

Rating

Space-Round Tradeoffs for MapReduce Computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Space-Round Tradeoffs for MapReduce Computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-Round Tradeoffs for MapReduce Computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-42839