Local Decode and Update for Big Data Compression

Vatedka, Shashank and Tchamkerten, Aslan (2020) Local Decode and Update for Big Data Compression. IEEE Transactions on Information Theory, 66 (9). pp. 5790-5805. ISSN 0018-9448

Text
Local_Decode_and_Update_for_Big_Data_Compression.pdf - Published Version
Available under License Creative Commons Attribution.
Download (1MB)

Abstract

This paper investigates data compression that simultaneously allows local decoding and local update. The main result is a universal compression scheme for memoryless sources with the following features. The rate can be made arbitrarily close to the entropy of the underlying source, contiguous fragments of the source can be recovered or updated by probing or modifying a number of codeword bits that is on average linear in the size of the fragment, and the overall encoding and decoding complexity is quasilinear in the blocklength of the source. In particular, the local decoding or update of a single message symbol can be performed by probing or modifying on average a constant number of codeword bits. This latter part improves over previous best known results for which local decodability or update efficiency grows logarithmically with blocklength. © 1963-2012 IEEE.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Vatedka, Shashank	https://orcid.org/0000-0003-2384-9392

Item Type:

Article

Additional Information:

Manuscript received September 14, 2019; accepted March 7, 2020. Date of publication June 11, 2020; date of current version August 18, 2020. This work was supported by the Nokia Bell Labs France within the Framework Computation over Encoded Data with Applications to Large Scale Storage. This article was presented in part at the 2019 IEEE International Symposium on Information Theory. (Corresponding author: Shashank Vatedka.) Shashank Vatedka is with the Department of Electrical Engineering, Indian Institute of Technology, Hyderabad 502285, India (e-mail: shashankvatedka@ ee.iith.ac.in).

Uncontrolled Keywords:

Codeword; Encoding and decoding; Memoryless source; Quasi-linear; Universal compression

Subjects:

Electrical Engineering

Divisions:

Department of Electrical Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

23 Nov 2022 09:35

Last Modified:

23 Nov 2022 09:35