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.

Text
O_log_log_n_Worst-Case_Local_Decoding_and_Update_Efficiency_for_Data_Compression.pdf
Available under License Creative Commons Attribution.
Download (364kB)

Abstract

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: