XML Tree Structure Compression

Sebastian Maneth, Nikolay Mihaylov, Sherif Sakr

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

Abstract

In an XML document a considerable fraction consists of markup, that is, begin and end-element tags describing the document's tree structure. XML compression tools such as XMill separate the tree structure from the data content and compress each separately. The main focus in these compression tools is how to group similar data content together prior to performing standard data compression such as gzip, bzip2, or ppm. In contrast, the focus of this paper is on compressing the tree structure part of an XML document. We use a known algorithm to derive a grammar representation of the tree structure which factors out the repetition of tree patterns. We then investigate several succinct binary encodings of these grammars. Our experiments show that we can be consistently smaller than the tree structure compression carried out by XMill, using the same backend compressors as XMill on our encodings. However, the most surprising result is that our own Huffman-like encoding of the grammars (without any backend compressor whatsoever) consistently outperforms XMill with gzip backend. This is of particular interest because our Huffman-like encoding can be queried without prior decompression. To the best of our knowledge this offers the smallest queriable XML tree structure representation currently available.
Original languageEnglish
Title of host publication19th International Workshop on Database and Expert Systems Applications (DEXA 2008), 1-5 September 2008, Turin, Italy
Pages243-247
Number of pages5
DOIs
Publication statusPublished - Sep 2008

Fingerprint Dive into the research topics of 'XML Tree Structure Compression'. Together they form a unique fingerprint.

Cite this