text: We give a succinct data-structure that stores a tree with color for each node, and allows finding, given a node x and a color alpha, the nearest node to x with color alpha. This results improves the O(n log n)-bits structure of [CPM 2016].
  @cite_14: We consider succinct or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static ordinal trees, that is, arbitrary static rooted trees where the children of each node are ordered. The set of operations is essentially the union of the sets of operations supported by previous succinct representations [Jacobson 1989; Munro and Raman 2001; 1999] to which we add the level-ancestor operation.Our representation takes 2n p o(n) bits to represent an n-node tree, which is within o(n) bits of the information-theoretic minimum, and supports all operations in O(1) time on the RAM model. These operations also provide a mapping from the n nodes of the tree onto the integers 1, …, n . In addition to the existing motivations for studying such data structures, we are motivated by the problem of representing XML documents compactly so that XPath queries can be supported efficiently.
  @cite_7: 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-known Burrows-Wheeler transform for strings [1994]. The XBW-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 path-search 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.
  @cite_8: 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 (ISAAC 2012) 8 which is succinct only when the entropy of the labels is ω ( 1 ) .
  @cite_6: The methods most heavily used by search engines to answer conjunctive queries on binary relations (such as one associating keywords with web-pages) are based on computing the intersection of postings lists stored as sorted arrays and using variants of binary search. We show that a succinct representation of the binary relation permits much better results, while using less space than traditional methods. We apply our results not only to conjunctive queries on binary relations, but also to queries on semi-structured documents such as XML documents or file-system indexes, using a variant of an adaptive algorithm used to solve conjunctive queries on binary relations.
  @cite_19: We start a systematic study of data structures for the nearest colored node problem on trees. Given a tree with colored nodes and weighted edges, we want to answer queries (v,c) asking for the nearest node to node v that has color c. This is a natural generalization of the well-known nearest marked ancestor problem. We give an O(n)-space O(log log n)-query solution and show that this is optimal. We also consider the dynamic case where updates can change a node's color and show that in O(n) space we can support both updates and queries in O(log n) time. We complement this by showing that O(polylog n) update time implies Omega(log n log log n) query time. Finally, we consider the case where updates can change the edges of the tree (link-cut operations). There is a known (top-tree based) solution that requires update time that is roughly linear in the number of colors. We show that this solution is probably optimal by showing that a strictly sublinear update time implies a strictly subcubic time algorithm for the classical all pairs shortest paths problem on a general graph. We also consider versions where the tree is rooted, and the query asks for the nearest ancestor descendant of node v that has color c, and present efficient data structures for both variants in the static and the dynamic setting.
  @cite_16: We consider succinct representations of labeled ordinal trees that support a rich set of operations. Our new representations support a much broader collection of operations than previous work. In our approach, labels of nodes are stored in a preorder label sequence, which can be compressed using any succinct representation of strings that supports @math access , @math rank and @math select operations. Thus, we present a framework for succinct representations of labeled ordinal trees that is able to handle large alphabets. This answers an open problem presented by , which asks for representations of labeled ordinal trees that remain space-efficient for large alphabets. We further extend our work and present the first succinct representations for dynamic labeled ordinal trees that support several label-based operations including finding the level ancestor with a given label.
  @cite_10: 
  @cite_17: 
summary: Several papers studied data-structures for storing colored trees with support for various queries @cite_14 @cite_6 @cite_7 @cite_16 @cite_8 @cite_17 @cite_10 . In particular, the problem of finding the nearest ancestor with color @math was considered in @cite_14 @cite_16 @cite_8 @cite_17 @cite_10 . In order to solve the nearest colored node problem, we combine techniques from the papers above and from @cite_19 .