Compact labeling scheme for ancestor queries
We consider the following problem. Given a rooted tree T, label the nodes of T in the most compact way such that, given the labels of two nodes u and v, one can determine in constant time, by looking only at the labels, whether u is ancestor of v. The best known labeling scheme is rather straightforward and uses labels of length at most 2 log(2) n bits each, where n is the number of nodes in the tree. Our main result in this paper is a labeling scheme with maximum label length log2 n+ O(root 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 length are important.
ancestor queries rooted tree labeling algorithm alphabetic codes