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

(a) MGG (b) MG Z-order

Fig. 3. An example of the MGG and the MG Z-order

The MGSFC and the splitting strategy are very closely related. For example,
Figure 3(a) shows an example of the MGG that uses the round-robin splitting
strategy in two-dimensional space. The thin line in Figure 3(b) shows the Z-order
of a grid pattern with k = 2, and the bold line shows the MG Z-order applied
for the MGG of Figure 3(a). As we can see, the MG Z-order can be regarded
as an integration of the Z-orders of multilevels. So, the MG Z-order is closely
related with the round-robin splitting strategy.
In the MGG, the cells of a non-square shape can be divided into multiple sub-
cells of a square shape and the order values of these sub-cells in the SFC must be
consecutive. For example, the cell in the upper left corner in Figure 3(a) can be
divided into two sub-cells of a square shape and the two sub-cells are consecutive
in the Z-order with k = 2. In such a case, we can regard the consecutive order
values in the SFC as one order value in the MGSFC. For example, the order
value of the cell in the upper left corner in Figure 3(a) can be represented as
'010' that includes the prefix of the order values of the two sub-cells '0100' and
'0101'.
The relation of the inclusion and adjacency of cells in the MGG can be easily
determined using the method of representing the order values of the cells ex-
plained in Section 2. For the two cells with order values of the different length,
the shorter cell is included in the longer cell if the prefix bits of longer cell is
same as all the bits of the shorter cell. For example, the cells with order values
'0100' and '0101' are included in the cell with an order value '010'. When the
order value of the longer cell is increased or decreased by one, the two cells are
adjacent if the prefix bits of the longer cellissameasallthebitsoftheshorter
cell. For example, the cells '0011' and '01' are adjacent since the cells '0011' and
'0100' are adjacent and the cell '0100' is included in the cell '01'. Also the cells
'0100' and '00' are adjacent since the cells '0100' and '0011' are adjacent and
the cell '0100' is included in the cell '01'.
The splitting strategy for the MGG must reflect the characteristics of the
MGSFC. To use some MGSFC, we must use an adequate splitting strategy.
Figure 4(a) shows an example of one to one correspondence with the MGG and
the MG Hilbert-order.