Stanford InfoLab Publication Server

GPS: A Graph Processing System

Salihoglu, Semih and Widom, Jennifer (2013) GPS: A Graph Processing System. In: Scientific and Statistical Database Management, Baltimore, Maryland.


[img]PDF - Accepted Version


GPS (for Graph Processing System) is a complete open-source system we developed for scalable, fault-tolerant, and easy-to-program execution of algorithms on extremely large graphs. This paper serves the dual role of describing the GPS system, and presenting techniques and experimental results for graph partitioning in distributed graph-processing systems like GPS. GPS is similar to Google's proprietary Pregel system, with three new features: (1) an extended API to make global computations more easily expressed and more efficient; (2) a dynamic repartitioning scheme that reassigns vertices to different workers during the computation based on messaging patterns; and (3) an optimization that distributes adjacency lists of high-degree vertices across all compute nodes to improve performance. In addition to presenting the implementation of GPS and its novel features, we also experiment with the performance effects of static graph partitioning schemes, i.e., assigning vertices to compute nodes "intelligently" before computation begins.

Item Type:Conference or Workshop Item (Paper)
ID Code:1039
Deposited By:Semih Salihoglu
Deposited On:25 Apr 2012 12:52
Last Modified:06 May 2013 15:20

Download statistics

Repository Staff Only: item control page