XML compression via DAGs

Markus Lohrey, Sebastian Maneth, Eric Noeth

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

Abstract / Description of output

Unranked trees can be represented using their minimal dag (directed acyclic graph). For XML this achieves high compression ratios due to their repetitive mark up. Unranked trees are often represented through first child/next sibling (fcns) encoded binary trees. We study the difference in size (= number of edges) of minimal dag versus minimal dag of the fcns encoded binary tree. One main finding is that the size of the dag of the binary tree can never be smaller than the square root of the size of the minimal dag, and that there are examples that match this bound. We introduce a new combined structure, the hybrid dag, which is guaranteed to be smaller than (or equal in size to) both dags. Interestingly, we find through experiments that last child/previous sibling encodings are much better for XML compression via dags, than fcns encodings. This is because optional elements are more likely to appear towards the end of child sequences.
Original languageEnglish
Title of host publicationJoint 2013 EDBT/ICDT Conferences, ICDT '13 Proceedings, Genoa, Italy, March 18-22, 2013
PublisherACM
Pages69-80
Number of pages12
ISBN (Electronic)978-1-4503-1598-2
DOIs
Publication statusPublished - 2013

Fingerprint

Dive into the research topics of 'XML compression via DAGs'. Together they form a unique fingerprint.

Cite this