File updates under random/arbitrary insertions and deletions
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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100953 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826194894036664320 |
|---|---|
| author | Wang, Qiwen Cadambe, Viveck Jaggi, Sidharth Schwartz, Moshe Medard, Muriel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Wang, Qiwen Cadambe, Viveck Jaggi, Sidharth Schwartz, Moshe Medard, Muriel |
| author_sort | Wang, Qiwen |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:03:31Z |
| format | Article |
| id | mit-1721.1/100953 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:03:31Z |
| publishDate | 2016 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1009532022-09-30T18:39:11Z File updates under random/arbitrary insertions and deletions Wang, Qiwen Cadambe, Viveck Jaggi, Sidharth Schwartz, Moshe Medard, Muriel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel 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. National Science Foundation (U.S.) (Grant CCF-1409228) 2016-01-20T17:33:37Z 2016-01-20T17:33:37Z 2015-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-5524-4 978-1-4799-5526-8 http://hdl.handle.net/1721.1/100953 Wang, Qiwen, Viveck Cadambe, Sidharth Jaggi, Moshe Schwartz, and Muriel Medard. “File Updates Under Random/arbitrary Insertions and Deletions.” 2015 IEEE Information Theory Workshop (ITW) (April 2015). https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/ITW.2015.7133118 Proceedings of the 2015 IEEE Information Theory Workshop (ITW) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Wang, Qiwen Cadambe, Viveck Jaggi, Sidharth Schwartz, Moshe Medard, Muriel File updates under random/arbitrary insertions and deletions |
| title | File updates under random/arbitrary insertions and deletions |
| title_full | File updates under random/arbitrary insertions and deletions |
| title_fullStr | File updates under random/arbitrary insertions and deletions |
| title_full_unstemmed | File updates under random/arbitrary insertions and deletions |
| title_short | File updates under random/arbitrary insertions and deletions |
| title_sort | file updates under random arbitrary insertions and deletions |
| url | http://hdl.handle.net/1721.1/100953 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT wangqiwen fileupdatesunderrandomarbitraryinsertionsanddeletions AT cadambeviveck fileupdatesunderrandomarbitraryinsertionsanddeletions AT jaggisidharth fileupdatesunderrandomarbitraryinsertionsanddeletions AT schwartzmoshe fileupdatesunderrandomarbitraryinsertionsanddeletions AT medardmuriel fileupdatesunderrandomarbitraryinsertionsanddeletions |