Ex-MATE: Data Intensive Computing with Large Reduction Objects and Its Application to Graph Mining

Map-reduce framework has been widely used as the infrastructure for processing large-scale datasets in various domains. Recent work has shown that an alternate API MATE(Mapreduce with an Alternate API), where a reduction object is explicitly maintained and updated, reduces memory requirements and can significantly improve performance for many applications. However, unlike the original API, support for the alternate API has been restricted to the cases where the reduction object can fit in the memory. This limits the applicability of the MATE approach. Particularly, one emerging class of applications that require support for large reduction objects are the graph mining applications. This paper describes a system, Extended MATE or Ex-MATE, which supports this alternate API with reduction objects of arbitrary sizes. We develop support for managing disk-resident reduction objects and updating them efficiently. We evaluate our system using three graph mining applications and compare its performance to that of PEGASUS, a graph mining system implemented based on the original map-reduce API and its Hadoop implementation. Our results on a cluster with 128 cores show that for all three applications, our system outperforms PEGASUS, by factors ranging between 9 and 35.

I. Introduction

One of the recent developments in high performance and cloud computing has been the emergence of the map-reduce model, originated by Google [8]. Besides the use of mapreduce for real commercial applications, map-reduce has sparked a large volume of research related to APIs for data-intensive computing, their implementations, and application/algorithm studies. Multiple projects have studied improving the API or implementations [13], [24], [30], [32], [37], [22], [29], [25], [23]. At the same time, several studies have evaluated the suitability of the map-reduce model for a variety of applications and on different computing environments [10], [27], [36], [11], [9], [7], [20].