← 研踪 PaperTrailarXiv: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
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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.
查看此版本解读 →查看此版本原文 ↗