DISTINGER: A distributed graph data structure for massive dynamic graph processing

Abstract

Large and dynamic graphs with streaming updates have been gaining traction recently, along with the need for enabling graph analytics in a commodity cluster instead of a high-performance computing facility. Surprisingly, there is a lack of study on scaling out graph data structures to represent sparse dynamic graphs in a commodity cluster, and even the latest work [1] based upon the most common in-memory graph representation CSR [2] is a single-machine case. In this paper we present DISTINGER, a distributed graph representation that handles massive graph analytics with streaming updates. DISTINGER successfully extends a scale-up design to a scale-out graph data structure while maintains its efficiency and scalability. We implement our design and algorithms as a prototype, and compare it to single-site STINGER and state-of-art graph systems. Our experimental evaluation in a real cluster shows that DISTINGER can handle larger graphs than STINGER, and perform graph tasks (PageRank and edge updates) more efficiently than GraphLab and Giraph.