On the Efficiency and Programmability of Large Graph Processing in the Cloud

Abstract

As the study of large graphs over hundreds of gigabytes becomes increasingly popular in cloud computing, efficiency and programmability of large graph processing tasks challenge existing tools. The inherent random access pattern on the graph generates significant amount of network traffic. Moreover, implementing custom logics on the unstructured data in a distributed manner is often a pain for graph analysts. To address these challenges, we develop Surfer, a large graph processing engine in the cloud. Surfer resolves the bottleneck of network traffic with graph partitioning, which is specifically adapted to the network environment of the cloud. To improve the programmability, Surfer provides two basic primitives as building blocks for high-level applications – MapReduce and propagation. Surfer implements both primitives with automatic optimizations on the partitioned graph. We implement and evaluate Surfer with common graph applications on the MSN social network and the synthetic graphs with over 100GB each. Our experimental results demonstrate the efficiency and programmability of Surfer.