Efficient Snapshot Retrieval over Historical Graph Data

We address the problem of managing historical data for large evolv-ing information networks like social networks or citation networks, with the goal to enable temporal and evolutionary queries and anal-ysis. We present the design and architecture of a distributed graph database system that stores the entire history of a network and pro-vides support for efficient retrieval of multiple graphs from arbi-trary time points in the past, in addition to maintaining the current state for ongoing updates. Our system exposes a general program-matic API to process and analyze the retrieved snapshots. We in-troduce DeltaGraph, a novel, extensible, highly tunable, and dis-tributed hierarchical index structure that enables compactly record-ing the historical information, and that supports efficient retrieval of historical graph snapshots for single-site or parallel processing. Along with the original graph data, DeltaGraph can also maintain and index auxiliary information; this functionality can be used to extend the structure to efficiently execute queries like subgraph pat-tern matching over historical data. We develop analytical models for both the storage space needed and the snapshot retrieval times to aid in choosing the right parameters for a specific scenario. In addition, we present strategies for materializing portions of the historical graph state in memory to further speed up the retrieval process. Secondly, we present an in-memory graph data structure called GraphPool that can maintain hundreds of historical graph instances in main memory in a non-redundant manner. We present a comprehensive experimental evaluation that illustrates the effec-tiveness of our proposed techniques at managing historical graph information. 1