A Universal Low Complexity Compression Algorithm for Sparse Marked Graphs
A Universal Low Complexity Compression Algorithm for Sparse Marked Graphs
复制标题
DOI：
10.1109/isit44484.2020.9174300
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Payam Delgosha;V. Anantharam
中科院分区：
文献类型：
--
作者：
Payam Delgosha;V. Anantharam
许多现代应用程序涉及访问和处理图形数据，即由图形自然索引的数据。例子来自互联网图表、社交网络、基因组学和蛋白质组学以及其他来源。这种数据的典型的大尺寸激励寻求有效的方法来对其进行压缩和解压缩。目前的压缩方法通常是针对特定的模型，或不提供理论保证。在本文中，我们介绍了一种低复杂度的无损压缩算法的稀疏标记图，即由稀疏图索引的图形数据，这是能够普遍实现精确定义的意义上的最佳压缩率。为了定义普适性，我们采用了局部弱收敛的框架，它允许人们理解图的随机过程的概念。此外，我们研究了我们的算法的性能，通过一些实验结果的合成和真实世界的数据。
Many modern applications involve accessing and processing graphical data, i.e. data that is naturally indexed by graphs. Examples come from internet graphs, social networks, genomics and proteomics, and other sources. The typically large size of such data motivates seeking efficient ways for its compression and decompression. The current compression methods are usually tailored to specific models, or do not provide theoretical guarantees. In this paper, we introduce a low–complexity lossless compression algorithm for sparse marked graphs, i.e. graphical data indexed by sparse graphs, which is capable of universally achieving the optimal compression rate in a precisely defined sense. In order to define universality, we employ the framework of local weak convergence, which allows one to make sense of a notion of stochastic processes for graphs. Moreover, we investigate the performance of our algorithm through some experimental results on both synthetic and real–world data.