PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

05.06.2013
Beteiligte : Joseph Gonzalez (AMPLab, UC Berkeley)
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 talk we will characterize the challenges of distributed computation on natural graphs in the context of existing graph-parallel abstractions. I will then introduce the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges. Leveraging the PowerGraph abstraction, I will then introduce a new approach to distributed graph placement and representation that exploits the structure of power-law graphs. I will discuss the performance of these new techniques on large-scale real-world problems demonstrating order of magnitude gains. Finally, I will present ongoing work on expressing graph computation within classical database systems.