ACGraph: Accelerating Streaming Graph Processing via Dependence Hierarchy
DescriptionStreaming graph processing requires massive computation resources to evaluate continuous queries with low latency. Prior streaming graph systems process updates in an irregular order, which results in a lot of redundant computations. To address the issues, we propose ACGraph, a novel streaming graph processing approach for monotonic graph algorithms. It maintains dependence trees during runtime, and leverages the dependencies between vertices to normalize the state propagation order, thus greatly reducing redundant computations. Experimental results show that our approach reduces the number of vertices updates by 60% on average, and achieves the speed up of about 2~10X over state-of-the-art systems.
Event Type
Research Manuscript
TimeWednesday, July 12th11:25am - 11:40am PDT
Location3010, 3rd Floor
Emerging Models of Computation