File updates under random/arbitrary insertions and deletions

Qiwen Wang; Viveck Cadambe; Sidharth Jaggi; Moshe Schwartz; Muriel Médard

doi:10.1109/ITW.2015.7133118

File updates under random/arbitrary insertions and deletions

Qiwen Wang
, Viveck Cadambe
, Sidharth Jaggi
, Moshe Schwartz
, Muriel Médard

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

4 Citations (Scopus)

Abstract

A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.

Original language	English
Title of host publication	2015 IEEE Information Theory Workshop, ITW 2015
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
ISBN (Electronic)	9781479955268
DOIs	https://doi.org/10.1109/ITW.2015.7133118
Publication status	Published - 24 Jun 2015
Event	2015 IEEE Information Theory Workshop, ITW 2015 - Jerusalem, Israel Duration: 26 Apr 2015 → 1 May 2015

Publication series

Name	2015 IEEE Information Theory Workshop, ITW 2015

Conference

Conference	2015 IEEE Information Theory Workshop, ITW 2015
Country/Territory	Israel
City	Jerusalem
Period	26/04/15 → 1/05/15

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Access to Document

10.1109/ITW.2015.7133118

Handle.net

Persistent link

Cite this

@inproceedings{a46f5fcf7e4e4558aa5568200e21e601,

title = "File updates under random/arbitrary insertions and deletions",

abstract = "A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.",

author = "Qiwen Wang and Viveck Cadambe and Sidharth Jaggi and Moshe Schwartz and Muriel M{\'e}dard",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 2015 IEEE Information Theory Workshop, ITW 2015 ; Conference date: 26-04-2015 Through 01-05-2015",

year = "2015",

month = jun,

day = "24",

doi = "10.1109/ITW.2015.7133118",

language = "English",

series = "2015 IEEE Information Theory Workshop, ITW 2015",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

booktitle = "2015 IEEE Information Theory Workshop, ITW 2015",

address = "United States",

}

Wang, Q, Cadambe, V, Jaggi, S, Schwartz, M & Médard, M 2015, File updates under random/arbitrary insertions and deletions. in 2015 IEEE Information Theory Workshop, ITW 2015., 7133118, 2015 IEEE Information Theory Workshop, ITW 2015, Institute of Electrical and Electronics Engineers (IEEE), 2015 IEEE Information Theory Workshop, ITW 2015, Jerusalem, Israel, 26/04/15. https://doi.org/10.1109/ITW.2015.7133118

File updates under random/arbitrary insertions and deletions. / Wang, Qiwen; Cadambe, Viveck; Jaggi, Sidharth et al.
2015 IEEE Information Theory Workshop, ITW 2015. Institute of Electrical and Electronics Engineers (IEEE), 2015. 7133118 (2015 IEEE Information Theory Workshop, ITW 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - File updates under random/arbitrary insertions and deletions

AU - Wang, Qiwen

AU - Cadambe, Viveck

AU - Jaggi, Sidharth

AU - Schwartz, Moshe

AU - Médard, Muriel

PY - 2015/6/24

Y1 - 2015/6/24

N2 - A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.

AB - A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.

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

U2 - 10.1109/ITW.2015.7133118

DO - 10.1109/ITW.2015.7133118

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:84938942101

T3 - 2015 IEEE Information Theory Workshop, ITW 2015

BT - 2015 IEEE Information Theory Workshop, ITW 2015

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 2015 IEEE Information Theory Workshop, ITW 2015

Y2 - 26 April 2015 through 1 May 2015

ER -

File updates under random/arbitrary insertions and deletions

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this