Information Technology Reference
In-Depth Information
having key values of objects are accessed for the lowest level. This algorithm
adapts the depth-first processing techniques 2 . So, for each level, only an SSS
is handled for query processing. The breath-first technique may be used. The
depth-first technique would be more ecient.
4MLGF-Plus
TheapproachproposedinSection3isageneral method that can be applied
for all PAMs managing the MGG. But, for applying the approach to a certain
PAM managing the MGG, the detail implementation method considering the
characteristics of the PAM must be designed. In this section, we address this for
applying our approach to the MLGF [7,8,10,11,13]. In Section 4.1, we explain
the characteristics of the MLGF [7,8,10,11,13] that can manage the MGG. In
Section 4.2, we propose a new index structure applying the approach proposed
in Section 3. We call it the MLGF-Plus . So, the MLGF-Plus can support ecient
sequential processing of region queries.
4.1 MLGF
The MLGF is a balanced tree and consists of a multilevel directory and data
pages [10,11]. Each directory level reflects the status of space partition of a level.
A directory page has directory entries contained in a region that corresponds to a
higher-level directory entry pointing to the page. When the MLGF is used as an
index, each directory entry in a leaf level consists of a key of the corresponding
object and a pointer to that object. So, the MLGF is an n -ary balanced index
structure basically.
A directory entry in a nonleaf level consists of a region vector and a pointer to
a lower-level page. A region vector in an n -dimensional MLGF consists of n hash
values that uniquely identify the region. The position, shape, and size of a region
are reflected in the region vector. The i -th hash value of a region vector is the
common prefix of the hash values for the i -th attribute of all the possible objects
that belong to the region. Figure 6 represents the MLGF structure managing the
MGG of Figure 5. For example, the directory entry E in this figure represents
the region containing all the objects having common prefix '01' and '1' for the
first and second attributes respectively when the two attributes of the objects
are hashed.
By splitting and merging pages, the MLGF adapts to dynamic environments
where insertions and deletions of objects frequently occur. If a directory page
overflows, the corresponding region is split into two equal-sized regions (say, the
halving strategy ). The MLGF employs the local splitting strategy [5] that splits a
region locally, rather than across the entire hyperplane, when the corresponding
2 In each level, if the number of entries between two SSSs is lower than some pre-
determined value, we may handle these two SSSs as one SSS. With this method,
the false-drop is larger but the number of scans gets smaller. We left it as a further
research.
 
Search WWH ::




Custom Search