Maria Massri
email: maria.massri@orange.com

Zoltan Miklos
email: zoltan.miklos@irisa.fr

Philippe Raipin
email: philippe.raipin@orange.com

Pierre Meye
email: pierre.meye@orange.com

Clock-G: A temporal graph management system with space-efficient storage technique

Keywords: Temporal Graphs, Graph management systems, Temporal graph traversal

published or not. The documents may come

I. INTRODUCTION

Graphs are frequently used to model real-world interactions as a collection of vertices and edges providing generally a fertile ground to analyze relationship-centered domains. Despite the wealth of studies on managing static graphs, a time version support is seldom provided.

In this work, we mainly focus on designing a temporal graph management system and integrating it into the Orange initiated platform Thing'in. This platform manages a graph of objects that can be either connected such as IoT devices (machines, traffic lights, cameras, etc.) or non-connected (doors, roads, shelves, etc.). It equally maintains a thorough structural and semantic description of the environments of these objects, such as cities or buildings, in which they are located. The clients of this platform are companies and public administrations developing services around smart cities, building or factories, as well as private object owners and developers building analytical IoT applications. This graph of objects is maintained by a commercial graph database that do not account for the temporal dimension. However, there has been an extensive and recent demand by the clients of Thign'in for preserving the past states and connections of the graph for the interest of tracking objects, anomaly detection and forecasting the future behaviour. For instance, Mo.Di.Flu, a project whose main goal targets the Industry 4.0 and BIM2TWIN 3 European project focusing on the integration of Digital Twins [START_REF] Tao | Digital twin in industry: State-of-the-art[END_REF] in smart buildings (e.g., smart factories), represents a concrete use case that motivated the integration of the temporal dimension into the graph of Thing'in. Mo.Di.Flu collaborates with Thing'in in order to keep track of the different positions of a product throughout a manufacturing pipeline, hence, detect the causes of manufacturing delays or products loss. Another requirement, also applied on the use-ase of smart factories, consists of reconstructing the surroundings of a machine at a given time instant or the states of all machines right before a system failure. These querying capabilities are only enabled by a system that persists the historical states and interactions recorded in the factory. These requirements have been the incentive of maintaining the history of the graph of Thing'in which we have addressed by designing the temporal graph management system Clock-G. This system is developed by the team of Thing'in and is currently being deployed into production.

Storing and querying temporal graphs are possible by exploiting a commercial graph database with temporal metadata [START_REF] Debrouvier | A model and query language for temporal graph databases[END_REF]- [START_REF] Huang | Tgraph: A temporal graph data management system[END_REF]. However, these systems do not natively offer timeversion support which might lead to unpredictable performances. Hence, we argue that time should be considered as a first-class citizen rather than a simple add-on.

A critical point in the design of such a system is defining a formal model of temporal graphs. Hence, we propose OPGM Operation-based Property Graph Model that we refer to throughout the paper to define key concepts of our proposal.

Available temporal graph management systems focus on the storage model in order to deal with the outgrowing size of data while being able to query it efficiently. In this context, several storage approaches have been proposed in literature such as the Log and the Copy+Log methods.

The Log approach [START_REF] George | Time-aggregated graphs for modeling spatiotemporal networks[END_REF], [START_REF] George | Spatio-temporal sensor graphs (stsg): A data model for the discovery of spatio-temporal patterns[END_REF] consists of preserving all the graph updates as a series of timestamped logs. Whereas the Copy+Log [START_REF] Khurana | Efficient snapshot retrieval over historical graph data[END_REF] approach consists of storing the graph updates in time windows such as each time window contains a fixed number of graph operations. These time windows are stored along with snapshots that represent the state of the graph at the end of each time window and are used as starting points for query evaluation.

Despite the advantage of the Copy+Log method in pruning the search space, storing full graph snapshots is space consuming, particularly in the case of growth-mostly graphs. The limitation of this method is that unchangeable graph entities will be copied across snapshots causing a large volume of redundant graph entities. Whereas the Log approach has a detrimental impact on the query evaluation time. Hence, a compromise between both methods is needed which is mainly addressed in this paper by proposing the δ-Copy+Log method.

The δ-Copy+Log method stores all graph updates in time windows. Instead of storing full snapshots along with these time windows, it stores deltas which contain only the difference between two successive snapshots. To clarify, a delta contains all the graph updates that are contained in a time window and are not canceled by another graph update. For instance, an addition of a graph element is cancelled by a deletion of the same graph element, thus, not stored in a delta. Besides deltas, a snapshot is stored for each M time windows that is considered as a starting point for query evaluation. That is, M represents as a configurable parameter that can tune the performance of the δ-Copy+Log method. Furthermore, we define two types of deltas: forward and backward deltas such that we store half of the time windows and their corresponding deltas between successive snapshots in a forward fashion, whereas the other half is stored in a backward fashion. Having this, based on the positioning of the requested time instant of a query, we choose between a forward or backward construction of the result. Indeed, this has the advantage of reducing the maximum execution time of queries by a factor of 50%. Besides, we also propose an optimization technique to mitigate the query execution time overhead caused by storing deltas instead of snapshots. This technique consists of assigning each delta with a Bloom filter that will be checked whenever data is requested from that delta.

We developed Clock-G: a system that manages temporal property graphs and adopts the δ-Copy+Log storage method. The system Clock-G supports several types of temporal queries such as point-based and range-based local and global queries. Clock-G also supports a special type of range-based traversal queries referred to as time-increasing paths [START_REF] Zhang | Distributed time-respecting flow graph pattern matching on temporal graphs[END_REF]- [START_REF] Redmond | Subgraph isomorphism in temporal networks[END_REF]. The queries supported by Clock-G belongs to the category of OLTP queries which cover most of the needs of our industrial use case.

We also conducted experiments to evaluate the performance of Clock-G. The obtained results are inline with previous findings on the apparent trade-off between space and query execution time of the Copy+Log and Log. Furthermore, a comparison between these traditional methods and the δ-Copy+Log validates that the δ-Copy+Log offers a good compromise between the performances of the Log and Copy+Log methods. Besides, we showcase how the parameters of Clock-G can be calibrated in order to tune the overall performance with an adequate configuration that adheres most with the acceptable threshold of query latency and available storage resources. We also compared the performance of Clock-G with a non-temporal commercial graph database (Neo4j4 ) to motivate the choice of creating a temporal graph management system with a native temporal support instead of simply adding a temporal layer. The results show that Clock-G outperforms Neo4j by orders of magnitude.

The main contributions of this work reduce to the following:

