Distributed Compression of Graphical Data

DOI10.1109/TIT.2021.3129189zbMATH Open1495.94027arXiv1802.07446OpenAlexW3217727316MaRDI QIDQ5080002

Payam Delgosha, Venkat Anantharam

Publication date: 30 May 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In contrast to time series, graphical data is data indexed by the vertices and edges of a graph. Modern applications such as the internet, social networks, genomics and proteomics generate graphical data, often at large scale. The large scale argues for the need to compress such data for storage and subsequent processing. Since this data might have several components available in different locations, it is also important to study distributed compression of graphical data. In this paper, we derive a rate region for this problem which is a counterpart of the Slepian-Wolf theorem. We characterize the rate region when the statistical description of the distributed graphical data can be modeled as being one of two types - as a member of a sequence of marked sparse Erdos-Renyi ensembles or as a member of a sequence of marked configuration model ensembles. Our results are in terms of a generalization of the notion of entropy introduced by Bordenave and Caputo in the study of local weak limits of sparse graphs. Furthermore, we give a generalization of this result for Erdos-Renyi and configuration model ensembles with more than two sources.

Full work available at URL: https://arxiv.org/abs/1802.07446

zbMATH Keywords

rate regioncounterpart of Slepian-Wolf theoremdistributed compression of graphical dataErdős-Rényi ensembles

Mathematics Subject Classification ID

Source coding (94A29)

Related Items (2)

Data reduction of large vector graphics ⋮ Title not available (Why is that?)

This page was built for publication: Distributed Compression of Graphical Data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080002)