What type of problems can mapreduce solve?

Question

Is there a theoretical analysis available which describes what kind of problems mapreduce can solve?

Answer 1

In Map-Reduce for Machine Learning on Multicore Chu et al describe "algorithms that fit the Statistical Query model can be written in a certain “summation form,” which allows them to be easily parallelized on multicore computers." They specifically implement 10 algorithms including e.g. weighted linear regression, k-Means, Naive Bayes, and SVM, using a map-reduce framework.

The Apache Mahout project has released a recent Hadoop (Java) implementation of some methods based on the ideas from this paper.

Answer 2

For problems requiring processing and generating large data sets. Say running an interest generation query over all accounts a bank hold. Say processing audit data for all transactions that happened in the past year in a bank. The best use case is from Google - generating search index for google search engine.