2014 · 79 citations · 30 references
ComputingComputer EngineeringComputer ScienceParallel AlgorithmsParallel ComputingStorage SystemsData LocalityData Locality OptimizationData ParallelismGraph AlgorithmsMemory Hierarchy OptimizationParallel Data StructuresGraph ProcessingGraph Processing SystemsOut-of-core AlgorithmsParallel Graph AlgorithmsPath ComputationRandom Access PerformanceScalable Graph AlgorithmsSequential Access Performance
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.
30
Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik et al. · 2010 · 3.5K citations
Yucheng Low, Danny Bickson, Joseph E. Gonzalez et al. · Proceedings of the VLDB Endowment · 2012 · 1.7K citations
PowerGraph: distributed graph-parallel computation on natural graphs
Joseph E. Gonzalez, Yucheng Low, Haijie Gu et al. · 2012 · 1.5K citations
Amitabha Roy, Ivo Mihailovic, Willy Zwaenepoel · 2013 · 687 citations · Full text