  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.
