Technical Report 93-23

TITLE:

A Technique for Global Clustering Using Spatial Access Methods

DATE:

October 1993

AUTHORS:

Hans-Peter Kriegel <kriegel@informatik.uni-muenchen.de>

Ralf Schneider

Thomas Brinkhoff <brink@informatik.uni-muenchen.de>

Institut für Informatik

Universität München

Leopoldstr. 11B

D-80802 München (Germany)

KEYWORDS:

spatial database systems, spatial objects, spatial operations, spatial join, spatial query processing, spatial access methods, object approximations, object decomposition, scene organization, global clustering, R-tree, R*-tree

ABSTRACT:

Due to the high complexity of objects and queries and also due to extremely large data volumes, spatial database systems impose stringent requirements on the performance of query processing. For improving query performance the following two properties are an absolute necessity: (i) a fast spatial access to the objects and (ii) a fast processing of geometric operations. It has been convincingly demonstrated and it is generally accepted that a fast spatial access can only be achieved by integrating spatial access methods (SAMs) into spatial database systems. However, the huge potential that SAMs open for global clustering in combination with set I/O, thus improving the performance of set-oriented access to large amounts of objects, has rarely been investigated. Furthermore, SAMs must be exploited adequately for improving expensive operations such as the spatial join. Property (ii), fast processing of complex geometric operations, is achieved by the following two building blocks: approximations and decompositions. Good approximations provide an efficient filtering by avoiding unnecessary access and operations on the exact representation. The decomposition of complex spatial objects into simple components substitutes the expensive execution of a computational geometry algorithm for the complex object by multiple executions of simple and fast computational geometry algorithms for simple components. In this paper, we investigate the above mentioned potentials for improving the query performance in spatial database systems in detail.