Modeling sequence of snapshots in dynamic graph

Zaki A. ; Attia M. ; Hegazy, Doaa ; Amin S. 


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.


Other data

Issue Date 9-May-2016
Journal ACM International Conference Proceeding Series 
URI http://research.asu.edu.eg/123456789/1025
ISBN 9781450340625
DOI http://api.elsevier.com/content/abstract/scopus_id/84998799641
197
09-11-May-2016
10.1145/2908446.2908483


Recommend this item

CORE Recommender
9
Views


Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.