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

(a) (b) (c)

Fig. 4. One to one correspondence between the splitting strategy and the MGSFC: (a)
MGG and MG Hilbert-order, (b) improperly split case, (c) properly split case

To use some MGSFC, a proper axis must be selected as a splitting axis when
a cell of the MGG is split. For example, we can't apply the MG Hilbert-order
when the upper left cell of Figure 4(a) is splitting as the Figure 4(b). This is
because the divided lower cell has two sub-cells (the dotted line divides the cell)
with not adjacent values '0100' and '0111'. So, the cell can't have one order
value in the MG Hilbert-order. As explained above, the cell in the MGG must
include conservative ordered sub-cells in the SFC. On the other hand, the two
upper and lower divided cells include two sub-cells with adjacent order values
when the upper left cell of Figure 4(a) is split as in Figure 4(c). So, this split is
adequate.
We must use the splitting strategy that has a property that the sub-cells of
splitted cells must be adjacent in the SFC. We discussed it with the example of
Figure 4. This principle also can be applied to the case of Figure 3 using the
round robin splitting strategy and the MG Z-order.
Therefore, the splitting strategy must reflect the property of the adapted
MGSFC. So, we can linearly order all the cells of multilevel and multidimen-
sional space using the appropriate MGSFC and splitting strategy. Using the
observations, we can process region queries sequentially.

3.3 Region Query Processing

We only consider the case that the multidimensional space is managed by multi-
levels and each level of multidimensional space can be represented by the MGG
when the space is handled by a multidimensional PAM. In this case, the PAM
should have a balanced tree structure and the database for an upper level is an
abstract database of its lower level: i.e., a cell in an upper level may be divided
into multiple cells in a lower level. It has one to n relationship. For example, in
Figure 5 which represents MGGs of two levels, the cell 'x' of an upper level at
Figure 5(a) is divided into cells 'A', 'B', and 'C' of its lower level at Figure 5(b).
When a query region is given for a multidimensional PAM, for each level, all
pages corresponding to the cells intersected with the query region are accessed
for query processing. For example, the pages corresponding to cells 'x' and 'z'
are accessed for the query region 'Q' for the upper level. The sum of these cells is