6
$\begingroup$

I am looking for good resources which have classified and solved typical large scale data processing in MapReduce framework (like graph algorithms, statistics, numerical algorithms ...). Any help is appreciated!

$\endgroup$
  • $\begingroup$ Are you referring to Google's implementation, or the underlying principle? Also, I'd guess there is lots of stuff searchable on the web; why does that not work for you? $\endgroup$ – Raphael Mar 11 '13 at 17:05
  • $\begingroup$ yes I mean the abstract framework. I could'nt find any organized reference/resource, just some random papers! Looking for survey type paper! $\endgroup$ – Reza Mar 11 '13 at 17:46
  • 1
    $\begingroup$ there is this book on design patterns (disclaimer: have not read it) amazon.com/MapReduce-Design-Patterns-Effective-Algorithms/dp/…. from the theory perspective, the models are still shifting somewhat and it's not clear there is enough out there to warrant a survey; in any case, i don't think there is one, but you can check these slides people.cs.umass.edu/~mcgregor/stocworkshop/vassilvitskii.pdf, $\endgroup$ – Sasho Nikolov Mar 11 '13 at 19:56
  • $\begingroup$ Reza, in this case you should sketch the abstract framework as you see it. Unfortunately, the notion is tied to Google's implementation. $\endgroup$ – Raphael Mar 12 '13 at 7:45
  • $\begingroup$ @Raphael: you're right! lets consider Google implementation. $\endgroup$ – Reza Mar 12 '13 at 23:05
5
$\begingroup$

Mapreduce does not seem to have received significant academic attention and/or widespread enthusiasm nor does it seem to have yet been integrated into much of the large previously-existing literature and theory on parallelism. This is partly due to it being relatively new, but there may be other reasons.

One possible angle: this is apparently not widely acknowledged or recognized but MapReduce seems mainly oriented towards & optimized for what are known as embarrassingly parallel problems where the problem space can easily be partitioned into independent parts requiring virtually no intercommunication, i.e. the "map" step. (this is partly the basis of some criticism of the simplicity of the model as in the Wikipedia article.)

The "reduce" step is a communication-heavy step of merging/combining/aggregating the separate results into a combined structure. [1] are slides on the background & structure of typical embarrassingly parallel problems, which classic examples are:

Another angle is that MapReduce has some similarities to the "master-slave" design pattern where the "master" distributes jobs and also handles collecting the results, and some surveys on "master-slave" decomposition of parallel problems may be available.

Embarrassingly parallel problems are also naturally "finely granular" and Mapreduce seems especially suited to "fine-grained" parallelism problems (such that the "fine grains" can be highly distributed over many computing machines). "Fine-grained" parallelism is possibly not studied as much from an academic point of view because its intrinsically theoretically less problematic.

Another angle: it's similar to "Bulk Synchronous Parallel" [4]. The reduce step is similar to "barrier synchronization".

A survey from 2006 by academic parallelism experts [2] that was meant to be very comprehensive and forward-looking at the time identified 7 widespread "dwarves" or basic parallelism structures found in algorithms (Section 3.2). Conspicuously and surprisingly, none have a MapReduce-like structure; i.e. MapReduce type problems are absent from the survey (but note Monte Carlo methods are one of the "dwarves" and is again regarded as embarrassingly parallel).

This would also tend to support the view that MapReduce is a kind of "toy" parallelism model. However! that point is not meant to detract from its widespread usefulness in many applications. Particularly with parallelism there can be great value in simpler models that avoid complexity and thereby also various pitfalls.

[1] Embarrassingly parallel overview

[2] The landscape of parallel computing: the view from Berkeley

[3] Current parallel models for computation tcs.se

[4] Is the mapreduce framework a type of BSP tcs.se

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.