In this paper, we address the problem of evaluating historical queries on graphs. To this end, we investigate the use of graph deltas, i.e., a log of time-annotated graph operations. Our storage model maintains the current graph snapshot and the delta. We reconstruct past snapshots by applying appropriate parts of the graph delta on the current snapshot. Query evaluation proceeds on the reconstructed snapshots but we also propose algorithms based mostly on deltas for efficiency. We introduce various techniques for improving performance, including materializing intermediate snapshots, partial reconstruction and indexing deltas.
The most relevant to our work is perhaps the historical graph structure recently proposed in @cite_14 . The authors consider a sequence of graphs produced as the graph evolves over time. Since the graphs in the sequence are very similar to each other, they propose computing graph representatives by clustering similar graphs and then storing appropriate differences from these representatives, instead of storing all graphs. Our approach is different in that we want to support a broad range of historical queries, not just queries that involve a single snapshot graph.
@cite_14
2154875162
In many applications, information is best represented as graphs. In a dynamic world, information changes and so the graphs representing the information evolve with time. We propose that historical graph-structured data be maintained for analytical processing. We call a historical evolving graph sequence an EGS. We observe that in many applications, graphs of an EGS are large and numerous, and they often exhibit much redundancy among them. We study the problem of efficient query processing on an EGS and put forward a solution framework called FVF. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in EGS query processing.