StarZIP: Streaming Graph Compression Technique for Data Archiving

The size of a streaming graph is possibly unbounded, and it is updated by a continuous sequence of edges over time. Due to numerous types of real-world interactions, the nature of edge arrival in a streaming graph is dynamic and holds different types of temporal subgraphs, such as stars, bipartite forms, cliques, and chains. The most current techniques find such subgraphs in each snapshot of a dynamic graph and use a dictionary or hash-based summary to compress the graph before applying a stitching technique to demonstrate its temporal behavior. However, it remains difficult to discover those subgraph structures from the continuous stream of edges found in large and rapidly changing dynamic graphs. In this paper, we propose a streaming graph compression algorithm, StarZIP, that uses a new encoding scheme. Our motivational factor is real-world graphs that contain an overwhelmingly large number of stars and a few other structures. We have observed that all subgraph structures can be represented as star-shaped subgraphs. Moreover, the star-shaped representation can easily be arranged in the form of an inverted index, which enables the application of different inverted list encoding techniques for compression. Therefore, we shatter a graph into a uniform representation of stars to compress it. The evaluation of StarZIP on real-world datasets shows that our proposed system reduced the size of a highly dense graph to 60 times less than its original size. Moreover, the experimental results indicate that StarZIP compression is 4 times better than the state-of-the-art techniques.