A New Multidimensional Point Access Method for Efficient Sequential Processing of Region Queries - Advances in Computational Science and Engineering - page 208

0101 0110 1001 1010

01

10

1011

0100

0111 1000

0010

1101

0011 1100

00 11

0000 0001 1110 1111

(a) (b) (c)

Fig. 2. The Hilbert-order with k =1,2,and3

Since the number of scans must be reduced to process queries eciently, the SFC
must have characteristics of making a small number of SSSs for various forms of a
query region. This means that the SFC must have a property of degree of locality
as high as possible. So, the SFC must locate cells in the linear order as adjacently
as possible for adjacent cells in the multidimensional space to reduce the number of
scans for query processing. This is also because that the processing may be handled
with one scan if the distance between two scans is not too far.
The reasoning behind the locality is that the cells must be located in the
linear order as adjacently as possible for adjacent cells in the multidimensional
space. For example, for the Hilbert-order of two-dimensional space, two cells
among four adjacent cells are located at contiguous positions in the linear order
and the average and variance of the distant value for the discontiguous two
cells are relatively small. But, in the Z-order, only a cell of four adjacent cells is
contiguous in some cases and the average and variance are relatively large. In [4],
it is discussed that the Hilbert-order has the best property with theoretical and
experimental investigation among the SFCs.
In the tree structured multidimensional PAMs, a region corresponding to a
parent node of the tree includes all regions corresponding to all leaf nodes pointed
by the parent node. If an SFC is applied to a multidimensional space managed
by a parent level of the tree, the SFC used for the child level must be
generated from the SFC used for the parent level recursively .Inother
words, the SFCs must have a property of the fractal. If the granule of cells is
reduced in one step (i.e., each cell is divided into 2 n cells), the order must be
maintained recursively. Figures 1 and 2 also show this recursive property.
To handle the recursive property of the SFC eciently, the order of each cell
can be represented n bits for each level in n dimensional space. So, for l levels, nl
bits are needed. For example, the binary value depicted in each cell of Figure 1(a)
represents the cells' order value of the SFC for k = 1. Figure 1(b) represents the
order value for k = 2 and the first two bits of all cells are same as the order
value of a cell in k = 1 including each cell in k = 2. For the Hilbert-order,
the characteristic is analogous. This method uses the lexicographical order for
representing the order value of cells. In this method, the inclusion and adjacency
relation among cells can be easily determined.