2024-03-29T20:17:09Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000692092020-10-27T05:03:12Z00934:01022:06082:06083
A Labeling Scheme for Dynamic XML Trees Based on History-offset EncodingA Labeling Scheme for Dynamic XML Trees Based on History-offset Encodingeng研究論文http://id.nii.ac.jp/1001/00069209/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=69209&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of JapanGraduate School of Engineering, University of FukuiToshiba Solutions CorporationGraduate School of Engineering, University of FukuiGraduate School of Engineering, University of FukuiBei, LiKatsuya, KawaguchiTatsuo, TsujiKen, HiguchiThis 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.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.AA11464847情報処理学会論文誌データベース(TOD)311172010-03-191882-77992010-03-16