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

A New Multidimensional Point Access Method
for Ecient Sequential Processing of Region
Queries

Ju-Won Song, Sung-Hyun Shin, and Sang-Wook Kim

College of Information & Communications, Hanyang University, Korea

Abstract. The B + -tree was proposed to support sequential processing
in the B-tree. To the extent of authors' knowledge, however, there have
been no studies supporting sequential processing in multidimensional
point access methods(PAMs). To do this, the cells in a multilevel and
multidimensional space managed by a multidimensional PAM must be
linearly ordered systematically. In this paper, we discuss an approach
that linearly orders cells in a multilevel and multidimensional space and
propose a novel sequential processing algorithm for region queries using
this approach. We then propose the MLGF-Plus applying this approach
to the MLGF.

1 Introduction

After the B-tree was invented by multiple teams simultaneously, the B + -tree
was proposed for supporting sequential processing of range queries without tree
traversal [1]. The B + -tree not only has all of advantages of the B-tree but also
supports ecient sequential processing of range queries in one dimensional space
without costly tree traversal.
In the B + -tree, the keys of all objects are stored in leaf nodes, and all the
leaf nodes are linked in increasing order of the keys. These all linked leaf nodes
are called the sequence set [1]. The SSS( subset of the sequence set )foraquery
is defined as a linked portion of the sequence set that starts from a leaf node
containing the starting point of the query range and ends a node containing
the ending point of the range. A range query in one dimensional space can be
processed by scanning of an SSS for the query.
In the last two decades, various multidimensional point access methods(PAMs)
were studied for handling of objects that can be represented as points in a mul-
tidimensional space. As results, robust PAMs that eciently handle various dis-
tributions including skewed, such as KDB-tree [6], MLGF [10,11,13,7,8], and
LSD-tree [2] were developed. These PAMs can be regarded as extensions of the
B-tree or the B + -tree for the multidimensional space in some aspects.
Also, a method using the space filling curve(SFC) for handling multidimen-
sional objects without the extension of the B-tree was proposed [4]. The SFC is
used for ordering of grid patterned square cells of a multidimensional space.