Fast and Scalable Graph Computations in Distributed Environments

Abstract

Fast and Scalable graph processing is the key to realize the great potential of the graph data. During the last few decades, graph analytics have been found increasingly applicable and useful for the real-world problems, and the real-world graphs such as the World Wide Web and social networks have shown exponential growth, which necessitates scalable and efficient graph processing methods.

While a number of graph processing systems have been proposed to process large-scale graphs, the existing systems do not achieve the efficiency or scalability for large-graphs. Especially, for neighbor-centric graph analytics requiring traversals to multi-hop neighbors, as the existing systems adopt the vertex-centric processing abstraction, its restricted expressiveness leads to signi ficant system bottlenecks in terms of scalability and efficiency.

In addition, the existing systems focus on the analysis of the static graphs and have to re-execute the analytics from scratch whenever the graph data changes. With the rise of streaming data for such dynamic graphs, large-scale graph analytics meets a new requirement of incremental computation because the larger the graph, the higher the cost for updating the analytics results by re-execution. We introduce Nested Windowed Streaming as a computation abstraction which enables fast and scalable processing of neighbor-centric graph analytics for large-scale graphs. We demonstrate how the Nested Windowed Streaming model achieves fast and scalable graph processing for neighbor-centric graph analytics.

We also propose the algebraic formalization of the Nested Windowed Streaming model and exploit it for scaling and automating incremental neighbor-centric graph analytics. We follow the journey of the abstraction to its realization in our proposed systems: TurboGraph++ and iTurboGraph++.