Home // ALLDATA 2021, The Seventh International Conference on Big Data, Small Data, Linked Data and Open Data // View article

On Compressing Time-Evolving Networks

Authors:
Sudhindra Gopal Krishna
Sridhar Radhakrishnan
Michael Nelson
Amlan Chatterjee
Chandra Shekaran

Keywords: Compression, Network Science, Time-Evolving, Queries, Graphs.

Abstract:
A graph G = (V, E) is an ordered tuple where V is a non-empty set of elements called vertices (nodes), and E is a set of an unordered pair of elements called links (edges), and a time-evolving graph is a change in the states of the edges over time. Extremely large graphs are such graphs that do not fit into the main memory. One way to address the issue is to compress the data for storage. The challenge with compressing data is to allow for queries on the compressed data itself at the time of computation without incurring overhead storage costs. Our previous work on Compressed Binary Trees (CBT), which was shown to be efficient both in time and space, compresses each node and its neighbors (termed as row-by-row compression). This paper first provides encoding to store the arrays in the Compressed Sparse Row (CSR) data structure and extends the encoding to store time-evolving graphs in the form of CSR. The encoding also enables accessing a node without decompressing the entire structure, meaning the data structure is queryable. We have performed an extensive evaluation of our structures on synthetic and real networks. Our evaluations include time/space comparison with both time-evolving compressed binary tree and ckd data structures, including the querying times.

Pages: 43 to 48

Copyright: Copyright (c) IARIA, 2021

Publication date: April 18, 2021

Published in: conference

ISSN: 2519-8386

ISBN: 978-1-61208-842-6

Location: Porto, Portugal

Dates: from April 18, 2021 to April 22, 2021