Change search
ReferencesLink to record
Permanent link

Direct link
Efficient Compression Algorithm For File Updates Under Random Insertions And Deletions
KTH, School of Electrical Engineering (EES).
KTH, School of Electrical Engineering (EES), Communication Theory.ORCID iD: 0000-0002-7926-5081
2016 (English)In: 2016 IEEE INFORMATION THEORY WORKSHOP (ITW), IEEE, 2016Conference paper (Refereed)
Abstract [en]

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 [1]. Therefore, when the insertion and deletion probabilities are small, the achievable rate is nearly optimal.

Place, publisher, year, edition, pages
IEEE, 2016.
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-197034ISI: 000386639100088ISBN: 978-1-5090-1090-5OAI: oai:DiVA.org:kth-197034DiVA: diva2:1053097
Conference
IEEE Information Theory Workshop (ITW), SEP 11-14, 2016, Cambridge, ENGLAND
Note

QC 20161208

Available from: 2016-12-08 Created: 2016-11-28 Last updated: 2016-12-08Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Wang, QiwenSkoglund, Mikael
By organisation
School of Electrical Engineering (EES)Communication Theory
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

ReferencesLink to record
Permanent link

Direct link