文章基本信息

标题：A Labeling Scheme for Dynamic XML Trees Based on History-offset Encoding
本地全文：下载
作者：Bei Li ; Katsuya Kawaguchi ; Tatsuo Tsuji 等
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2010
卷号：5
期号：2
页码：549-565
DOI：10.11185/imt.5.549
出版社：Information and Media Technologies Editorial Board
摘要：This paper presents a novel labeling scheme for dynamic XML trees. The scheme employs history-offset 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.