• Defining a formal model of temporal property graphs.

• Proposing δ-Copy+Log as a space-efficient variant of the traditional Copy+Log method. • Implementing the δ-Copy+Log in a temporal graph management system Clock-G with optimization techniques that accelerates the query evaluation time.

• Evaluating the performance of Clock-G with large scale real-world and synthetic temporal graphs and validate the gain of using δ-Copy+Log technique as compared to traditional techniques. Outline Section II discusses the related work. Section III introduces key definitions of our temporal graph model. Section IV introduces and formalises key concepts of the δ-Copy+Log storage approach. Section V introduces the key design features of Clock-G such as its architecture and querying optimizations. Section VI evaluates the work through experiments conducted on real and synthetic datasets. Finally, Section VII concludes the paper.

II. RELATED WORK

The challenge of versioning data is one of the classical problems in data management and there is a large literature on this subject, however it is not extensively studied in the context of graph management systems. Indeed, such a system must incorporate first a formal model for underlying temporal graphs. Since these graphs are not as intuitive as their static counterparts [START_REF] Holme | Modern temporal network theory: a colloquium[END_REF], several formal models have been posited in literature [START_REF] Wu | Reachability and timebased path queries in temporal graphs[END_REF]- [START_REF] Wen | Efficiently answering span-reachability queries in large temporal graphs[END_REF]. The main limitation of these models is that they do not support the property graph model and assign only edges with timestamps. In this context, we provide a formal model of temporal property graphs presented in Section III.

Narrowing the survey on the storage of temporal graphs, two main concerns should be addressed: the backend storage engine and the storage technique. Since temporal graphs can grow very large in size, the questions of secondary storage are crucial. In this context, one can develop a temporal graph management system by designing a dedicated storage engine such as a file system layout [START_REF] Miao | Immortalgraph: A system for storage and analysis of temporal graphs[END_REF] or a temporal key/value store [START_REF] Haeusler | Chronograph: A versioned tinkerpop graph database[END_REF]. However, regarding the fact that most real-world temporal graphs are more likely to exponentially grow in size, the backend storage engine should offer scalability. Such a specification is natively offered by NoSQL databases which has been already exploited in the design of temporal management systems. Examples of such an implementation are SystemG [START_REF] Vijitbenjaronk | Scalable time-versioning support for property graph databases[END_REF] using a key/value store LMBD 5 and ChronoGraph [START_REF] Byun | Chronograph: Enabling temporal graph traversals for efficient information diffusion analysis over time[END_REF] using a document store MongoDB [START_REF] Chodorow | MongoDB: the definitive guide: powerful and scalable data storage[END_REF]. Clock-G relies on Apache Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF] as a backend storage engine. In this paper, we choose Cassandra for the reasons of scalability, fault-tolerance and engineering maturity.

Available temporal graph storage techniques can be categorized as follows: Log, Copy, Copy-on-write and Copy+Log. These methods are mainly motivated by concepts of logging and checkpointing which reflects on lessons learned from classical techniques of database state recovery [START_REF] Verhofstad | Recovery techniques for database systems[END_REF], [START_REF] Haerder | Principles of transaction-oriented database recovery[END_REF]. The Log approach followed by Raphtory [START_REF] Steer | Raphtory: Streaming analysis of distributed temporal graphs[END_REF], ChronoGraph [START_REF] Haeusler | Chronograph: A versioned tinkerpop graph database[END_REF] and TAG [START_REF] George | Time-aggregated graphs for modeling spatiotemporal networks[END_REF], [START_REF] George | Spatio-temporal sensor graphs (stsg): A data model for the discovery of spatio-temporal patterns[END_REF] consists of storing graph updates as a series of timestamped logs such that any graph state can be recovered by reloading all logs with a relative timestamp lower than or equal to the requested one. Whereas the Copy approach consists of materializing and persisting graph snapshots. As discussed by authors of [START_REF] Salzberg | Comparison of access methods for timeevolving data[END_REF], the Log and Copy represents two extremes for storing temporal graphs. That is, these methods favor either the optimization of the space usage at the expense of the query's computation time or vice-versa. Instead of storing full graph copies, the Copy-On-Write [START_REF] Hartmann | Analyzing complex data in motion at scale with temporal graphs[END_REF]- [START_REF] Castelltort | Representing history in graph-oriented nosql databases: A versioning system[END_REF] consists of copying the state of a single graph entity that can be a vertex or edge whenever the latter gets updated. The main limitation of this technique is that one cannot control the copying frequency as it depends on the granularity of graph updates. The Copy+Log storage method [START_REF] Khurana | Efficient snapshot retrieval over historical graph data[END_REF], [START_REF] Miao | Immortalgraph: A system for storage and analysis of temporal graphs[END_REF], [START_REF] Han | Chronos: a graph engine for temporal graph analysis[END_REF]- [START_REF] Xiangyu | An efficient snapshot strategy for dynamic graph storage systems to support historical queries[END_REF] consists of storing graph updates in temporally disjoint chunks known as time windows along with valid states of the graph known as snapshots. These snapshots represent a materialization of the graph states that are valid between the boundaries of two successive time windows. The advantage of this solution relies in the fact that recovering the state of the graph at a given time instant requires at most reading a single snapshot and all graph updates recorded in a time window. This method reflects on lessons learned from the area of database recovery such as Oracle's RMAN 6 .

The critical limitation of the Copy+Log that is mainly tackled in this work relates to the fact that snapshots are cost prohibitive in terms of space consumption because they materialize the state of every existing vertex or edge at a single time instant. Now, in a lot of use cases some parts of the graph are static especially in growth mostly graphs where additions are more probable than deletions. In this case, vertices and edges tend to survive for longer duration and hence are copied over and over again in several snapshots. To overcome this limitation, we proposed the δ-Copy+Log storage approach to mitigate the space usage caused by the storage of full graph snapshots. In this method, we consider deltas representing the difference between snapshots instead of snapshots. However, we preserve a number of snapshots to serve as starting points for query evaluation such that after a fixed number of delta, a full snapshot is materialized. The main difference between the δ-Copy+Log and the methods that follow the Copy+Log technique such as RMAN is that storage of full snapshots or full database backups is critical and space consuming. Hence, we propose in this paper to keep the time windows (incremental backups) but to replace full backups (snapshots) by deltas which contain only the difference between two snapshots. If a large number of incremental updates cancel each other between two successive snapshots, leading to few differences between successive snapshots, the δ-Copy+Log keeps only those differences to preserve space. Now, to account for the evaluation time overhead, we add bloom filters to the deltas to verify the existence of an element in a delta.

