Scalable machine learning algorithms seem like the buzz these days. Every company is handling nothing short of big data. Is there a textbook which discusses what machine learning algorithms can be scaled using parallel architectures like Map-Reduce, and which algorithms cannot? Or some relevant papers?
Vowpal Wabbit, a very fast machine learning program focused on online gradient descent learning, can be used with Hadoop: http://arxiv.org/abs/1110.4198 Though, I've never used it this way. If I understand it correctly, it really only uses Hadoop for reliability and providing the data to the Vowpal Wabbit processes. It uses something like MPI's AllReduce to do most of the communication.
As Jimmy Lin and Chris Dyer point out in the first chapter in their book on Data-Intensive Text Mining with MapReduce, at large data scales, the performance of different algorithms converge such that performance differences virtually disappear. This means that given a large enough data set, the algorithm you'd want to use is the one that is computationally less expensive. It's only at smaller data scales that the performance differences between algorithms matter.
That being said, their book (linked above) and Mining of Massive Datasets by Anand Rajaraman, Jure Leskovec, and Jeffrey D. Ullman are probably two books you'll want to check out as well, especially as they're directly concerned with MapReduce for data mining purposes.
If you have access to a Hadoop cluster, I'd give Spark a look. https://spark.apache.org/
No one has mentioned the following paper - http://papers.nips.cc/paper/3150-map-reduce-for-machine-learning-on-multicore.pdf (Andrew Ng is one of the authors)
The paper itself is for multi-core machines, but it is essentially about recasting machine learning problems so that they fit the map-reduce pattern, and can be used for a cluster of computers. (for seeing why that is not a good idea in general, you may want to read this paper - http://arxiv.org/pdf/1006.4990v1.pdf . It has a good overview).
Scaling Up Machine Learning: parallel and distributed approaches is a great book by John Langford et. al. that discusses parallel implementations of supervised and unsupervised algorithms. It talks about MapReduce, decision tree ensembles, parallel K-means, parallel SVM, belief propagation, and AD-LDA.