GRAPE: Parallelizing Sequential Graph Computations

Wenfei Fan, Jingbo Xu, Yinghui Wu, Wenyuan Yu, Jiaxin Jiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

This paper presents GRAPE, a parallel system for graph computations. GRAPE differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole. Underlying GRAPE are a simple programming model and a principled approach, based on partial evaluation and incremental computation. We show that sequential graph algorithms can be “plugged into” GRAPE with minor changes, and get parallelized. As long as the sequential algorithms are correct, their GRAPE parallelization guarantees to terminate with correct answers under a monotonic condition. Moreover, we show that algorithms in MapReduce, BSP and PRAM can be optimally simulated on GRAPE. In addition to the ease of programming, we experimentally verify that GRAPE achieves comparable performance to the state-of-the-art graph systems, using real-life and synthetic graphs.
Original languageEnglish
Title of host publicationProceedings of the 43rd International Conference on Very Large Data Bases
PublisherVery Large Data Base Endowment Inc.
Number of pages4
Publication statusPublished - 31 Aug 2017
Event43rd International Conference on Very Large Data Bases - Technical University of Munich, Munich, Germany
Duration: 28 Aug 20171 Sept 2017

Publication series

NameProceedings of the VLDB Endowment
ISSN (Print)2150-8097


Conference43rd International Conference on Very Large Data Bases
Abbreviated titleVLDB 2017
Internet address


Dive into the research topics of 'GRAPE: Parallelizing Sequential Graph Computations'. Together they form a unique fingerprint.

Cite this