Efficient Compression Algorithm For File Updates Under Random Insertions And Deletions
2016 (English)In: 2016 IEEE INFORMATION THEORY WORKSHOP (ITW), IEEE, 2016Conference paper (Refereed)
The problem of one-way file synchronization from the client to the data-center, namely, file updates, is studied. The problem is investigated in particular when an old version of a file which can be available at both client and data-center, is edited by the client to a new version. The edits are modeled as random insertions and deletions (InDels). Based on the updated and the previous version of the file, the client transmits a message to the data-center via a noiseless link, such that the datacenter can update the file. A dynamic-programming-run-lengthcoding (DP-RLC) scheme is proposed for the message encoding in this paper. The lower order terms of the achievable rate are computed explicitly. It is worth noting that these terms match the information-theoretic lower bound derived in our previous work . Therefore, when the insertion and deletion probabilities are small, the achievable rate is nearly optimal.
Place, publisher, year, edition, pages
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-197034ISI: 000386639100088ISBN: 978-1-5090-1090-5OAI: oai:DiVA.org:kth-197034DiVA: diva2:1053097
IEEE Information Theory Workshop (ITW), SEP 11-14, 2016, Cambridge, ENGLAND
QC 201612082016-12-082016-11-282016-12-08Bibliographically approved