Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient compression algorithm for file updates under random insertions and deletions
KTH, School of Electrical Engineering (EES), Information Science and Engineering.
KTH, School of Electrical Engineering (EES), Information Science and Engineering.ORCID iD: 0000-0002-7926-5081
2016 (English)In: 2016 IEEE Information Theory Workshop, ITW 2016, IEEE, 2016, p. 434-438Conference paper, Published 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 data-center can update the file. A dynamic-programming-run-length-coding (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. © 2016 IEEE.

Place, publisher, year, edition, pages
IEEE, 2016. p. 434-438
Keywords [en]
Convolutional codes, Information theory, Compression algorithms, Data centers, File synchronization, Information-theoretic lower bounds, Lower order terms, Random insertions, Run-length coding, Dynamic programming
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-202292DOI: 10.1109/ITW.2016.7606871Scopus ID: 2-s2.0-84998813330ISBN: 9781509010905 (print)OAI: oai:DiVA.org:kth-202292DiVA, id: diva2:1075746
Conference
2016 IEEE Information Theory Workshop, ITW 2016, 11 September 2016 through 14 September 2016
Note

Conference Paper. QC 20170221

Available from: 2017-02-21 Created: 2017-02-21 Last updated: 2017-02-27Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Wang, QiwenSkoglund, Mikael
By organisation
Information Science and Engineering
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 22 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf