ImmortalGraph: A System for Storage and Analysis of Temporal Graphs

• Published in: ACM transactions on storage 2015-07, Vol.11 (3), p.1-34
• Main Authors: Miao, Youshan, Han, Wentao, Li, Kaiwei, Wu, Ming, Yang, Fan, Zhou, Lidong, Prabhakaran, Vijayan, Chen, Enhong, Chen, Wenguang
• Format: Article
• Language: English
• Subjects: Computation; Design engineering; Engines; Graphs; Mathematical models; Mining; Temporal logic
• ISSN: 1553-3077; 1553-3093
• DOI: 10.1145/2700302

Temporal graphs that capture graph changes over time are attracting increasing interest from research communities, for functions such as understanding temporal characteristics of social interactions on a time-evolving social graph. ImmortalGraph is a storage and execution engine designed and optimized specifically for temporal graphs. Locality is at the center of ImmortalGraph’s design: temporal graphs are carefully laid out in both persistent storage and memory, taking into account data locality in both time and graph-structure dimensions. ImmortalGraph introduces the notion of locality-aware batch scheduling in computation, so that common “bulk” operations on temporal graphs are scheduled to maximize the benefit of in-memory data locality. The design of ImmortalGraph explores an interesting interplay among locality, parallelism, and incremental computation in supporting common mining tasks on temporal graphs. The result is a high-performance temporal-graph system that is up to 5 times more efficient than existing database solutions for graph queries. The locality optimizations in ImmortalGraph offer up to an order of magnitude speedup for temporal iterative graph mining compared to a straightforward application of existing graph engines on a series of snapshots.