Compact Ancestry Labeling Schemes for XML Trees

Date Added: Oct 2009
Format: PDF

An ancestry labeling scheme labels the nodes of any tree in such a way that ancestry queries between any two nodes can be answered just by looking at their corresponding labels. The common measure to evaluate the quality of an ancestry scheme is by its label size that is the maximum number of bits stored in a label, taken over all n-node trees. The design of ancestry labeling schemes finds applications in XML search engines. In these contexts, even small improvements in the label size are important. As a result, following the proposal of a simple interval based ancestry scheme with label size 2 log n bits a considerable amount of work was devoted to improve the bound on the label size.