There are many applications in which users interactively access huge
tree data by repeating set-based navigations.
In this paper, we focus on label-specific/wildcard children/descendant
navigations. For efficient processing of these operations in huge
data stored on a disk, we need a node ordering scheme that clusters
nodes that are accessed together by these operations.
In this paper, (1) we show there is no node order that is optimal for
all these operations, (2) we propose two schemes, each of which is
optimal only for some subset of them, and (3) we show that one of the
proposed schemes can process all these operations with access to a
constant-bounded number of regions on the disk without accessing
irrelevant nodes.
tree data, storage scheme, node order, child, descendent, query,
retrieval, navigation, traversal, closure, I/O complexity, XML
Publishd in Proc. of IEEE ICDE, pp.840-843, Mar. 2010, Long Beach, CA
/ Fax: +81(Japan) 75-753-5978 / Office: Research Bldg. #7, room 404