### An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal PosetsAn Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

Access Restriction
Subscribed

 Author Fraigniaud, Pierre ♦ Korman, Amos Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Database ♦ XML search engine ♦ Graph decomposition ♦ Labeling scheme ♦ Poset ♦ Tree Abstract In this article, we solve the $\textit{ancestry}-labeling$ scheme problem, which aims at assigning the shortest possible labels (bit strings) to nodes of rooted trees, so ancestry queries between any two nodes can be answered by inspecting their assigned labels only. This problem was introduced more than 20 years ago by Kannan et al. [1988] and is among the most well-studied problems in the field of informative labeling schemes. We construct an ancestry-labeling scheme for $\textit{n}-node$ trees with label size log $_{2}n$ + $\textit{O}(log$ log $\textit{n})$ bits, thus matching the log $_{2}n$ + Ω(log log $\textit{n})$ bits lower bound given by Alstrup et al. [2003]. Our scheme is based on a simplified ancestry scheme that operates extremely well on a restricted set of trees. In particular, for the set of $\textit{n}-node$ trees with a depth of at most $\textit{d},$ the simplified ancestry scheme enjoys label size of log $_{2}n$ + $2log_{2}d$ + $\textit{O}(1)$ bits. Since the depth of most XML trees is at most some small constant, such an ancestry scheme may be of practical use. In addition, we also obtain an $\textit{adjacency}-labeling$ scheme that labels $\textit{n}-node$ trees of depth $\textit{d}$ with labels of size log $_{2}n$ + 3log $_{2}d$ + $\textit{O}(1)$ bits. All our schemes assign the labels in linear time, and guarantee that any query can be answered in constant time. Finally, our ancestry scheme finds applications to the construction of small $\textit{universal}$ partially ordered sets (posets). Specifically, for any fixed integer $\textit{k},$ it enables the construction of a universal poset of size $Õ(n^{k})$ for the family of $\textit{n}-element$ posets with a tree dimension of at most $\textit{k}.$ Up to lower-order terms, this bound is tight thanks to a lower bound of $\textit{n}\textit{k}$ ™ $\textit{o}(1)$ by to Alon and Scheinerman [1988]. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-02-12 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 1 Page Count 31 Starting Page 1 Ending Page 31

#### Open content in new tab

Source: ACM Digital Library