GraphIn: An Online High Performance Incremental Graph Processing Framework
The massive explosion in social networks has led to a significant growth in graph analytics and specifically in dynamic, time varying graphs. Most prior work processes dynamic graphs by first storing the updates and then repeatedly running static graph analytics on saved snapshots. To handle the extreme scale and fast evolution of real world graphs, we propose a dynamic graph analytics framework, GraphIn, that incrementally processes graphs on the fly using fixed sized batches of updates. As part of GraphIn, we propose a novel programming model called I GAS based on gather apply scatter programming paradigm that allows for implementing a large set of incremental graph processing algorithms seamlessly across multiple CPU cores. We further propose a property based, dual path execution model to choose between incremental or static computation. Our experiments show that for a variety of graph inputs and algorithms, GraphIn achieves upi?zto 9.3 million updates/sec and over 400$\times speedup when compared to static graph recomputation.
Euro Par