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

For processing of region queries, costly tree traversals are needed in a mul-
tidimensional PAM as in the B-tree. If sequential processing of region queries
is supported as in the B + -tree, we can expect great performance enhancements
for region query processing. But, to the extent of the authors' knowledge, there
have been no methods supporting sequential processing of region queries in mul-
tidimensional PAMs. In this paper, we propose an approach that extends multi-
dimensional PAMs for supporting sequential processing of region queries. Using
the approach, we can process a region query with ecient sequential accessing
of multiple SSSs. An SSS is composed of linked disk blocks. The method does
not lose all of current benefits of multidimensional PAMs.
This paper is organized as follows. The characteristics of SFC are explained
inSection2.InSection3,wedefineextendedgridpatternandSFCforhandling
of a multilevel and multidimensional space. Then, we show the splitting strat-
egy of a multidimensional PAM must reflect the characteristics of the extended
SFC. Next, we propose a sequential processing algorithm of region queries in
a multidimensional space using the extended SFC. In Section 4, we propose a
new index structure the MLGF-Plus applying our approach of Section 3 to the
MLGF. In Section 5, we conclude the results and give further research directions
of the proposed ideas.

2 Characteristics of Space Filling Curves

The SFC orders the square shaped cells with full grid patterns of n dimensional
space that divide each axis with the number of 2 k ( k =1 , 2 , ... ) with equal length.
The total number of cells is 2 kn . The SFC can be used for mapping of cells in
multidimensional space to linear order. Typical such SFCs are the Z-order and
the Hilbert-order [4]. Figures 1 and 2 show how these two SFCs order cells in
the two dimensional space when k =1,2,and3.
Generally, the query region for a region query is determined as some prefixed
range or a value for some of multiple attributes. We can regard that the entire
range is selected for undetermined attributes. So, a query region is a hyper-
rectangle. The cells intersected with the query region may be divided as m
SSSs. In this case, the query may be processed m scans of SSSs.

0101 0111 1101 1111

01 11

0100

0110 1100 1110

0001 0011 1001 1011

00 10

0000 0010 1000 1010

(a) (b) (c)

Fig. 1. The Z-order with k =1,2,and3