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

Pierre Fraigniaud 1, 2 Amos Korman 2, 1, *
* Auteur correspondant
1 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
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 log 2 n + O(log log n) bits, thus matching the log 2 n + Ω(log log n) 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 log 2 n + 2 log 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 log 2 n + 3 log 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˜Osize˜ size˜O(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].
Type de document :
Article dans une revue
Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63, pp.1 - 31. 〈10.1145/2794076〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01393643
Contributeur : Amos Korman <>
Soumis le : lundi 7 novembre 2016 - 18:44:16
Dernière modification le : jeudi 26 avril 2018 - 10:29:14
Document(s) archivé(s) le : mardi 14 mars 2017 - 23:27:10

Fichiers

JACM-final-HAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Fraigniaud, Amos Korman. An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets. Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63, pp.1 - 31. 〈10.1145/2794076〉. 〈hal-01393643〉

Partager

Métriques

Consultations de la notice

175

Téléchargements de fichiers

51