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

摘要

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).