A new labeling scheme for XML trees based on mesh partition
Na Niu, Dong Guo-qing · 2010
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.