Select Lab Publications


PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs (2012)

By: Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin

Abstract: Large-scale graph-structured computation is central to tasks ranging from targeted advertising to natural language processing and has led to the development of several graph-parallel abstractions including Pregel and GraphLab. However, the natural graphs commonly found in the real-world have highly skewed power-law degree distributions, which challenge the assumptions made by these abstractions, limiting performance and scalability.

In this paper, we characterize the challenges of computation on natural graphs in the context of existing graph-parallel abstractions. We then introduce the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges. Leveraging the PowerGraph abstraction we introduce a new approach to distributed graph placement and representation that exploits the structure of power-law graphs. We provide a detailed analysis and experimental evaluation comparing PowerGraph to two popular graph-parallel systems. Finally, we describe three different implementation strategies for PowerGraph and discuss their relative merits with empirical evaluations on large-scale real-world problems demonstrating order of magnitude gains.

Download Information
Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin (2012). "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs." Proceedings of the 10th USENIX Symposium onOperating Systems Design and Implementation (OSDI '12). pdf            
BibTeX citation

@inproceedings{Gonzalez+al:osdi2012,
title = {PowerGraph: Distributed Graph-Parallel Computation
on Natural Graphs},
author = {Joseph E. Gonzalez and Yucheng Low and Haijie Gu and Danny Bickson and Carlos Guestrin},
booktitle = {Proceedings of the 10th {USENIX} {S}ymposium on
{O}perating {S}ystems {D}esign and {I}mplementation
({OSDI} '12)},
month = {October},
year = {2012},
address = {Hollywood},
wwwfilebase = {osdi2012-gonzalez-low-gu-bickson-guestrin},
wwwtopic = {Parallel Learning}
}



full list