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

entry A: 00,00, PTR7
entry B: 00,01, PTR8
entry C: 01,0, PTR9

entry x: 0,0, PTR1
entry y: 0,1, PTR2
entry z: 1,-, PTR3

entry D: 00,1, PTR5
entry E: 01,1, PTR6

entry F: 1,0, PTR10
entry G: 1,1, PTR11

Fig. 6. Two level directory structure of two dimensional MLGF

page overflows. The local splitting strategy maintains the policy of having one
directory entry correspond to one page; thus, the strategy prevents the MLGF
from creating unnecessary directory entries. As a result, the directory size of the
MLGF is linearly dependent on the number of inserted objects regardless of data
distribution or correlation among the attributes [5]. So, the MLGF can manage
the MGG.
Basically, in the MLGF, the axis for splitting is not determined when the
splitting is needed. So, as discussed in Section 3, the MLGF can be generated
by using the characteristics of the adapted MGSFC. Thus, the MLGF is a PAM
thatcanmanagetheMGG,whichproposedinSection3.1,andcanemploythe
query processing method proposed in Section 3.3.

4.2 MLGF-Plus

In this section, we discuss how the approach of Section 3 is applied to the MLGF.
We also discuss the difference between algorithms of the MLGF and the MLGF-
Plus for the region query processing.
For linear ordering of the cells of multilevel and multidimensional space that
are managed by the MLGF-Plus, we maintain the order of cells by the MGSFC,
the MGSFC order value , for each level. For doing this, we should know the
MGSFC order value for each region that corresponds each entry. The order
value can be stored in an additional field for each entry or can be calculated
by using the region vector of each directory entry. The former is not preferable
since it decreases the fan-out because of growing of the entry size. Thus, we use
the latter although it needs some additional calculations.
By using these order values, we can store the entries for all regions of a
directory page according to the order of the MGSFC. This can be done by
using the insertion sort technique and thus requires position changes of directory
entries. Although an additional field may be used without the position changes,
we do not use this technique since it incurs growing of the entry size.
When the two regions corresponding to two entries K and L stored in other
directory pages are adjacent in the order of the MGSFC, we can maintain the
adjacency relation by storing the page ID of L in the page containing K (with