TVA: A Version-aware Temporal Graph Storage System for Real-time Analytics
2026-07-01 • Databases
Databases
AI summaryⓘ
The authors developed TVA, a storage system specially designed to handle graphs that change over time, called temporal graphs. TVA stores information about changes separately from the actual data, making it faster to find specific versions of graph elements like vertices and edges. They also created efficient ways to organize and look up this version information to speed up queries about a vertex's neighbors. Their tests show TVA queries run much faster and use less storage space than current systems.
temporal graphsgraph storageversion metadataverticesedgesneighborhood scanhashingquery latencystorage overheadmulti-version storage
Authors
Wenhao Li, Zhanhao Zhao, Jinhao Dong, Jiamin Hou, Wei Lu, Yunhai Wang, Xiaoyong Du
Abstract
Analyzing temporal graphs can reveal valuable insights that are typically hidden in static graphs. Unfortunately, existing graph storage systems either lack native temporal support or suffer from high latency when querying temporal graphs. This paper presents TVA, a new temporal graph storage system designed for efficient temporal query processing. First, TVA introduces a specialized multi-version storage architecture that separates version metadata from actual data, i.e., the property values associated with different versions of vertices and edges. This architecture enables efficient version retrieval for a vertex or edge by quickly locating valid version metadata and directly dereferencing it to access the corresponding property values. Second, we design tailored data structures, namely the temporal table and enhanced hopscotch-based hashing, to compactly organize the version metadata of adjacent vertices and edges, thus reducing random I/O for metadata lookups during the neighborhood scan initiated from a vertex. Finally, to further accelerate neighborhood scans over multiple vertices, we propose a version-kipping strategy that reuses temporal information obtained from prior scans, thereby avoiding redundant metadata lookups across scans. Empirical evaluations demonstrate that TVA achieves up to 9.9x lower temporal query latency and 2.2x lower storage overhead compared to state-of-the-art temporal graph storage systems.