On Lossy Compression of Directed Graphs
On Lossy Compression of Directed Graphs
复制标题
关于有向图的有损压缩
DOI：
--
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
O. Shayevitz
中科院分区：
文献类型：
--
作者：
R. Bustin;O. Shayevitz
由Csiszár和Körner提出的类型方法是用于开发和分析有限字母表上数据序列的基本属性和约束的核心工具。使用这些工具考虑的一个中心问题是数据压缩，特别是有损数据压缩。在这项工作中，我们考虑这个问题，但是，而不是序列的数据，我们考虑有向图。我们表明，给定一个更自然的失真措施，拟合的数据结构的有向图，类型的方法不能应用。所建议的失真度量旨在保持有向图的局部结构。我们建立在最近的工作Barvinok和扩展的方法类型的二维设置有向图。我们看到，这种延伸在许多方面都是很自然的。鉴于此扩展，我们提供了一个下限和上限的率失真问题的有损压缩的失真措施。
The method of types presented by Csiszár and Körner is a central tool used to develop and analyze the basic properties and constraints on sequences of data over finite alphabets. A central problem considered using these tools is that of data compression, and specifically lossy data compression. In this work we consider this very problem, however, instead of sequences of data we consider directed graphs. We show that given a more natural distortion measure, fitting the data structure of a directed graph, the method of types cannot be applied. The suggested distortion measure aims to preserves the local structure of a directed graph. We build on the recent work of Barvinok and extend the method of types to the two dimensional setting of directed graphs. We see that the extension is quite natural in many ways. Given this extension we provide a lower and upper bound on the rate-distortion problem of lossy compression given the suggested distortion measure.