Research On Temporal Graph Processing Techniques

A temporal graph captures changes in a graph over time. It contains the evolving his-tory of the graph, from which graph snapshots at any historical moments can be retrieved. Thus, it is a more versatile data model for research on data analysis and algorithm design of communication networks, social networks and other related topics.Compared to traditional graph data, there are new challenges in storing, querying, and computing of temporal graph data. There is a trade-off between the space complexity of storing and the time complexity of querying temporal graphs. Moreover, it is difficult to leverage the data locality of temporal graph data for interleaving of the graph structure dimension and the time dimension.We studied the processing techniques of large-scale temporal graph data in this thesis, designed and implemented a temporal graph data management system called Auxo, and a graph engine for temporal graph analysis called Chronos.1. Auxo is designed for storing and querying temporal graph data. It proposes a novel data organization unit called spatio-temporal chunk, and investigates the corre-sponding time split policy. The theoretical analysis shows that this solution can achieve linear complexity in both space and time cost for a constantly growing temporal graph. And graph split operations can reduce the worst-case time cost for querying further. It also creates an opportunity for improving the performance of traverse-based graph query operations by rearranging the data layout inside a spatio-temporal chunk. The evaluation shows that Auxo achieves 2.9-12. lx per-formance improvement on global queries, and 1.7-2.7x on local queries, compared to the state-of-the-art solutions.2. Chronos is designed for temporal graph data analysis. We compare the trade-off between partition-parallelism and snapshot-parallelism, and propose hybrid-parallelism for distributed settings. The performance increases due to the co-design of data locality, computation scheduling, and communication cost. The evaluation shows that the performance of Chronos is an order of magnitude better than applying existing graph computation solutions to temporal graph data in a straight-forward way.In summary, the design of the systems in this thesis takes growing trends and intrinsic data locality of temporal graph data as major concerns, and proposes solutions for storing, querying, and computing, which achieve good performance at low cost.