Modeling sequence of snapshots in dynamic graph

Abstract

�2016 ACM. There is a significant research interest in representing evolving networks in the form of graph models. Most of the existing models use data structures to store sequence of snapshots, which are either historical or retrieved for processing purposes. Despite consuming minimal update time, these data structures induce storage redundancy, since consecutive snapshots share most of their nodes and edges in common. Compressed variants reduce this redundancy, but at the cost of increasing the update time, required to insert a new snapshot into the structure. So there is a tradeoff between storage and update time. In this paper we address the problem of storing sequence of snapshots in a compact manner while maintaining a very low update overhead. We minimize the update time by limiting the size of data that will undergo the update process. This is accomplished by separating the parts susceptible to change, from the other parts. Our experiments show that the proposed data structure achieves a compression, which is comparable to the state of the art methods, while offering an unprecedented low update overhead.