Incremental Updates on Compressed XML

Stefan Böttcher, Rita Hartel, Thomas Jacobs, Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceedingConference contribution


XML tree structures can be effectively compressed using straight-line grammars. It has been an open problem how to update straight-line grammars, while keeping them compressed. Therefore, the best previous known methods resort to periodic decompression followed by compression from scratch.The decompression step is expensive, potentially with exponential running time. We present a method that avoids this expensive step. Our method recompresses the updated grammar directly,without prior decompression; it thus greatly outperforms the decompress-compress approach, in terms of both space and time.Our experiments show that the obtained grammars are similar or even smaller than those of the decompress-compress method.
Original languageEnglish
Title of host publication2016 IEEE 32nd International Conference on Data Engineering (ICDE)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1026 - 1037
Number of pages12
ISBN (Print)978-1-5090-2020-1
Publication statusPublished - May 2016
Event2016 IEEE 32nd International Conference on Data Engineering - Helsinki, Finland
Duration: 16 May 201620 May 2016


Conference2016 IEEE 32nd International Conference on Data Engineering
Abbreviated titleICDE 2016
Internet address

Fingerprint Dive into the research topics of 'Incremental Updates on Compressed XML'. Together they form a unique fingerprint.

Cite this