A modulo-based labeling scheme for dynamically ordered XML trees

XML is becoming the de facto standard for exchanging and querying documents over the Web. Many XML query languages such as XQuery and XPath use label paths to traverse the irregularly structured XML data. Several labeling schemes have been proposed to identify the structural relationships in the tree, as well as to support the incremental updates at a low cost. In this paper, we conduct a comprehensive survey for labeling XML trees, and classify these schemes according to their labeling mechanism. We also propose a novel modulo-based labeling scheme that uses modular arithmetic operations and numbering theory to label the XML tree. Our algorithm labels nodes in the tree in a way, similar to the encryption-decryption function using modular multiplication and a prime modulo. We show that our algorithm supersedes other XML labeling schemes by having a smaller space size for the node label regardless of the fan-out or the depth of the tree, and completely eliminates the need to re-label the whole XML tree in case of future insertions.