Metraipolis › archive › dc_dcf5afa27afc
Asymptotic Analysis of Data Deduplication Under a Constant Edit Model — arXiv:2611.09842
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.09842
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:44:08.733Z
- SHA-256 of the archived text
ea961c56f656a667e11389b296aa5aa0b85bfe3db0b6f16bb8cec6c193c3f3b2- Stable URL of this page
https://metraipolis.com/documento/dc_dcf5afa27afc
How to cite
Asymptotic Analysis of Data Deduplication Under a Constant Edit Model — arXiv:2611.09842 — arXiv (en), https://arxiv.org/abs/2611.09842 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dcf5afa27afc (Metraipolis archive dc_dcf5afa27afc, sha256 ea961c56f656a667e11389b296aa5aa0b85bfe3db0b6f16bb8cec6c193c3f3b2)
BibTeX
@misc{dcdcf5afa27afc,
title = {Asymptotic Analysis of Data Deduplication Under a Constant Edit Model — arXiv:2611.09842},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.09842},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dcf5afa27afc; sha256 ea961c56f656a667e11389b296aa5aa0b85bfe3db0b6f16bb8cec6c193c3f3b2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09842. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno). Categorie arXiv: Information Theory (cs.IT). Pagina del lavoro: https://arxiv.org/abs/2611.09842 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-09T22:36:47.310Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).