GraPU: Accelerate Streaming Graph Analysis through Preprocessing Buffered Updates

Streaming graph analysis extracts timely insights from evolving graphs, and has gained increasing popularity. For current streaming graph analytics systems, incoming updates are simply cached in a buffer, until being applied onto existing graph structure to construct a new snapshot. Iterative graph algorithms then work on the new snapshot to produce up-to-date analysis result. Nevertheless, we find that for widely used monotonic graph algorithms, the buffered updates can be effectively preprocessed to achieve fast and accurate analysis on new snapshots. To this end, we propose GraPU, a streaming graph analytics system for monotonic graph algorithms. Before applying updates, GraPU preprocesses buffered updates in two sequential phases: 1) Components-based Classification first identifies the effective graph data that are actually affected by current updates, by classifying the vertices involved in buffered updates according to the predetermined connected components in underlying graph; 2) In-buffer Precomputation then generates safe and profitable intermediate values that can be later merged onto underlying graph to facilitate the convergence on new snapshots, by precomputing the values of vertices involved in buffered updates. After all updates are applied, GraPU calculates new vertex values in subgraph-centric manner. GraPU further presents Load-factors Guided Balancing to achieve subgraph-level load balance, by efficiently reassigning some vertices and edges among subgraphs beforehand. Evaluation shows that GraPU outperforms state-of-the-art KineoGraph by up to 19.67x, when running four monotonic graph algorithms on real-word graphs.