跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.09842 · v1

Asymptotic Analysis of Data Deduplication Under a Constant Edit Model

恒定编辑模型下数据去重的渐近分析

首次提交 2026-11-07 02:26
版本更新 2026-11-07 02:26
雷达观测 2026-11-09 13:22
arXiv ↗PDF ↗

摘要

Data deduplication has become increasingly important in large-scale storage systems, driven by the rapid growth of digital data. By identifying and removing repeats in the data stream, deduplication saves storage space more efficiently than traditional compression methods. In this paper, we study the performance of variable-length deduplication and multi-chunk deduplication algorithms from an information-theoretic perspective, focusing on data streams where repeats are approximate rather than exact. We consider two probabilistic source models in which source strings consist of repeated blocks that are modified by either a constant number of substitution edits or burst-insertion edits per block, the latter capturing the localized edit patterns commonly observed in real-world data. For both models, we show that variable-length deduplication achieves asymptotically arbitrarily large compression ratios, and that multi-chunk deduplication achieves compression within a constant factor of the source entropy under mild conditions.

AI 论文解读

基于摘要 · 非全文审阅

该论文从信息论角度分析在重复块仅含少量替换或突发插入编辑的概率源模型下,变长去重与多块去重的渐近压缩性能。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-07 02:26 · 最新观测版本

Asymptotic Analysis of Data Deduplication Under a Constant Edit Model

Data deduplication has become increasingly important in large-scale storage systems, driven by the rapid growth of digital data. By identifying and removing repeats in the data stream, deduplication saves storage space more efficiently than traditional compression methods. In this paper, we study the performance of variable-length deduplication and multi-chunk deduplication algorithms from an information-theoretic perspective, focusing on data streams where repeats are approximate rather than exact. We consider two probabilistic source models in which source strings consist of repeated blocks that are modified by either a constant number of substitution edits or burst-insertion edits per block, the latter capturing the localized edit patterns commonly observed in real-world data. For both models, we show that variable-length deduplication achieves asymptotically arbitrarily large compression ratios, and that multi-chunk deduplication achieves compression within a constant factor of the source entropy under mild conditions.

查看此版本解读 →查看此版本原文 ↗