III. FORMAL DEFINITIONS

A. Time domain

In this section, we provide a definition of the time domain. Indeed, defining the time domain is needed in data management systems when temporal ontologies are to be defined in order to assign data items with temporal validity information [START_REF] Montanari | Time Domain[END_REF]. In this work, we choose a discrete temporal flow by considering a time axis that is quantified by time granules [START_REF] Clifford | A consensus glossary of temporal database concepts[END_REF]. A time granule, also referred to as a chronon, is the smallest non-decomposable unit of time defined by a specific temporal granularity (for example, a second or a millisecond, etc.). Hence, we consider D T = t i |i ∈ N {N ow, ∞} to be the time domain defined as a totally ordered set of instants such that the duration between consecutive instants is equal to a chronon. Besides, we consider a transactional time of graph updates that is assigned by the system. Hence, we do not encounter the classical challenges of valid time considerations such as out-of-order insertions, clock shifts, different time zones or granularity that are imposed by having independent data spouts assigning a valid timestamp for each event.

B. Temporal property graph model

In this section, we introduce the Operation-based Property Graph Model (OPGM) that is used throughout the paper to define key concepts of our proposal.

We define the notations used to formalize this model as follows: Let V and E denote finite sets of vertex and edge identifiers (ids), respectively. Vertices and edges can have a single label and a set of dynamic property keys denoted as P . Let R denote an infinite set of atomic values that can have any type from a finite set of data types D (e.g., string), L denote a finite set of strings, id denote an identifier, 2 X denote the set of all finite subsets of domain X. Finally let a, d and u denote an addition, deletion and update respectively. We define a graph operation i as an action applied on a graph entity which translates to either an addition/deletion of a vertex/edge or the update of a dynamic property. We define finite sequence of temporally ordered graph operations Υ = i , i ∈ N . Following the OPGM, a temporal property graph model is a tuple:

G O = Υ, V, E, P, ρ, α, f G , f T , f E
We explain the functions below:

• ρ : (V ∪ E) → 2 L maps each vertex and edge to a finite set of labels from L. • α : E → (V × V ) maps each edge to its source and target ID. Example III.1. To clarify, we provide in the following an example of a toy graph modelling the use case of Mo.Di.Flu presented in Section I. Figures 1a and1b illustrate a temporal property graph and its representation based on the OPGM model, respectively. The temporal graph models the dynamic connections between the machines and products and the different values recorded by the sensors monitoring the state of the machines. We show how, for a sample of vertices and edges, the history of this graph can be represented using the above definitions:

• f G : Υ → (V ∪ E ∪ ((V ∪ E) × R × P ))
• V = {n 1 , ..., n 5 }, E = {e 1 , ..., e 6 }, P = {Status}; • ρ(r) = {Machine}, if r ∈ {n 1 , n 2 } {In}, if r ∈ {e 1 , ..., e 6 } ; • α = {e 1 → (n 3 , n 2 ), e 2 → (n 3 , n 2 )}; • Υ = { 1 , ..., 14 }; • f G = { 1 → e 1 , 4 → e 1 , 13 → (n 1 , O, Status)}; • f T = { 1 → t 1 , 4 → t 4 , 13 → t 12 }; • f E = { 1 → a, 4 → d, 13 → u};
As presented in Figure 1a, the validity intervals of vertices indicate the time during which the corresponding machine or product was recorded into the database. The validity intervals of the 'In' edges indicate the time during which a product was in a machine. The property 'Status' indicates the value and the time interval of the status of a machine.

IV. δ-COPY+LOG

The δ-Copy+Log is a variant of the Copy+Log storage approach that we propose to mitigate the space cost induced by storing full snapshots. Recall that the Copy+Log consists of storing snapshots that are valid between the boundaries of a time window s.t. each time window contains a fixed number of graph operations. Now, the δ-Copy+Log follows a similar mechanism with the main difference that consists of storing deltas instead of snapshots. A critical point is that a delta differs from a time window. That is, a time window contains every graph operation that exists between two snapshots whereas a delta contains the only the minimum number of graph operations that morph a snapshot into another one. Indeed, an addition of an element in cancelled by a deletion of the same element, hence, both operations are stored in time window but omitted from the delta. We store a snapshot after a number of time windows in order to serve as a starting point for query evaluation. Having this, we store graph operations in consecutive time buckets containing each a number M of time windows such that the first M -1 time windows ends with a delta, whereas the final time window ends with a snapshot. A critical optimization is the forward and backward data storage and retrieval. That is, half of the deltas and time windows in a bucket is constructed in a forward fashion whereas the other half is constructed in a backward fashion. The rationale behind this choice is the acceleration of the query execution time. That is, we choose the closest snapshot from which to start the retrieval then compute the result in a forward or backward fashion whether the time instant of that snapshot is lower or greater than the requested one.

Figure 2 illustrates the storage internals of the δ-Copy+Log and Copy+Log methods. It shows that the Copy+Log method stores time windows and snapshots. Whereas, the δ-Copy+Log stores time windows, deltas and snapshots. In this example, we consider a set of time buckets B where M = 6 which implies that the bucket contains 3 forward time windows {ω 1 ⇒ , ω 2 ⇒ , ω 3 ⇒ } and 3 backward time windows {ω 4 ⇐ , ω 5 ⇐ , ω 6 ⇐ }. At the highest time instant of a forward time window, a delta is materialized resulting in 3 forward deltas

{δ 1 ⇒ , δ 2 ⇒ , δ 3 ⇒ }.
Whereas, a delta is materialized at the lowest time instant of every backward time window except the last time window where a snapshot is materialized resulting in 2 ⇒ whose timestamp is lower than t. Whereas, if t falls within the time interval of the time window ω 5 ⇐ , we construct the result in a backward fashion. That is, we start by fetching S 6 then δ 5 ⇐ and finally ω 5 ⇐ . Note that, in the Copy+Log method all the time windows are considered as forward.

All the symbols used in this section can be found in table I. In the following, we describe the key components of the δ-Copy+Log approach.

Time buckets: The concept of time buckets stems from the choice of storing a fixed number of time windows and deltas between two snapshots. Indeed, we store the history of the graph in a sequence of temporally disjoint time buckets s.t. each time bucket is a logical container of M time windows and their corresponding checkpoints. That is, a checkpoint can be either a delta or a snapshot. Now, we store a snapshot that is valid at the highest time instant of the last time window of a each bucket, whereas we store a delta at the ending time instant of other time windows. Having this, M time windows exist between the snapshots of two successive buckets. Besides, the first M/2 time windows are constructed in a forward fashion and ends each with a forward delta. Whereas, the rest of the time windows are constructed in a backward fashion and ends each with a backward delta. To formalize, we consider the sequence of time buckets B = b i |i ∈ N s.t. a time bucket is defined as the tuple b i = Ω i , Γ i :

