Edinburgh Research Explorer

GRAPE: Parallelizing Sequential Graph Computations

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Final published version, 727 KB, PDF document

    Licence: Creative Commons: Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

http://www.vldb.org/pvldb/vol10/p1889-fan.pdf
Original languageEnglish
Title of host publicationProceedings of the 43rd International Conference on Very Large Data Bases
PublisherVery Large Data Base Endowment Inc.
Pages1889-1892
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 Sep 2017
http://www.vldb.org/2017/index.php

Publication series

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

Conference

Conference43rd International Conference on Very Large Data Bases
Abbreviated titleVLDB 2017
CountryGermany
CityMunich
Period28/08/171/09/17
Internet address

Abstract

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.

Event

43rd International Conference on Very Large Data Bases

28/08/171/09/17

Munich, Germany

Event: Conference

Download statistics

No data available

ID: 36017645