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 f...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8649624/ |
| _version_ | 1819291243658608640 |
|---|---|
| author | Batjargal Dolgorsuren Kifayat Ullah Khan Mostofa Kamal Rasel Young-Koo Lee |
| author_facet | Batjargal Dolgorsuren Kifayat Ullah Khan Mostofa Kamal Rasel Young-Koo Lee |
| author_sort | Batjargal Dolgorsuren |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-24T03:35:33Z |
| format | Article |
| id | doaj.art-5334ee8927354e9a89c35183c4d4141f |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-24T03:35:33Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-5334ee8927354e9a89c35183c4d4141f2022-12-21T17:17:04ZengIEEEIEEE Access2169-35362019-01-017380203803410.1109/ACCESS.2019.28999218649624StarZIP: Streaming Graph Compression Technique for Data ArchivingBatjargal Dolgorsuren0https://orcid.org/0000-0002-8795-2762Kifayat Ullah Khan1Mostofa Kamal Rasel2Young-Koo Lee3Department of Computer Science and Engineering, Kyung Hee University, Seoul, South KoreaDepartment of Computer Science, National University of Computer and Emerging Sciences, Islamabad, PakistanDepartment of Computer Science and Engineering, Kyung Hee University, Seoul, South KoreaDepartment of Computer Science and Engineering, Kyung Hee University, Seoul, South KoreaThe 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.https://ieeexplore.ieee.org/document/8649624/Encoding schemegraph compressionstreaming graphstar structure |
| spellingShingle | Batjargal Dolgorsuren Kifayat Ullah Khan Mostofa Kamal Rasel Young-Koo Lee StarZIP: Streaming Graph Compression Technique for Data Archiving IEEE Access Encoding scheme graph compression streaming graph star structure |
| title | StarZIP: Streaming Graph Compression Technique for Data Archiving |
| title_full | StarZIP: Streaming Graph Compression Technique for Data Archiving |
| title_fullStr | StarZIP: Streaming Graph Compression Technique for Data Archiving |
| title_full_unstemmed | StarZIP: Streaming Graph Compression Technique for Data Archiving |
| title_short | StarZIP: Streaming Graph Compression Technique for Data Archiving |
| title_sort | starzip streaming graph compression technique for data archiving |
| topic | Encoding scheme graph compression streaming graph star structure |
| url | https://ieeexplore.ieee.org/document/8649624/ |
| work_keys_str_mv | AT batjargaldolgorsuren starzipstreaminggraphcompressiontechniquefordataarchiving AT kifayatullahkhan starzipstreaminggraphcompressiontechniquefordataarchiving AT mostofakamalrasel starzipstreaminggraphcompressiontechniquefordataarchiving AT youngkoolee starzipstreaminggraphcompressiontechniquefordataarchiving |