Local Decoding and Update of Compressed Data

Shashank Vatedka; Aslan Tchamkerten

doi:10.1109/ISIT.2019.8849634

Local Decoding and Update of Compressed Data

Shashank Vatedka
, Aslan Tchamkerten

Telecom Paris

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.

Original language	English
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	572-576
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849634
Publication status	Published - 1 Jul 2019
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: 7 Jul 2019 → 12 Jul 2019

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2019-July
ISSN (Print)	2157-8095

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	7/07/19 → 12/07/19

Access to Document

10.1109/ISIT.2019.8849634

Cite this

Vatedka, S., & Tchamkerten, A. (2019). Local Decoding and Update of Compressed Data. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 572-576). Article 8849634 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849634

@inproceedings{db142e53d43d4ec1b0a6c025153ee707,

title = "Local Decoding and Update of Compressed Data",

abstract = "In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.",

author = "Shashank Vatedka and Aslan Tchamkerten",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

day = "1",

doi = "10.1109/ISIT.2019.8849634",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "572--576",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

}

Vatedka, S & Tchamkerten, A 2019, Local Decoding and Update of Compressed Data. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849634, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 572-576, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/07/19. https://doi.org/10.1109/ISIT.2019.8849634

Local Decoding and Update of Compressed Data. / Vatedka, Shashank; Tchamkerten, Aslan.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 572-576 8849634 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Local Decoding and Update of Compressed Data

AU - Vatedka, Shashank

AU - Tchamkerten, Aslan

PY - 2019/7/1

Y1 - 2019/7/1

N2 - In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.

AB - In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.

UR - https://www.scopus.com/pages/publications/85073166363

U2 - 10.1109/ISIT.2019.8849634

DO - 10.1109/ISIT.2019.8849634

M3 - Conference contribution

AN - SCOPUS:85073166363

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 572

EP - 576

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

Local Decoding and Update of Compressed Data

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this