• Ω i = ω j |j ∈ [iM + 1, (i + 1)M ] is the sequence of time
windows that can be a forward or backward time window

ω j = ω j ⇒ ifj ∈ [iM + 1, (i + 1/2)M ] ω j ⇐ ifj ∈ [(i + 1/2)M + 1, (i + 1)M ] (1)
• Γ i = γ j |j ∈ j ∈ [iM + 1, (i + 1)M ] -(i + 1/2)M
is the sequence of checkpoints that can be a snapshot, forward or backward delta s.t.:

γ j =      s j if j = (i+1)M δ j ⇒ if j ∈ [iM + 1, (i + 1/2)M -1] δ j ⇐ if j ∈ [(i + 1/2)M + 1, (i + 1)M -1] (2)
Time windows: A time window is a physical container of N graph operations. A forward time window ω i ⇒ contains graph operations that are sorted following an ascending order of their timestamps. However, a backward time window ω i ⇐ contains graph operations that are first reversed, meaning that an addition is stored as a deletion and vice versa then sorted following a decreasing order of their timestamps.

Snapshots: A snapshot is only persisted at the ending time instant of the last time window of a bucket and represents a state that is valid at that time instant. If the bucket corresponds to a vertex or edge label, then a snapshot contains all vertices and edges that exist at the time instant of the snapshot. Whereas, if the bucket corresponds to a dynamic property, then a snapshot contains all vertices and edges that has that property with the last updated value before or at the time instant of a snapshot.

Deltas: A delta between two snapshots S and S contains the minimum number of graph updates that permit the transformation of S into S . That is, if an addition is followed by a deletion of the same graph entity, these graph operations cancel each other and will not be added to the corresponding delta. Having this we can formally define a forward delta δ i ⇒ , using constructs from the OPGM model, as follows:

δ i ⇒ = { k |∀ k ∈ ω i ⇒ (∀ l ∈ ω i ⇒ -{ k }(f G ( k ) = f G ( l ) =⇒ f T ( k ) > f T ( l ))) } (3)
Equation ( 3) states that a graph operation is contained in a forward delta if the former is not followed by any other graph operation in the same time window that maps to the same graph entity. A formal definition of a backward delta can be derived from Equation (3) by replacing δ i ⇒ and ω i ⇒ by δ i ⇐ and ωi and (f

T ( k ) > f T ( l )) by (f T ( k ) < f T ( l )).

A. Space and time complexities

In this section, we present and discuss the space and time complexities of δ-Copy+Log, Log and Copy+Log methods. We consider the system parameters: N , M , c 1 , c 2 , r 1 and r 2 and the graph parameters: γ and p d . Parameters γ, N and M are previously defined and correspond to the set of all the graph operations, number of graph operations in a time window and the number of time windows in a bucket, respectively. Now, parameters c 1 and c 2 are constants that correspond to the size of a single graph operation or graph element. Whereas, r 1 and r 2 are constants that correspond to the time taken to read a graph operation or graph element. Parameter p d corresponds to the probability of deleting a graph element. For simplicity, we assume that all deleted elements are created in the same time window.

The space usage of the δ-Copy+Log method is the sum of the space occupied by graph operations (χ o ), deltas (χ d ) and snapshots (χ s ). We compute (χ o ), (χ d ) and (χ s ) separately, as follows. Space occupied by graph operations is equal to the total number of graph operations (|γ|) times the space occupied by each graph operation (c 1 ) as indicated in the following equation:

χ o = |γ|c 1
Space occupied by deltas is equal to the total number of deltas

( (M -2)|γ| N M
) times the space occupied by each delta. The space occupied by each delta is equal to the total number of graph operations that are not canceled by a deletion (N -2p d N ) times the space occupied by each graph operation (c 1 ). Having this the space occupied by deltas can be computed as follows:

χ d = (1 -2p d ) M -2 M c 1 |γ|
Space occupied by snapshots The total number of graph elements in the i th snapshot is equal to the total number of graph operations that were not canceled by any deletion

(iN M (1 -2p d ))
whereas the total number of snapshots is equal to |γ| N M . Given that, the number of elements in snapshots represent an arithmetic sequence:

{N M (1 -2p d ), 2N M (1 - 2p d ), . . . , |γ| N M N M (1 -2p d )}.
The space usage of snapshots is equal to the sum of the number of elements in all snapshots times the space usage of a graph element c 2 which leads to the following equation:

χ s = ( |γ| N M + 1) (1 -2p d )|γ| 2 c 2 , |γ| N M 1 = (1 -2p d ) 2N M c 2 |γ| 2
Having this, the total space usage of the δ-Copy+Log method (χ δ-CL ) can be formulated as follows:

χ δ-CL = (1 + (1 -2p d ) (M -2) M )c 1 |γ| + (1 -2p d ) 2N M c 2 |γ| 2
The space usage of the Log approach (χ Log ) is equal to the space occupied by all graph operations (χ o ) which implies the following:

χ Log = c 1 |γ|
The space usage of the Copy+Log method (χ CL ) is equal to the space occupied by graph operations and snapshots (χ o + χ s ) where M = 1. Having this, we derive the following:

χ CL = c 1 |γ| + (1 -2p d ) 2N c 2 |γ| 2
From the obtained equations for χ Log , χ δ-CL and χ CL , we can derive the following:

χ Log ≤ χ δ-CL ≤ χ CL
We analyze the time complexity of a unary query evaluation operator for point-based traversal queries. The expand operator (↑ τ (v)) retrieves all the edges of a vertex v whose validity intervals contain the time instant τ . Note that the expand operator was first proposed in [START_REF] Hölsch | An algebra and equivalences to transform graph patterns in neo4j[END_REF] to define a graph algebra. In this complexity analysis, we use a simplified temporal variant of this operator. Execution time of the expand operator: In the following we consider the worst case execution time of the operator. That is, expanding a vertex at a given time instant implies reading at most from the snapshot whose timestamp is the closest to τ . Then, it induces reading all the operation in the deltas of the selected time bucket whose time interval is before τ which implies reading (( M 2 -1)N ) graph operations. Finally, it induces reading all the graph operations in the time window that follows the last selected delta. Having this, we obtain the following:

