A Labeling Scheme for Dynamic XML Trees Based on History-offset Encoding

Access this Article



This paper presents a novel labeling scheme for dynamic XML trees. The scheme employs <i>history-offset</i> encoding method for multidimensional datasets and takes advantage of this method by embedding an XML tree into a multidimensional extendible array. Even if structural updates are made on the XML tree, no relabeling of nodes is required under the support of extra data structure for preserving the document order. The most significant advantage of our scheme over other existing labeling schemes is that the storage cost for generated labels is very small irrespective of the order and the position of node insertions; in most of our competing schemes, the generated label size would become very large if the insertions occur around the same position. After describing our labeling scheme, label size, total label storage cost and node access performance are examined compared with other sophisticated schemes, such as ORDPATH, QED, DLN and Prime Numbering, and proves that our scheme outperforms these schemes in some criteria.


  • IPSJ Online Transactions

    IPSJ Online Transactions (3), 71-87, 2010

    Information Processing Society of Japan


Page Top