An empirical study of large-scale graph processing with Pregel

In this age of information, data gathering has become a new growing trend. Social networking sites, Internet banking, online communities, all gather and store data concerning their users preferences, interactions or activities. This data is strongly relational and can be represented in the form of graphs where a Vertex represents the subject of the information and Edges represent its interaction or connections with other entities. The purpose of using resources to store these large amounts of information is later processing that will lead to useful result derivation. Hence, we are dealing with graph processing. The large amount of information is leading to distributed graph processing for result calculation within a ?nite time. Distributed large-scale graph processing, is a computational intensive task that entails many challenges such as distributed programming and knowledge of platform speci?c architectural characteristics. One approach that attempts to make the graph processing easy, platform independent and ef?cient, is Google’s Pregel model. Pregel’s computational model is based on an iterative program representation with two distinct entities (Master, Worker), that abstracts distribution related details behind a ?exible, user friendly API. In this project, using C++ and MPI we implement a Pregel clone, called MPI\u882, and we evaluate its performance in the DAS4 cluster of TU Delft using three well studied graph processing algorithms(i.e,Page Rank, BFS, APSP).We conclude that the Pregel system successfully abstracts the graph processing task to a level where platform speci?c information is transparent. Furthermore, we observe that the system scales with the increasing number of computing nodes without introducing extra communication overhead. Finally, we notice that our system is sensitive to platform limitations like memory usage and we propose methods for its future development.Parallel and Distributed SystemsMicroelectronics & Computer EngineeringElectrical Engineering, Mathematics and Computer Scienc