A model of computation for MapReduce

By Howard J. Karloff, Siddharth Suri, Sergei Vassilvitskii. ACM-SIAM Symposium on Discrete Algorithms, 2010

699 citations recorded by the source corpus.

In recent years the MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing data on terabyte and petabyte scales. Used daily at companies such as Yahoo!, Google, Amazon, and Facebook, and adopted more recently by several universities, it allows for easy parallelization of data intensive computations over many machines. One key feature of MapReduce that differentiates it from previous models of parallel computation is that it interleaves sequential and parallel computation. We propose a model of efficient computation using the MapReduce paradigm. Since MapReduce is designed for computations over massive data sets, our model limits the number of machines and the memory per machine to be substantially sublinear in the size of the input. On the other hand, we place very loose restrictions on the computational power of of any individual machine---our model allows each machine to perform sequential computations in time polynomial in the size of the original input. We compare MapReduce to the PRAM model of computation. We prove a simulation lemma showing that a large class of PRAM algorithms can be efficiently simulated via MapReduce. The strength of MapReduce, however, lies in the fact that it uses both sequential and parallel computation. We demonstrate how algorithms can take advantage of this fact to compute an MST of a dense graph in only two rounds, as opposed to Ω(log(n)) rounds needed in the standard PRAM model. We show how to evaluate a wide class of functions using the MapReduce framework. We conclude by applying this result to show how to compute some basic algorithmic problems such as undirected s-t connectivity in the MapReduce framework.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Systems

View Paper: https://www.semanticscholar.org/paper/da3df6274c1758bc5beaf72216e230a4717272c9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Systems

Citations in the corpus

Counting triangles and the curse of the last reducer (2011, methodology): “We omit this technicality for the sake of clarity and refer the interested reader to [11] for exact details.”
Scalable K-Means++ (2012, methodology): “[24] introduced a model of computation for MapReduce, which has since been used to reason about algorithms for set cover [11], graph problems [27], and other clustering formulations [15].”
Book Reviews: Data-Intensive Text Processing with MapReduce by Jimmy Lin and Chris Dyer (2010, background): “[82] demonstrated that a large class of PRAM algorithms can be efficiently simulated via MapReduce.”
Max-cover in map-reduce (2010, background): “There have been some attempts to abstractly model Map-Reduce computations; see [13, 19].”
Connected Components at Scale via Local Contractions (2018, methodology): “CREW PRAM algorithms can be simulated in MapReduce using the result of [KSV10], but they would require O ( n 2 ) communication per MapReduce iteration on a star graph.”
Apache Spark (2016, methodology): “Recent theoretical work has formalized this type of emulation by showing that MapReduce can simulate many computations in the Parallel Random Access Machine model.(8) Repeated MapReduce is also equivalent to the Bulk Synchronous Parallel model.”