Graph Coloring as a Challenge Problem for Dynamic Graph Processing on Distributed Systems
SessionTensor and Graph Algorithms
Session ChairHari Sundar
Event Type
Paper
Algorithms
Intermediate
Introductory
TimeTuesday, November 15th3:30pm - 4pm
Location355-D
DescriptionAn 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 coloring, to explore massive-scale analytics for dynamic graph processing. We present an event-based infrastructure, and a novel, online, distributed graph coloring algorithm. Our implementation for coloring 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 coloring 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.
This paper uses a challenge problem, graph coloring, to explore massive-scale analytics for dynamic graph processing. We present an event-based infrastructure, and a novel, online, distributed graph coloring algorithm. Our implementation for coloring 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 coloring 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.
