Iterative MapReduce for Large Scale Machine Learning

Large datasets (“Big Data”) are becoming ubiquitous be-cause the potential value in deriving insights from data, across a wide range of business and scientific applications, is increasingly recognized. The data growth has been accom-panied by rapid adoption of large, elastic, multi-tenanted computing clusters (“compute clouds”), leading to a virtu-ous cycle: the scalability of cloud computing makes it possi-ble to analyze ever larger datasets, and the proliferation of Big Data leads to further adoption of cloud computing. In particular, machine learning—one of the foundational dis-ciplines for data analysis, summarization and inference—on Big Data has become routine at most organizations that op-erate large clouds, usually based on systems such as Hadoop that support the MapReduce programming paradigm. It is now widely recognized that while MapReduce is highly scal-able, it suffers from a critical weakness for machine learn-ing: it does not support iteration. Consequently, one has to program around this limitation, leading to fragile, inef-ficient code. Further, reliance on the programmer is inher-ently flawed in a multi-tenanted cloud environment, since the programmer does not have visibility into the state of the system when his or her program executes. Prior work has sought to address this problem by either developing spe-cialized systems aimed at stylized applications, or by aug-menting MapReduce with ad hoc support for saving state across iterations (driven by an external loop). In this paper, we advocate support for looping as a first-class construct, and propose an extension of the MapReduce programming paradigm called Iterative MapReduce. We then develop an optimizer for a class of Iterative MapReduce programs that cover most machine learning techniques, provide theoretical justifications for the key optimization steps, and empirically demonstrate that system-optimized programs for significant machine learning tasks are competitive with state-of-the-art specialized solutions