2013 Poster Sessions : GPS: A Graph Processing System

Student Name : Semih Salihoglu
Advisor : Jennifer Widom
Research Areas: Computer Systems
Abstract:
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. GPS is similar to Google's proprietary Pregel system [MAB+11], with three additional properties: (1) An extended API to express serial computation. (2) Dynamic repartitioning of the input graph across compute nodes during computation to lower communication. (3) Partitioning the adjacency lists of high-degree vertices to lower communication. In distributed graph processing systems like GPS and Pregel, graph partitioning is the problem of deciding which vertices of the graph are assigned to which compute nodes. In addition to presenting the GPS system itself, we describe how we have used GPS to study the e ects of di erent graph partitioning schemes. We present our experiments on the performance of GPS under di erent static partitioning schemes|assigning vertices to workers intelligently" before the computation starts|and with GPS's dynamic repartitioning feature, which reassigns vertices to di erent compute nodes during the computation by observing their message sending patterns.

Bio:
I am a 4th year Ph.D. student in Computer Science advised by Prof. Jennifer Widom. My main research topic is on systems for distributed graph computations. I also work theoretical topics about the MapReduce system.