O (log log n) Worst-Case Local Decoding and Update Efficiency for Data Compression

Vatedka, Shashank and Chandar, Venkat and Tchamkerten, Aslan (2020) O (log log n) Worst-Case Local Decoding and Update Efficiency for Data Compression. In: 2020 IEEE International Symposium on Information Theory, ISIT 2020, 21 July 2020through 26 July 2020, Los Angeles.

[img] Text
Available under License Creative Commons Attribution.

Download (364kB)


This paper addresses the problem of data compression with local decoding and local update. A compression scheme has worst-case local decoding dwc if any bit of the raw file can be recovered by probing at most dwc bits of the compressed sequence, and has update efficiency of uwc if a single bit of the raw file can be updated by modifying at most uwc bits of the compressed sequence. This article provides an entropy-achieving compression scheme for memoryless sources that simultaneously achieves O (log log n) local decoding and update efficiency. Key to this achievability result is a novel succinct data structure for sparse sequences which allows efficient local decoding and local update.Under general assumptions on the local decoder and update algorithms, a converse result shows that the maximum of dwc and uwc must grow as (log log n). © 2020 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Vatedka, Shashankhttps://orcid.org/0000-0003-2384-9392
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Achievability; Compression scheme; Memoryless source; Single-bit; Sparse sequences; Succinct data structure; Update algorithms
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 16 Nov 2022 05:40
Last Modified: 16 Nov 2022 05:40
URI: http://raiith.iith.ac.in/id/eprint/11282
Publisher URL: http://doi.org/10.1109/ISIT44484.2020.9173968
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 11282 Statistics for this ePrint Item