Clock-G: Temporal Graph Management System

Graphs are a ubiquitous data model for capturing entities and their relationships. Since most graphs that model real-world networks evolve over time, efficiently managing temporal graphs is an important problem from both a theoretical and practical perspective. Querying the history of temporal graphs can lead to new applications such as object tracking, anomaly detection, and predicting future behavior. However, existing commercial graph databases lack native temporal support, hindering their usefulness in these use cases. This paper introduces Clock-G, a temporal graph management system designed to handle the history temporal graphs. What differentiates Clock-G from other temporal graph management systems is its comprehensive approach, covering query language, query processing, and physical storage. We define T-Cypher, a temporal extension of Cypher query language, enabling user-friendly and concise querying of the graph’s history. Additionally, we propose a query processor that utilizes temporal statistics collected from underlying temporal graphs to offer a good evaluation plan for T-Cypher queries. We also propose a novel storage technique that balances space usage and query evaluation time.