ImmortalGraph

TLDR

Temporal graphs that capture changes over time are increasingly studied for analyzing evolving social interactions. The paper introduces ImmortalGraph, a storage and execution engine optimized for temporal graphs. ImmortalGraph achieves performance by carefully laying out temporal graphs in storage and memory to exploit locality, employing locality‑aware batch scheduling, and balancing locality, parallelism, and incremental computation for mining tasks. The system delivers up to five‑fold speedup over existing graph databases for queries and up to an order‑of‑magnitude faster iterative mining compared to snapshot‑based engines.

Abstract

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.