2009/09/15 by Pierre Fraigniaud, Amos Korman, Fraigniaud, Pierre +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0909.2733
arxiv created 2009/09/15 · openalex publication_date 2009/09/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An ancestry labeling scheme assigns labels (bit strings) to the nodes of rooted trees such that ancestry queries between any two nodes in a tree can be answered merely by looking at their corresponding labels. The quality of an ancestry labeling scheme is measured by its label size, that is the maximal number of bits in a label of a tree node. In addition to its theoretical appeal, the design of efficient ancestry labeling schemes is motivated by applications in web search engines. For this purpose, 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 a simple interval-based ancestry scheme with label size 2log2 n bits (Kannan et al., STOC '88), a considerable amount of work was devoted to improve the bound on the size of a label. The current state of the art upper bound is log2 n + O(√(log n)) bits (Abiteboul et al., SODA '02) which is still far from the known log2 n + Ω(loglog n) bits lower bound (Alstrup et al., SODA '03). In this paper we close the gap between the known lower and upper bounds, by constructing an ancestry labeling scheme with label size log2 n + O(loglog n) bits. In addition to the optimal label size, our scheme assigns the labels in linear time and can support any ancestry query in constant time.