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).