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

[img] 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 CreatorsORCiD
Vatedka, Shashankhttps://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
URI: http://raiith.iith.ac.in/id/eprint/11225
Publisher URL: https://doi.org/10.1109/TIT.2020.2999909
OA policy: https://v2.sherpa.ac.uk/id/publication/3480
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 11225 Statistics for this ePrint Item