Optimal Tree Node Ordering forChild/Descendant Navigations

Atsuyuki Morishima, University of Tsukuba
Keishi Tajima, Kyoto University
Masateru Tadaishi, University of Tsukuba
ICDE 2010

Background• There are many applications to deal withhuge tree data:– File Directories, XML data, taxonomies, and someof bioinformatics data.

• Set-based navigations are fundamental
operations for interactively accessing suchdata.

Set-based Navigations• A user specifies one node and a type of navigation,then the system retrieves all the nodes reachable
from that node via that type of navigation.
• The user browses the retrieved nodes, selects one
node, and repeats set-based navigations from it.

aabccaFour Basic Navigations
In such an interactive browse-and-traverse styleof access, users rarely specify complex traverse
conditions. Therefore, we focus on the following
most basic tree navigations:child
descendantl-child
l-descendant

a→ X
*

a→ X
l

a→ X
l*

a→ X

nnl
l
ml

Four Basic Navigations
In such an interactive browse-and-traverse styleof access, users rarely specify complex traverse
conditions. Therefore, we focus on the followingmost basic tree navigations:child
descendantl-child
l-descendant

a→ X
*a→ X
l

a→ X
l*

a→ X

nnllmlFour Basic Navigations
In such an interactive browse-and-traverse styleof access, users rarely specify complex traverse
conditions. Therefore, we focus on the following
most basic tree navigations:child
descendantl-child
l-descendant

a→ X
*

a→ X
l

a→ X
l*

a→ X

nnl
lml

Four Basic Navigations
In such an interactive browse-and-traverse styleof access, users rarely specify complex traverse
conditions. Therefore, we focus on the following
most basic tree navigations:child
descendantl-child
l-descendant

a→ X
*a→ X
l

a→ X
l*

a→ Xnnllml

Four Basic Navigations
In such an interactive browse-and-traverse styleof access, users rarely specify complex traverse
conditions. Therefore, we focus on the following
most basic tree navigations:child
descendantl-child
l-descendant

a→ X
*

a→ X
l

a→ X
l*

a→ X

nnllmlThe Problem Addressed• When the data is huge and stored on the disk,
how to store the nodes to achieve efficientevaluation of the navigations is not trivial.
• One approach is to store the nodes in an
appropriate order so that the nodes
accessed together by these operations are
clustered, but how?

What’s the Problem?
There is no trivial ordering for set-basednavigations which is I/O optimalEx) Depth-first OrderContributions of Our Work• Show that there is no single ordering schemethat is optimal for all the four operations.
• Show three ordering schemes, each of which
is optimal only for a subset of them.
• Found that one of the schemes can process allthe four operations with disk access to a
constant-bounded number of regions on thedisks, without accessing irrelevant nodes

Outline
1. Overview and background
2. The first order: < t
3. The second order: < ltl*
4. The third order: < t
5. Properties and Discussions
6. Summary

< t : Optimal Ordering for a → X and a →* X
Intuitively,
1. Group siblings who has the same parent,
2. Sort the groups in the depth first order in t, and3. Sort the siblings within each group in the siblingorderl*Conflicts caused by a → X

Conflict witha→ X*

Conflict with a → X• This proves that there is no single ordering which
is optimal for all the four set-based navigations• We have two choices.

<Intuitively,lt : Optimal Ordering forl*a → X , a → X , and a → X

1. Sort the children of each node primarily by thelabels of their incoming edges, and secondly by
their original sibling order.
2. Sort the nodes in the same way as < t

<l*t : Optimal Ordering forll*a → X and a → X(1/2)• A maximal unilabeled connected subgraph: A Maximal
connected subgraph that includes only one kind of edgelabel
• Unilabeled clusters : subgraphs created from maximal
unilabeled connected subgraphs by removing their rootnodes

<l*t : Optimal Ordering forll*a → X and a → X

Intuitively,(2/2)

1. Sort the unilabeled clusters primarily in thedepth-first order of their original roots, andsecondly in the dictionary order of their labels
2. Within each unilabeled cluster, we sort nodes inthe order of < tTheoremsll*• There are procedures for a → X and a → Xwith < l * that are I/O optimal.
tl• Similar theorems hold for < t and < t .

The numbers of disk regions to accessn : the number of nodes, l : the number of edge labels

Related Work
• Indexing schemes and labeling schemes for path queries
on XML data
Completely different problem because of differences in thenumber of steps, starting nodes, and support of the closure
operator for specific edge-labels.

• Storage schemes for trees (Clustering-based, twodimensional disk-space architecture, …)
 Efficiently executed by the current disk access interface. No
modification to the disk access interface• Many processing schemes of path queries that scannodes in the depth-first order.
 Efficient for the fundamental navigations without additional
indicesSummary
We showed how we should order nodes of labeledtrees on the disk for efficient processing of setbased navigations.
– Showed there is no single ordering scheme that isoptimal for all the four operations.
– Showed a couple of schemes, each of which isoptimal only for a subset of them.
– Found that one of the schemes can process all thefour operations with disk access to a constantbounded number of regions on the disks, without
accessing irrelevant nodes

Processing a → X with <l*

Tree:

l*t

Disk image:

Procedure:
1. Scan the node entries starting at firstChild(a,l)
2. Stop the scan when we reach a node n s.t either:
1. Parent(n)≠a and parent(n)<firstChild(a,l), or
2. Label(n) ≠l