LSGraph: A Locality-centric High-performance Streaming Graph Engine

Streaming graph has been broadly employed across various application domains. It involves updating edges to the graph and then performing analytics on the updated graph. However, existing solutions either suffer from poor data locality and high computation complexity for streaming graph analytics, or need high overhead to search and move graph data to ensure ordered neighbors during streaming graph update.

This paper presents a novel locality-centric streaming graph engine, called LSGraph, to enable efficient both graph analytics and graph update. The main novelty of this engine is a differentiated hierarchical indexed streaming graph representation approach to achieve efficient data search and movement for graph update and also maintain data locality and ordered neighbors for efficient graph analytics simultaneously. Besides, a locality-aware streaming graph data update mechanism is also proposed to efficiently regulate the distance of data movement, minimizing the overhead of memory access during graph update. We have implemented LSGraph and conducted a systematic evaluation on both real-world and synthetic datasets. Compared with three cutting-edge streaming graph engines, i.e., Terrace, Aspen, and PaC-tree, LSGraph achieves 2.98×-81.08×, 1.46×-12.56×, and 1.26×-10.31× speedups during graph update, while obtaining 1.02×-4.28×, 1.58×-3.55×, and 1.20×-2.72× speedups during graph analytics, respectively.

• Theory of computation → Dynamic graph algorithms; Data structures design and analysis.