iTurboGraph: Scaling and Automating Incremental Graph Analytics

With the rise of streaming data for 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. A dynamic graph consists of an initial graph G and graph mutation updates Δ G$of edge insertions or deletions. Given a query Q, its results$Q(G)$, and updates for Δ G$ to G, incremental graph analytics computes updates Δ Q$such that Q($G Δ G)$=$Q(G) $$ Δ Q where $\cup$ is a union operator. In this paper, we consider the problem of large-scale incremental neighbor-centric graph analytics (). We solve the limitations of previous systems: lack of usability due to the difficulties in programming incremental algorithms for and limited scalability and efficiency due to the overheads in maintaining intermediate results for graph traversals in . First, we propose a domain-specific language, ŁNGA, and develop its compiler for intuitive programming of , automatic query incrementalization, and query optimizations. Second, we define Graph Streaming Algebra as a theoretical foundation for scalable processing of incremental . We introduce a concept of Nested Graph Windows and model graph traversals as the generation of walk streams. Lastly, we present a system , which efficiently processes incremental for large graphs. Comprehensive experiments show that it effectively avoids costly re-executions and efficiently updates the analytics results with reduced IO and computations.