A new labeling scheme for XML trees based on mesh partition

In this paper we propose a labeling scheme for rooted trees. The scheme based on a mesh partition of the tree, all nodes of the tree have mesh label and nodes in each mesh grid have interval label and/or prefix label. This new scheme is proposed to identify the ancestor-descendant relationship and the parent-child relationship between any two random nodes in constant time. What´s more, the labeling scheme implies how many levels between two given nodes. Meanwhile, the idea of classifying and layering encoding is helpful to solve a critical issue, the size of labels increased when the size of XML document augments.