Generalized Deduplication: Bounds, Convergence, and Asymptotic Properties

TY - GEN

T1 - Generalized Deduplication: Bounds, Convergence, and Asymptotic Properties

AU - Vestergaard, Rasmus

AU - Zhang, Qi

AU - Lucani Rötter, Daniel Enrique

PY - 2019/12

Y1 - 2019/12

N2 - We study a generalization of deduplication, which enables lossless deduplication of highly similar data and show that classic deduplication with fixed chunk length is a special case. We provide bounds on the expected length of coded sequences for generalized deduplication and show that the coding has asymptotic near-entropy cost under the proposed source model. More importantly, we show that generalized deduplication allows for multiple orders of magnitude faster convergence than classic deduplication. This means that generalized deduplication can provide compression benefits much earlier than classic deduplication, which is key in practical systems. Numerical examples demonstrate our results, showing that our lower bounds are achievable, and illustrating the potential gain of using the generalization over classic deduplication. In fact, we show that even for a simple case of generalized deduplication, the gain in convergence speed is linear with the size of the data chunks.

AB - We study a generalization of deduplication, which enables lossless deduplication of highly similar data and show that classic deduplication with fixed chunk length is a special case. We provide bounds on the expected length of coded sequences for generalized deduplication and show that the coding has asymptotic near-entropy cost under the proposed source model. More importantly, we show that generalized deduplication allows for multiple orders of magnitude faster convergence than classic deduplication. This means that generalized deduplication can provide compression benefits much earlier than classic deduplication, which is key in practical systems. Numerical examples demonstrate our results, showing that our lower bounds are achievable, and illustrating the potential gain of using the generalization over classic deduplication. In fact, we show that even for a simple case of generalized deduplication, the gain in convergence speed is linear with the size of the data chunks.

UR - https://www.scopus.com/pages/publications/85074452918

U2 - 10.1109/GLOBECOM38437.2019.9014012

DO - 10.1109/GLOBECOM38437.2019.9014012

M3 - Article in proceedings

BT - 2019 IEEE Global Communications Conference, GLOBECOM 2019 - Proceedings

PB - IEEE

T2 - IEEE Global Communications (GLOBECOM 2019)

Y2 - 8 December 2019 through 12 December 2019

ER -