Data Deduplication With Random Substitutions
Data Deduplication With Random Substitutions
复制标题
DOI：
10.1109/tit.2022.3176778
复制
发表时间：
2021-07
影响因子：
2.5
通讯作者：
Hao Lou;Farzad Farnoud
中科院分区：
文献类型：
--
作者：
Hao Lou;Farzad Farnoud
重复数据消除通过识别和删除数据流中的重复项来节省存储空间。与传统的压缩方法相比，重复数据删除方案的计算效率更高，因此在大规模存储系统中得到了广泛的应用。在这篇文章中，我们提供了一个信息论分析的重复数据删除算法的性能，其中重复不准确的数据流。我们引入了一个源模型，其中考虑了概率替换。更准确地说，用给定的编辑概率替换重复字符串中的每个符号。研究了定长方案和变长方案中的重复数据删除算法。固定长度的重复数据删除算法不适合于所提出的源模型，因为它没有考虑编辑概率。对于已知模型参数的特定类型的源模型，提出了两种改进，并证明了它们在恒定的最优系数范围内的性能。我们还研究了传统的可变长度重复数据删除算法，结果表明，随着源熵变小，压缩字符串的大小相对于未压缩字符串的长度消失，从而导致较高的压缩比。
Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios.