Compressing and indexing labeled trees, with applications

Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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 signifi-cantly better than the one achievable by state-of-the-art tools, and its query time performance is order of magnitudes faster.

    Original languageEnglish (US)
    Article number4
    JournalJournal of the ACM
    Volume57
    Issue number1
    DOIs
    StatePublished - Nov 1 2009

    Keywords

    • Burrows-Wheeler transform
    • Labeled tree compression
    • Labeled tree indexing
    • Path searching
    • Tree navigation
    • XML compression
    • XML indexing

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Information Systems
    • Hardware and Architecture
    • Artificial Intelligence

    Fingerprint

    Dive into the research topics of 'Compressing and indexing labeled trees, with applications'. Together they form a unique fingerprint.

    Cite this