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

DOI10.1145/2794076zbMATH Open1426.68078arXiv1611.02589OpenAlexW3102876231MaRDI QIDQ3177763FDOQ3177763

Amos Korman, Pierre Fraigniaud

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: In this paper we solve the ancestry-labeling scheme problem which aims at assigning the shortest possible labels (bit strings) to nodes of rooted trees, so that ancestry queries between any two nodes can be answered by inspecting their assigned labels only. This problem was introduced more than twenty years ago by Kannan et al. [STOC '88], and is among the most well-studied problems in the field of informative labeling schemes. We construct an ancestry-labeling scheme for $n$-node trees with label size $lo{g}_{2}n+O(loglogn)$ bits, thus matching the $lo{g}_{2}n+O(loglogn)$ bits lower bound given by Alstrup et al. [SODA '03]. 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 n-node trees with depth at most d, the simplified ancestry scheme enjoys label size of $lo{g}_{2}n+2lo{g}_{2}d+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 adjacency-labeling scheme that labels n-node trees of depth d with labels of size $lo{g}_{2}n+3lo{g}_{2}d+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 universal partially ordered sets (posets). Specifically, for any fixed integer k, it enables the construction of a universal poset of size $ildeO(n^k)$ for the family of $n$-element posets with tree-dimension at most $k$. Up to lower order terms, this bound is tight thanks to a lower bound of $n^{k-o(1)}$ due to Alon and Scheinerman [Order '88].

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

zbMATH Keywords

treedatabasegraph decompositionposetlabeling schemeXML search engine

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Database theory (68P15)

Cited In (3)

• Compact labeling scheme for XML ancestor queries
• Shorter Labeling Schemes for Planar Graphs
• An optimal ancestry scheme and small universal posets

   Recommendations

• Title not available (Why is that?) 👍 👎
• A Simple and Optimal Ancestry Labeling Scheme for Trees 👍 👎
• An optimal ancestry scheme and small universal posets 👍 👎
• Title not available (Why is that?) 👍 👎
• Compact labeling schemes for ancestor queries. (Extended abstract) 👍 👎
• Compact labeling scheme for XML ancestor queries 👍 👎
• Title not available (Why is that?) 👍 👎
• Near-optimal labeling schemes for nearest common ancestors 👍 👎
• Optimal labellings of rooted directed trees 👍 👎

This page was built for publication: An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

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