T δ-CL (↑ τ (v)) = (r 2 + ( M 2 -1)N r 1 + N r 1 )
The expansion of a vertex using the Log method might incur loading all graph operations in γ. Having this, we derive the following:

T Log (↑ τ (v)) = |γ|r 1
Finally, the expansion of a vertex using the Copy+Log method incur a single snapshot read which implies the following:

T Copy+Log (↑ τ (v)) = r 2 Consider |γ| ( N M
2 ) and |γ| r2 r1 , then we can derive the following:

T Copy+Log (↑ τ (v)) ≤ T δ-CL (↑ τ )(v) ≤ T Log (↑ τ )(v)
This analysis validates that δ-Copy+Log presents a compromise between the Log and Copy+Log methods.

V. CLOCK-G

A. Architecture

In the following, we provide the description of the key elements composing the architecture of Clock-G (Figure 3). 1) Client API: Clock-G offers a Client API enabling a client to connect, ingest graph updates or query the stored graphs. For instance, users can define the graph space's schema that includes labels of vertices and edges and a set of static and dynamic properties for each vertex/edge label. That is, we differentiate between static and dynamic properties for the interest of reducing the disk space usage such that static properties will be stored along with the corresponding vertex or edge whereas dynamic properties are stored separately as depicted in Section V-A3. Users can insert graph operations individually or in batches into the system. In both cases, graph operations are attached with a transactional time based on the system's internal clock. Besides, users can query the temporal graph with local and global point queries.

2) Request Handler: The request handler manages a pool of a fixed number of workers s.t. each worker is responsible of serving a single client request. Requests are first sent to the gateway and then buffered until being served by a free worker.

3) Storage: Clock-G uses the column-oriented database Apache Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF] as a backend store. We choose Cassandra for the reasons of robustness, engineering maturity and scalability. Besides, Cassandra sorts blocks of data according to a given column or combination of columns. We utilize this feature in order to sort graph updates according to their chronological order which accelerates their sequential read.

For instance, the storage is separated based on the graph entity type. That is, we store vertex operations in vertex store, edge operations in edge store and dynamic property operations in property store. In each store, the storage is separated based on the type of graph element. The vertex and edge stores separate the storage of different vertex and edge labels, respectively. Whereas, property store separates the storage of different property names. The rationale behind the separation is that graph elements are more likely to be queried independently.

For each vertex/edge label or dynamic property name we partition the storage based on a Hash partitioning strategy. Each of these partitions corresponds to a storage unit and is stored following the δ-Copy+Log method (denoted δ-CL in Figure 3 for simplicity).

4) Bloom Cache: In order to mitigate the execution time overhead of graph traversals induced by the storage of deltas instead of snapshots, we assign each edge delta with a Bloom filter. Indeed, for each graph operation in a delta, we add the ID of the source vertex to the Bloom filter. Having this, we can accelerate graph traversals by skipping the retrieval of the neighborhood of a vertex if the id of the latter is not found in the Bloom filter. It should be noted that we keep Bloom filters in main memory s.t. we fix the threshold of memory usage as a design parameter to limit the creation of bloom filters. That is, whenever the space occupied by Bloom filters reaches the specified threshold, we follow a FIFO (First In First Out) policy to evict the oldest Bloom Filters (corresponding to the oldest delta) from cache. Further description of the functionality of Bloom filters in the acceleration of query evaluation is provided in section V-B. 6) Backend connector: The backend connector manages a pool of workers whose main functionality is to connect to and execute requests against the backend store. It is critical to mention that a backend worker is responsible for a range of partitions s.t. all requests directed to a worker correspond to elements of its local partitions. A write request consists of the insertion of a graph operation in a forward or backward time window, creation of a forward or backward delta, or creation of a snapshot. In order to create a delta, a worker loads the time window in memory, then removes any pair of graph operations that cancel each other. Whereas, it creates a snapshot by loading the snapshot of the previous time bucket on which it applies the graph updates contained in forward deltas and the inverse of the graph updates contained in backwards deltas of the current time bucket. If a read request consists of finding the neighborhood of a source vertex in a delta, then the worker checks the corresponding Bloom filter from the Bloom cache. Having this, the backend store is only fetched in case the bloom filter returns a positive response.

B. Querying

Clock-G supports several types of temporal graph queries as defined below.

1) Point-based local queries: This type of queries retrieve the N-Hop neighborhood of a vertex given several predicates. These predicates are used to express constraints on the id, label, or values of properties of the starting vertex, length of the traversal, type of the edges and the time instant at which all the vertices and edges must be valid. For the industrial use-case presented in this paper, a local query (N-Hop queries, i.e.) can retrieve the surroundings of a malfunctioning machine including sensors, other machines, products up to a fixed length, given a set of property predicates at a given time instant. For example, the property predicates can express that the property representing the status of the machine should be equal to 'Out-of-service' at the requested time instant. Clock-G returns the traversal in the form of a Bag of records s.t. each record u is a tuple mapping a field name k to a value v s.t. u(k) = v. The notation dom(u) is used to denote the domain of u. Now, each tuple represents a valid path that maps a depth d , s.t. 0 ≤ d ≤ d where d is the depth of the traversal, to the id of the vertex that belongs to the path at d . Towards introducing the algorithm of the traversal, we define the following unary operators:

• Select: σ c (r) This operator selects the tuples of a bag r for which the propositional formula c holds and returns a new bag with the selected tuples. • Distinct: ϑ(r) This operator returns a bag containing all distinct tuples of a bag r s.t. it de-duplicates tuples sharing the same set of fields that are mapped to same values. • Projection: π f0,f1,...,fn (r) This operator keeps a specific set of the names of the fields (f 0 , f 1 , ..., f n ) of a bag r.

Note that the tuples are not de-duplicated, thus the result bag can have the same number of tuples as the input bag.

• Expand:

(r) ----→ i,(x,y)
This operator expands a tuple u, if u is contained in a bag r and maps the field i to the value x s.t. u(i) = x, by adding the field i + 1 to dom(u) s.t. u(i + 1) = y and keeps u unchanged otherwise. Then, the operator adds the tuple u to the returned bag.

• Shrink (r) ← ---- i,(x,y)
This operator shrinks a tuple u, if u is contained in a bag r and maps fields i and i+1 to values x and y s.t. u(i) = x and u(i+1) = y, by removing the field i + 1 from dom(u) and keeping u unchanged otherwise. Then, the operator adds the tuple u to the returned bag.

