Paper Info
Title
Graph colouring as a challenge problem for dynamic graph processing on distributed systems.
Abstract
An unprecedented growth in data generation is taking place. Data about larger dynamic systems is being accumulated, capturing finer granularity events, and thus processing requirements are increasingly approaching real-time. To keep up, data-analytics pipelines need to be viable at massive scale, and switch away from static, offline scenarios to support fully online analysis of dynamic systems. This paper uses a challenge problem, graph colouring, to explore massive-scale analytics for dynamic graph processing. We present an event-based infrastructure, and a novel, online, distributed graph colouring algorithm. Our implementation for colouring static graphs, used as a performance baseline, is up to an order of magnitude faster than previous results and handles massive graphs with over 257 billion edges. Our framework supports dynamic graph colouring with performance at large scale better than GraphLab's static analysis. Our experience indicates that online solutions are feasible, and can be more efficient than those based on snapshotting.
Year
DOI
Venue
2016
10.1109/SC.2016.29
SC
Keywords
Field
DocType
dynamic graph processing,distributed system,data generation,data analytics pipeline,online dynamic system analysis,massive-scale analytics,event-based infrastructure,distributed graph colouring algorithm,static graph colouring,massive graph handling,dynamic graph colouring,GraphLab static analysis,snapshotting
Algorithm design,Computer science,Fault detection and isolation,Static analysis,Parallel computing,Theoretical computer science,Redundancy (engineering),Granularity,Software quality,Analytics,Test data generation,Distributed computing
Conference
ISBN
Citations 
PageRank 
978-1-4673-8815-3
7
0.49
References 
Authors
23
6
Name
Order
Citations
PageRank
scott sallinen1413.01
Keita Iwabuchi2111.93
Suraj Poudel370.49
Maya Gokhale41329163.33
Matei Ripeanu52461233.84
Roger Pearce624419.40