XML木のための動的範囲ラベル付け手法

• Item type: Trans(1)
• 公開日: 2004-06-15
• タイトル: XML木のための動的範囲ラベル付け手法
• タイトル / 言語: en
• タイトル: Dynamic Range Labeling for XML Trees
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 日本電信電話株式会社NTTサイバースペース研究所
• 著者所属: 日本電信電話株式会社NTTサイバースペース研究所
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 名古屋大学情報連携基盤センター
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Information Technology Center, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nara Institute of Science and Technology
• 著者名: 江田, 毅晴; 櫻井, 保志; 天笠, 俊之; 吉川, 正俊; 植村, 俊亮
• 著者名(英): Takeharu, Eda; Yasushi, Sakurai; Toshiyuki, Amagasa; Masatoshi, Yoshikawa; Shunsuke, Uemura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文は，動的XMLデータのための新しい節点ラベル付け手法について述べる．今日，範囲ラベル付け手法に基づく構造結合は，XML問合せ処理において最も重要な課題の1つと見なされている．XML木中のそれぞれの節点は，木の中での前置順と後置順の順序関係を保存した数の対でラベル付けされる．このラベルを利用すると，任意の節点間の先祖子孫関係が判定できるため，XML問合せ処理を効率的に行うことができる．しかしながら，XMLデータが更新されると，前置順，後置順それぞれの順序関係を保持するために，ラベルを付け直さなければならない．たとえ間隔を空けてラベル付けしたとしても，大量の挿入や大きなXMLデータの挿入があった場合には十分ではないと考えられる．頻繁に更新の起こる動的なXMLデータへの高速な問合せ処理を継続するためには，大規模なラベルの付け直しを避ける必要がある．そこで，本論文では大規模なラベル付け直しのコストを分散させ，小規模なラベルの付け直しでノードのラベルを維持する2つの動的節点ラベル付け手法を提案する．1つは簡単な小規模ラベル付け直し手法であり，もう1つは近似ヒストグラムを用いて更新操作の情報を保持する，より洗練された手法である．これらの2つの手法により，節点のラベルを動的かつ小規模に管理することができる．実験結果により，更新操作を続けていってもコストの高い大規模なラベルの付け直しを回避できることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a new node labeling approach for data-oriented dynamic XML trees. Recently, structural joins based on range labeling schemes have been considered as one of the most important research topics for XML query processing. Each node in an XML tree is labeled with a pair of numbers which preserves the preorder and the postorder in the tree. The ancestor-descendant relationship between any two labeled nodes can be verified by using their labels; consequently, this property leads to efficient evaluation of XML queries. When an XML data set undergoes updating, however, the nodes have to be relabeled in order to keep their order relationships. Moreover, even if “gaps” are used in labels, the gaps may prove to be insufficient if there are many update operations or the insertion of a large XML tree is required. To avoid a “gap” shortfall, we propose two new dynamic node labeling schemes. One is simple local relabeling scheme and the other is more sophisticated in that it uses approximate histograms to keep approximated information of update operations. These two techniques allow node labels to be managed dynamically and locally. Experiments show that bulk relabeling, which is expensive, can be avoided while still permitting update operations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 45, 号 SIG07(TOD22), p. 102-114, 発行日 2004-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会