Fast Iterative Graph Computation: A Path Centric Approach

摘要

Large scale graph processing represents an interesting challenge due to the lack of locality. This paper presents Path Graph for improving iterative graph computation on graphs with billions of edges. Our system design has three unique features: First, we model a large graph using a collection of tree-based partitions and use an path-centric computation rather than vertex-centric or edge-centric computation. Our parallel computation model significantly improves the memory and disk locality for performing iterative computation algorithms. Second, we design a compact storage that further maximize sequential access and minimize random access on storage media. Third, we implement the path-centric computation model by using a scatter/gather programming model, which parallels the iterative computation at partition tree level and performs sequential updates for vertices in each partition tree. The experimental results show that the path-centric approach outperforms vertex centric and edge-centric systems on a number of graph algorithms for both in-memory and out-of-core graphs.