Algorithm 1 depicts how the N-Hop traversal is computed. The Algorithm takes an id of the source vertex s, a number of hops d and a time instant t and returns a traversal T that contains all paths of depth d starting from s and existing at t. First, InitBag initializes T as a bag with a single tuple u mapping hop 0 to the id of the source vertex s.t. u(0) = s. Then, GetCheckpointIDs returns an array of the identifiers of the δ-Copy+Log components that has to be fetched in each hop of the traversal. Indeed, those identifiers are sorted incrementally or decreasingly whether the traversal has to be computed in a forward or backward fashion, respectively. The result is then computed in a BFS (Breadth First Search) fashion. Indeed, for each hop n, we get the set nextV ertices using the projection and distinct operators that extracts the distinct vertices found at depth n from the traversal T . Then, the vertices of depth (n + 1) are computed by finding the neighbors of each vertex found in nextV ertices. That is, the algorithm finds the neighbors by visiting every component whose id is contained in ids.

In case the visited component corresponds to a snapshot, the algorithm expands the traversal T at depth (n + 1) with each vertex returned from the GetN eighbors function using the expand operator. Now, in case the component corresponds to a delta, then before fetching the neighborhood of a vertex, the function CheckBloomF ilter checks for the existence of that vertex in that delta by testing the corresponding Bloom filter. Now, in case of a positive response, the GetOperations returns all edge operations of a source vertex.

In case the component corresponds to a forward or backward time window, then the function GetOperationsT returns the edge operations belonging to a source vertex and having a timestamp that is either lower than t, or greater than or equal to t, respectively.

Next, for every retrieved edge operation , the algorithm gets the event and the id of the target vertex (lines [START_REF] Haeusler | Chronograph: A versioned tinkerpop graph database[END_REF][START_REF] Vijitbenjaronk | Scalable time-versioning support for property graph databases[END_REF][START_REF] Byun | Chronograph: Enabling temporal graph traversals for efficient information diffusion analysis over time[END_REF]. Note that functions f E , f G and α are defined in section III and T arget(x) returns the id of the target vertex of an edge x. In case of an addition (a), T is expanded at the depth (n + 1) with the target vertex (Line 22). Otherwise, that target vertex is removed from T using the shrink operator (Line 24). Finally, the select operator is used (Line 25) to filter every tuple u from T s.t. the condition d ∈ dom(u) does not hold. Indeed, this condition states that all returned tuples should represent a path of length d.

2) Range-based local queries: are similar to the pointbased local queries. While point-based queries take a time instant as an input, range queries take a time interval with which the validity intervals of the returned vertices and edges should overlap. Furthermore, we implemented a special type of range-based local queries that we refer to as time-increasing paths. For this type of temporal paths, every outgoing edge of a vertex should have occurred after the incoming edges to the same node. In the case of Thing'in, this type of temporal paths finds applicability in logistic chains. For example, a product starting from a given station can reach another station if there exists a sequential path representing product transfer between the stations.

3) Global queries: Point-based global queries retrieve the state of a sub-graph given the labels of the vertices, types of edges and a time instant at which all the returned vertices and edges must be valid. Similarly, range-based global queries retrieves a sub-graph that was valid during a time range meaning that the validity interval of the returned nodes and edges should intersect with the requested time interval. Note that, one can choose to return a full snapshot of the graph which translates to returning all the nodes and edges without any constraints on the nodes and edges. In the case of Mo.Di.Flu, a global query can recover the status of all the machines and their connections with other devices at a given time instant or follow their evolution during a time interval. Note that we omit the pseudo-code of the range-based point and global queries for the lack of space.

VI. EVALUATION

In this section, we present the evaluation of the overall performance of Clock-G. Our main goal is to validate that the δ-Copy+Log produces a compromise between the performances of traditional methods Copy+Log and Log. Another goal is to show that one can tune the performance of Clock-G by choosing the adequate configuration of the system parameters. Based on this evaluation, one should be able to configure the parameters of Clock-G in order to account for the threshold of accepted query latency and available storage resources. Furthermore, we want to compare Clock-G with a non-temporal graph database to highlight that available commercial systems are not optimized for handling temporal graphs.

A. Experimental setup

Machine configuration

The experiments were conducted on a single machine equipped with 32 Intel(R) Xeon(R) E5-2630L v3 1.80GHz CPUs, 264 GB memory, 1 TB SSD, running 64-bit Ubuntu 18.04.4 LTS with 5.0.0-23-generic Linux kernel. We use OpenJDK 11.0.9, Go 1.14.4, DSE 6.8.4, CQL spec 3.4.5 and Neo4j 4.4.

Datasets In order to validate the performance of the proposed methods, we conducted experiments on synthetic and real temporal graphs. Since the space reduction obtained from the δ-Copy+Log is strictly related to the elimination of redundant graph elements that exist across snapshots, we generated synthetic datasets by varying the probability of addition p a . Indeed, higher values of p a implies that graph elements will have longer validity duration, hence they will be more frequently copied across snapshots. That is, we generated three temporal graph datasets referred to as DS pa by choosing a value of p a in {0.9, 0.75, 0.6}.

