Edinburgh Research Explorer

Parallelizing Sequential Graph Computations

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=3035942
Original languageEnglish
Title of host publicationSIGMOD '17 Proceedings of the 2017 ACM International Conference on Management of Data
PublisherACM
Pages495-510
Number of pages16
ISBN (Electronic)978-1-4503-4197-4
DOIs
Publication statusPublished - 9 May 2017
Event2017 ACM International Conference on Management of Data - Chicago, United States
Duration: 14 May 201719 May 2017
http://sigmod2017.org/

Conference

Conference2017 ACM International Conference on Management of Data
Abbreviated titleSIGMOD/PODS 2017
CountryUnited States
CityChicago
Period14/05/1719/05/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

2017 ACM International Conference on Management of Data

14/05/1719/05/17

Chicago, United States

Event: Conference

Download statistics

No data available

ID: 28268655