XML Indexing Technology Based on IRST

A new numbering scheme for labeling rooted trees based on leaf order interval numbering scheme (LOINS) is proposed. The nodes in a rooted tree can be encoded in once traversal of the tree, and the ancestor-descendantship among nodes can be determined in constant time based on LOINS. Furthermore, IsBaRTI-I, a novel index for rooted tree structure data model, is proposed which takes the advantages of IRST, such as indexing and compressibility. IsBaRTI-II, the space optimization version of IsBaRTI-I, is also introduced. IsBaRTI-I,II indexes the ancestor-descendantship among nodes and the LOINS number of node by the name (label) of the node and the count of its appearance in the rooted tree. In this way, indexing structure and numbering scheme becomes a unit unity. Theory analysis and experiment result illustrates that IsBaRTI-I,II needs more little time and capacity to be built; the node series and path matching XPath expressions can be obtained more quickly than the previous XML indexes through IsBaRTI-I,II.