Atlantis Press Paper Details: Algorithms for Indexing Dynamic XML Data

Some approaches such as path indexing, labeling, and numbering scheme have been proposed in order to facilitate query of XML data. The indexes derived by these approaches must be rebuilt if XML data is updated. The method LSDX (Labeling Scheme for Dynamic XML data) can dynamically add new labels without updating existing old labels. However, there are two defects in LSDX. The first defect is that the nodes within the same level can be labeled no more than twenty five when LSDX builds the XML index tree. The second defect occurs when updating the index tree. If LSDX inserts a new node C between two nodes A, B and then inserts a new node D between the two nodes A, C, the label of the node D cannot be coded because of the label coding strategy of LSDX. In this paper, we propose algorithms with new label coding rules to solve the two defects of LSDX. With our method, unlimited nodes within the same level can be labeled when building the index. When updating the index tree, we use a new label coding method for new-inserted nodes. If the number of new-inserted nodes within the same level is not more than five, the label length of these nodes will not increase immediately.


title:		Algorithms for Indexing Dynamic XML Data
publication:		JCIS-2006 Proceedings
part of series:		Advances in Intelligent Systems Research
ISBN:		978-90-78677-01-7
ISSN:		1951-6851
DOI:		doi:10.2991/jcis.2006.333 (how to use a DOI)
author(s):		Jeang-Kuo Chen, Jen-Peng Hsu
corresponding author:		Jeang-Kuo Chen
publication date:		October 2006
keywords:		XML, Algorithm, Indexing, Labeling
abstract:		Some approaches such as path indexing, labeling, and numbering scheme have been proposed in order to facilitate query of XML data. The indexes derived by these approaches must be rebuilt if XML data is updated. The method LSDX (Labeling Scheme for Dynamic XML data) can dynamically add new labels without updating existing old labels. However, there are two defects in LSDX. The first defect is that the nodes within the same level can be labeled no more than twenty five when LSDX builds the XML index tree. The second defect occurs when updating the index tree. If LSDX inserts a new node C between two nodes A, B and then inserts a new node D between the two nodes A, C, the label of the node D cannot be coded because of the label coding strategy of LSDX. In this paper, we propose algorithms with new label coding rules to solve the two defects of LSDX. With our method, unlimited nodes within the same level can be labeled when building the index. When updating the index tree, we use a new label coding method for new-inserted nodes. If the number of new-inserted nodes within the same level is not more than five, the label length of these nodes will not increase immediately.
copyright:		© Atlantis Press. This article is distributed under the terms of the Creative Commons Attribution License, which permits non-commercial use, distribution and reproduction in any medium, provided the original work is properly cited.
full text:		JCIS06-CSI-72.pdf (111 K)