Although Clock-G is introduced in this paper to answer the requirements of a specific use case, it can also be deployed for other categories of temporal graphs. Having this, we used different real-world datasets such as DBLP dataset (DS DBLP [START_REF] Kunegis | Konect: The koblenz network collection[END_REF], Stack overflow dataset (DS stack ) and Wiki talk dataset (DS wiki ) [START_REF] Wen | Efficiently answering span-reachability queries in large temporal graphs[END_REF]. We assume that these graphs are growth-only graphs in the sense that once an edge is added, it will not be deleted. To evaluate the time increasing paths, we used the CitiBike dataset7 (DS citi ) which includes information of bike trips between stations in New York city. We transformed 3 months of data into a series of timestamped graph updates.

We present some of the characteristics of the generated datasets in Table II where |V | refers to the total number of vertices, |E| refers to the total number of graph operations.

B. Space usage and query execution time

We evaluate the disk space usage and query execution time with different configurations by tuning the system parameters. We compute local queries, detailed in Section V-B1, by randomly choosing 1k vertices to be the starting nodes of the traversals. Global queries, detailed in Section V-B3, retrieve a snapshot of the graph that was valid at a requested time instant. It should be highlighted that time instants used in queries are uniformly chosen within the time span of the datasets in order to avoid a biased distribution that favors only time instants that are closer to checkpoints.

Comparison with state-of-the-art methods. We compare the results of the proposed method δ-Copy+Log with those of the traditional methods Copy+Log and Log. Now, the implementation of Copy+Log in Clock-G is fairly straightforward since it consists of setting parameter M to 1. However, the implementation of the Log method consists of creating time windows of size N that are not bounded by any checkpoint. That is, the evaluation of a query with a requested time instant t implies reading from time windows whose time intervals fall before or contains t. Figures 4a, 4b and 4c display the space usage, the execution time of 5-Hops and global queries on datasets DS 0,6 , DS 0,75 and DS 0,9 . Note that, we set the system parameters N and M to 10k and 12, respectively. The results are directly inline with previous findings on the apparent trade-off between the space usage and execution time of the Copy+Log and Log methods. Such that the Copy+Log results in a space usage that is 144 times higher than that resulting from the Log approach whereas it results in a query execution time of 5-Hop queries that is 433 times faster then that resulting from the Log approach. It is clear from the results that the proposed δ-Copy+Log method offers a compromise between the Log and Copy+Log as it reduces the storage obtained by the Copy+Log by a factor of 12 whereas it reduces the query execution time offered by the Log approach by a factor of 340. For the interest of space, we limit the discussion here to the results obtained from the evaluation on the DS 0.75 .

Validating the use of Bloom filters. As previously discussed, storing deltas instead of snapshots induces a query execution time overhead. Hence, we developed optimization techniques to reduce the induced query latency. We evaluated the execution time of queries with 3 methods namely: f-δ-CL, b-δ-CL and δ-CL. The f-δ-CL method, standing for forwardδ-Copy+Log, follows the same approach as the δ-Copy+Log with the difference of storing only forward time windows and deltas and omitting the use of Bloom filters. The b-δ-CL, standing for bloomed-δ-Copy+Log, consists of adding Bloom filters to the f-δ-CL. Finally, the δ-CL refers the δ-Copy+Log method, hence, consists of adding forward and backward time windows and deltas to the b-δ-CL. Indeed, comparing the aforementioned methods emphasizes the gain of adding Bloom filters and that of storing backward time windows and deltas, separately. Figure 5 shows the average execution time of traversal queries with a fixed depth equals to 8 on the dataset DS 0,6 while increasing the system parameter M from 1 to 12. Note that the system parameter N is set to 10k. It is clear that using the f-δ-CL significantly increases the execution time with the increase of M . Now, adding Bloom filters to the b-δ-CL method reduces the execution time as compared to the f-δ-CL s.t. the speedup can reach 52% for M = 12. Furthermore, adding forward and backward time windows and deltas to the δ-CL speeds up the traversals by a factor of 23% as compared to the b-δ-CL. The execution time overhead of the f-δ-CL is equal to 206% when the value of M is increased from 1 to 12. Indeed, this overhead is reduced to 12, 5% when using the δ-CL. The rest of evaluations depicted in this section are executed using the δ-CL method s.t. the f-δ-CL and b-δ-CL methods are used as proof-of-concept implementations and will not be further discussed.

Variation of N and M . We evaluate the disk space usage in function of system parameters N and M . Figure 6a shows the disk space usage of checkpoints for different configurations s.t. each configuration is set with a value of N in {10k, 100k, 250k} and a value of M in {1, . . . , 12}. We ingest the dataset DS 0,6 in Clock-G with every combination of the values of parameters N and M . It is notable that the smaller is the value of N , the higher is the space usage of checkpoints. Now, increasing M while fixing the value of N significantly reduces the space usage as compared to the Copy+Log method (corresponding to M = 1). Besides, the disk space gain obtained by increasing the value of M is more significant for smaller values of N which is intuitively justified by the fact that lower values of N cause the creation of more time windows. Consequently, a larger number of snapshots will be substituted by deltas which leads to a more significant overall space reduction as compared to that obtained with higher values of N . We also evaluate the variation of N and M on the execution time of 5-Hop and global queries with the same system configuration whose results are given in Figures 6b and6c. For these results, it is notable that the higher is the value of N , the higher is the execution time. That is, less checkpoints are created in configurations tuned with larger time windows (higher values of N ) which increases, in general, the duration between requested time instants and the time instant of the closest snapshots that are used as starting points for query evaluation. Fig. 9: Evaluation of the effect of varying the number of partitions and backend connector workers on the disk space usage and execution time of queries with N = 10K. The evaluation is conducted on synthetic datasets DS 0,6 , DS 0,75 and DS 0,9

Variation of p a and M . We study the effect of varying the system parameter M and the dataset characteristic p a on the disk space. Figure 7a displays the space usage occupied by the checkpoints of datasets DS 0,6 , DS 0,75 and DS 0,9 with different system configurations corresponding each to a value of M in {1, . . . 12}. The obtained results demonstrate that the space usage strictly decreases with the increase of the value of M . Besides, superior space gains are obtained for graphs with higher probability of additions. This is due to the fact that snapshots of such graphs are more space consuming which implies that replacing them with deltas emphasizes more significantly the space gain. We also evaluate the effect of varying p a and the system parameter M on the execution time of 5-Hop queries and Global queries. Figures 7b and7c show that the execution time of queries increases with the increase of parameter p a . That is, the average degree of a node increases with the value of p a which results in a higher number of computations to evaluate the result of a query.

Evaluation on real datasets. We evaluate the space gain obtained from ingesting real-world datasets following the δ-Copy+Log method. Figure 8a displays the disk space usage of checkpoints created by the ingestion of datasets DS stack , DS DBLP and DS wiki into Clock-G while increasing the value of the system parameter M from 1 to 12. It can be noticed that the δ-Copy+Log approach markedly reduces the space usage occupied by the dataset when increasing the value of M from 1 to 12. We also evaluate 5-Hop traversal and global queries on these real-world datasets. The obtained results, given in Figures 8b and8c, validate that our solution gives clearly good results as compared to the Copy+Log method such as it significantly reduces the space usage while adding a slight query execution time overhead.

Variation of the number of partitions and backend workers. We evaluate the space usage by changing the total number of partitions. As depicted in Section V-A3, we separate each graph element store into a number of partitions. It is clear from Figure 9a that the space gain decreases with the increase of the total number of partitions. Figure 9b and 9c validate that the query execution time is reduced with the increase of the number of backend connector workers. Indeed, this is due to the fact that fetching tasks are executed by a pool of backend workers in parallel.

Comparison with a non-temporal graph database We compare the performance of Clock-G with that of a commercial graph database Neo4j. That is, we developed a temporal layer on top of Neo4j to enable the storage and evaluation of temporal graphs. To add the validity intervals to the graph elements, we created for each node and relationship occurrence, two properties: tStart and tEnd to indicate the starting and ending time instants of the temporal validity interval of the occurrence. Furthermore, we added an index on the identifiers of nodes, properties tStart and tEnd of the nodes and edges to accelerate the traversal. We refer to the implementation without indexes as Neo4j and the one with the use of indexes as Neo4j i . We ingested the dataset DS citi in Clock-G, Neo4j, Neo4j i with a fixed batch size of 500 graph operations per batch. Then, we evaluated a time increasing path query for each node (station) of the graph and for each depth 1 → 8 and time range 1 hour → 8 hours.

Figures 10a and10b show the ingestion throughput and space usage of Clock-G, Neo4j, Neo4j i . It can be derived from the plots that Clock-G significantly outperforms Neo4j and Neo4j i . This difference in the ingestion throughput is due to the fact that performing deletes incur the update the property tEnd, which induces a read operation to match the graph element before setting the new property value. Another key factor is the parallelism of Clock-G. That is, a number of backend workers are delegated to batch each, in parallel, a partition of the received graph operations. However, inserting graph updates in parallel into Neo4j is not possible since the chronological order of the updates should be guaranteed.

Figures 10c and10d show the execution time of time increasing path queries while varying the depth and time range of the queries. It should be noted that for each depth and time range, we run the query on all the nodes of the graph and plot the average of the obtained results. It can be noticed from the plots that Clock-G outperforms Neo4j and Neo4j i such that the difference is more significant with the increase of the depth and time range of the query. Indeed, when evaluating a time range query in Clock-G, the search space is trimmed to a number of selected time windows whose time interval intersects with the time range of the query. Furthermore, backend connector workers compute the result of the query in parallel such that each worker computes a sub-result that contains vertices and edges belonging to its local partitions. This, however, is not possible with Neo4j and Neo4j i even when indexes are used to accelerate the traversals.

The results obtained from this experiment highlight the need to develop a graph management system with a native temporal support instead of using an existing non-temporal commercial system.

VII. CONCLUSION

In this paper, we introduced a temporal graph management system designed with a space-efficient storage technique in order to keep pace with the requirement of querying the history of the graphs managed by the platform Thing'in. Our proposed storage technique δ-Copy+Log differentiates from the Copy+Log by storing deltas instead of snapshots. Besides, we referred to forward and backward data storage and retrieval in order to accelerate the query evaluation time. We also provided a detailed description of the architecture of Clock-G and the special implementation of Bloom filters that permits the acceleration of traversal queries. We conducted an evaluation test on synthetic and real-world graphs that validate the efficiency of the δ-Copy+Log method as compared to traditional methods. The results demonstrate that our solution reduces significantly the space usage of the Copy+Log method and the execution time of the Log method, hence mitigates the space-execution time tradeoff limiting the efficiency of these methods. In a future perspective, we plan to integrate a temporal querying language into Clock-G. Despite the existing work on temporal query languages [START_REF] Snodgrass | Tsql2 language specification[END_REF]- [START_REF] Rizzolo | Temporal xml: modeling, indexing, and query processing[END_REF], this problem has not been fully addressed in the context of graph databases.

  maps a graph operation to its corresponding graph entity. • f T : Υ → D T maps a graph operation to its corresponding time instant. • f E : Υ → {a, d, u} maps a graph operation to an addition (a), deletion (d) or update (u).

Fig. 1 :

 1 Fig. 1: Example illustrating a temporal property graph and its representation based on the OPGM model. We used (a), (d), (u), (N ), (O) to denote addition, deletion, update of a dynamic property, normal and out-of-service, respectively

Fig. 2 :

 2 Fig. 2: The internals of the Copy+Log and δ-Copy+Log showing a time bucket (b 1 ) with M = 6, forward and backwards time windows (ω i ⇒ , ω i ⇐ ) , deltas (δ i ⇒ , δ i ⇐ ) and snapshot S i

Fig. 3 :

 3 Fig. 3: System architecture

Algorithm 1 : 5 for id ∈ ids do 6 for i ∈ nextV ertices do 7 if id corresponds to a snapshot then 8 neighbors← 10 else if id corresponds to a delta then 11 if 15 for ∈ ops do // Get event from operation 16 e 17 j

 156781011151617 N-Hop traversal Input: id of the source vertex s; Number of hops d; Time instant t Output: Traversal T 1 T ← InitBag(0, s);// Initialize traversal // Find checkpoints 2 ids ← GetCheckpointIDs(t); 3 for n ← 0, 1, 2, ..., (d -1) do 4 nextV ertices ← ϑ(π n (T )); GetN eighbors(i, id) for j ∈ neighbors do /CheckBloomFilters(i, id) then 12 ops ← GetOperations(i, id); 13 else 14 ops ← GetOperationsT (i, id, t); ← f E ( ); // Get target vertex from operation ← T arget(α(f G ( ))); d hops paths in Traversal 22 T ← σ d∈dom(u) (T );

Fig. 4 :Fig. 5 :

 45 Fig. 4: Comparison with state-of-the-art techniques

Fig. 6 : 6 (Fig. 7 :Fig. 8 :

 6678 Fig.6: Evaluation of the disk space usage and execution time of queries while varying the system's configuration parameter N . The evaluation is conducted on the synthetic dataset DS 0,6

Fig. 10 :

 10 Fig. 10: Evaluation of the ingestion throughput and space usage of Clock-G, Neo4j and Neo4j i

TABLE I :

 I Symbols and their descriptions used in the formalisation of the δ-Copy+Log approach

	Symbol	Description
	B	Sequence of time buckets
	b i	Time bucket
	Ω i	Sequence of time windows
	Γ i	Sequence of checkpoints
	ω i ⇒ , ω i ⇐ s i	Forward and Backward time window Snapshot
	δ i ⇒ , δ i

⇐ Forward and Backward delta M Number of time windows in a bucket N Number of graph operations in a time window s.t.:

TABLE II :

 II Characteristics of the generated graphs

	Dataset	|V |	|E|	pa	Time span (Days)
	DSp a	500K	10 M	0.9, 0.74, 0.6	116
	DS stack	2.6 M	63.4 M		2774
	DS DBLP	1.8 M	29.5 M		29930
	DS wiki	1.1 M	7.8 M		2320
	DS citi	1K	2.5M		90

https://www.thinginthefuture.com/

Orange is a French multinational telecommunication operator

https://bim2twin.eu/

https://neo4j.com/

https://symas.com/lmdb/

https://www.oracle.com/database/technologies/high-availability/rman.html

https://ride.citibikenyc.com/system-data