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

y D E G

z

Q Q

B

x C F

A

(a) (b)

Fig. 5. The MGG of upper and lower levels

larger than or equal to the query region. We call the sum as MGG corresponding
region of a query region.
However, the pages corresponding to the lower level cells that are divided
from all the upper level cells within the MGG corresponding region for a query
region may not be accessed for query processing. This is because that some cells
in a lower level divided from its upper level cells within the MGG corresponding
region may not be intersected with the query region: i.e., the MGG corresponding
region of the upper level is larger than or equal to the region of its lower level.
For example, in Figure 5, the page corresponding to the cell 'x' must be accessed
for query processing but the page corresponding to the only cell 'C' (not all the
cells 'A', 'B', and 'C' divided from the cell 'x' of the upper level) is accessed for
query processing.
An MGG corresponding region for each level may be divided into multiple re-
gions corresponding to multiple SSSs. This is because that the cells correspond-
ing to MGG corresponding region may be divided into regions corresponding to
multiple SSSs.
An SSS of the upper level may be divided into multiple SSSs of the lower
level. The MGG corresponding region of the lower level may be smaller than
that of the upper level. So, the cells corresponding to the shrinked region of the
lower level for query processing may not be adjacent in the MGSFC order of the
lower level since the region of the lower level corresponding to the given upper
level SSS may be smaller than the region of the upper level corresponding to a
given SSS.
With above observations, Algorithms 1-3 show the pseudo code of our recur-
sive algorithm of handling region queries sequentially for the multilevel MGG
environment. In the algorithms, we assume that the cursor point of the current
handled entry of each level is managed with global variable and all entries for
each level are linked as a chain style according to the MGSFC order value. We
also assume that the page corresponding to a cell in the lowest level points the
leaf page saving key of objects.
In this algorithm, an SSS is constructed in the root level at first and a lower
level SSS is constructed. This process is done recursively. Then, leaf level pages