Distributed Compression of Graphical Data
Distributed Compression of Graphical Data
复制标题
图形数据的分布式压缩
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
V. Anantharam
中科院分区：
文献类型：
--
作者：
Payam Delgosha;V. Anantharam
与时间序列相比，图形数据是由图的节点和边索引的数据。诸如互联网、社交网络、基因组学和蛋白质组学之类的现代应用生成图形数据，通常是大规模的。大规模的数据需要压缩存储和后续处理。由于这些数据可能在不同的位置有多个组件，因此研究图形数据的分布式压缩也很重要。在本文中，我们推导出一个率区域，这是对应的Slepian-Wolf定理。当分布式图形数据的统计描述是两种类型之一时，我们表征率区域-标记稀疏Erdos-Renyi系综或标记配置模型。我们的结果是Bordenave和Caputo在稀疏图的局部弱极限研究中引入的熵概念的推广。
In contrast to time series, graphical data is data indexed by the nodes 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 is one of two types - a marked sparse Erdos-Renyi ensemble or a marked configuration model. 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.