Succinct representation of labeled trees

DOI10.1016/J.TCS.2014.10.006MaRDI QIDQ476876zbMATHOpenAlexFDO

Authors Dekel Tsur

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.6039

zbMATH Keywords

succinct data structureslabeled trees

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We give a representation for labeled ordered trees that supports labeled queries such as finding the i-th ancestor of a node with a given label. Our representation is succinct, namely the redundancy is small-o of the optimal space for storing the tree. This improves the representation of He et al. which is succinct unless the entropy of the labels is small.

Recommendations

• A Framework for Succinct Labeled Ordinal Trees over Large Alphabets
• A framework for succinct labeled ordinal trees over large alphabets
• Succinct representations of ordinal trees
• Ultra-succinct representation of ordered trees
• Succinct Representation of Labeled Graphs

Cites work

• A Framework for Succinct Labeled Ordinal Trees over Large Alphabets
• A Uniform Approach Towards Succinct Representation of Trees
• Adaptive searching in succinctly encoded binary relations and tree-structured documents
• Compressing and indexing labeled trees, with applications
• Fully functional static and dynamic succinct trees
• New lower and upper bounds for representing sequences
• Orderly Spanning Trees with Applications
• Representing trees of higher degree
• Succinct ordinal trees with level-ancestor queries
• Succinct representation of balanced parentheses and static trees
• Succinct representations of permutations and functions

Cited in

(16)

• LATIN 2004: Theoretical Informatics
• A uniform paradigm to succinctly encode various families of trees
• Succinct representation of labeled graphs
• Tradeoff between label space and auxiliary space for representation of equivalence classes
• Short Labels by Traversal and Jumping
• scientific article; zbMATH DE number 7561422 (Why is no real title available?)
• Tree path majority data structures
• Path queries on functions
• Reduced representations of rooted trees.
• Representation of ordered trees with a given degree distribution
• Short Transitive Signatures for Directed Trees
• Succinct data structure for dynamic trees with faster queries
• A framework for succinct labeled ordinal trees over large alphabets
• A Uniform Approach Towards Succinct Representation of Trees
• Succinct Representation of Labeled Graphs
• Succinct data structures for nearest colored node in a tree

This page was built for publication: Succinct representation of labeled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476876)