A Compact Distance Labeling Scheme for Trees of Small Depths

A distance labeling scheme for trees labels the nodes of a tree in such a way that distance queries between any nodes of the tree can be inferred just by looking at their corresponding labels. The natural measure to evaluate the quality of a distance labeling scheme is by its label size, that is the maximal number of bits stored in a label. For arbitrary n-node trees, the current state of the art upper bound on the label is O(log² n) bits. However, general distance labeling schemes may be sub-optimal for specific family of trees. Based on the observation that most real-world tree networks have small depths (e.g., d is polylogarithmic in n), we present a distance labeling scheme of size O(lognlogd), for the family of trees with at most n nodes and depth at most d. This bound is lower than O(log² n) when d takes small values. As an application to our scheme, we show in the end of this paper the scheme can be used to improve routing scalability for small-world networks.