Compressing and Indexing Labeled Trees, with Applications.
In: Journal of the ACM, Jg. 57 (2009-11-01), Heft 1, S. 4-36
Online
academicJournal
Zugriff:
Consider an ordered, static tree T where each node has a label from alphabet Σ. Tree T may be of arbitrary degree and shape. Our goal is designing a compressed storage scheme of T that supports basic navigational operations among the immediate neighbors of a node (i.e. parent, ith child, or any child with some label, ߪ) as well as more sophisticated path-based search operations over its labeled structure. We present a novel approach to this problem by designing what we call the XBW-transform of the tree in the spirit of the well-knownBurrows-Wheeler transform for strings [1994]. TheXBW-transform uses path-sorting to linearize the labeled tree T into two coordinated arrays, one capturing the structure and the other the labels. For the first time, by using the properties of the XBW-transform, our compressed indexes go beyond the information-theoretic lower bound, and support navigational and pathsearch operations over labeled trees within (near-)optimal time bounds and entropy-bounded space. Our XBW-transform is simple and likely to spur new results in the theory of tree compression and indexing, as well as interesting application contexts. As an example, we use the XBW-transform to design and implement a compressed index for XML documents whose compression ratio is significantly better than the one achievable by state-of-the-art tools, and its query time performance is order of magnitudes faster. [ABSTRACT FROM AUTHOR]
Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Titel: |
Compressing and Indexing Labeled Trees, with Applications.
|
---|---|
Autor/in / Beteiligte Person: | FERRAGINA, PAOLO ; LUCCIO, FABRIZIO ; MANZINI, GIOVANNI ; MUTHUKRISHNAN, S. |
Link: | |
Zeitschrift: | Journal of the ACM, Jg. 57 (2009-11-01), Heft 1, S. 4-36 |
Veröffentlichung: | 2009 |
Medientyp: | academicJournal |
ISSN: | 0004-5411 (print) |
DOI: | 10.1145/1613676.1613680 |
Schlagwort: |
|
Sonstiges: |
|