An ancestry labeling scheme labels the nodes of any tree in such a way that ancestry queries between any two nodes in a tree can be answered just by looking at their corresponding labels. The common measure to evaluate the quality of an ancestry labeling scheme is by its label size , that is the maximal number of bits stored in a label, taken over all @math -node trees. The design of ancestry labeling schemes finds applications in XML search engines. In the context of these applications, even small improvements in the label size are important. In fact, the literature about this topic is interested in the exact label size rather than just its order of magnitude. As a result, following the proposal of an original scheme of size @math bits, a considerable amount of work was devoted to improve the bound on the label size. The current state of the art upper bound is @math bits which is still far from the known @math lower bound. Moreover, the hidden constant factor in the additive @math term is large, which makes this term dominate the label size for typical current XML trees. In attempt to provide good performances for real XML data, we rely on the observation that the depth of a typical XML tree is bounded from above by a small constant. Having this in mind, we present an ancestry labeling scheme of size @math , for the family of trees with at most @math nodes and depth at most @math . In addition to our main result, we prove a result that may be of independent interest concerning the existence of a linear universal graph for the family of forests with trees of bounded depth.
Adjacency labeling schemes on trees were further investigated in an attempt to reduce the constant factor in the label size. In @cite_4 an adjacency labeling scheme using label size of @math is presented; and in @cite_9 the label size was further reduced to @math . This current state of the art bound implies the existence of a universal graph for the family of @math -node trees with @math nodes.
@cite_9 @cite_4
2025590344 1990376056
We consider the following problem. Given a rooted tree @math , label the nodes of @math in the most compact way such that, given the labels of two nodes @math and @math , one can determine in constant time, by looking only at the labels, whether @math is ancestor of @math . The best known labeling scheme is rather straightforward and uses labels of length at most @math bits each, where @math is the number of nodes in the tree. Our main result in this paper is a labeling scheme with maximum label length @math . Our motivation for studying this problem is enhancing the performance of web search engines. In the context of this application each indexed document is a tree, and the labels of all trees are maintained in main memory. Therefore even small improvements in the maximum label length are important. We consider the following problem. Give a rooted tree T, label the nodes of T in the most compact way such that given the labels of two nodes one can determine in constant time, by looking only at the labels, if one node is an ancestor of the other. The best known labeling scheme is rather straightforward and uses labels of size at most 2 log n, where n is the number of vertices In the tree. Our main result in this paper is a labeling scheme with maximum label size close to 3 2 log n. Our motivation for studying this problem is enhancing the performance of Web search engines. In the context of this application each indexed document is a tree and the labels of all trees are maintained in main memory. Therefore even small improvements in the maximum label size are important. There are no lower bounds known for this problem except for an obvious lower bound of log n that follows from the fact that different vertices must have different labels. The question whether one can find even shorter labels remains an intriguing open question.