Technical Report 93-22

TITLE:

A Technique for Global Clustering Using Spatial Access Methods

DATE:

October 1993

AUTHORS:

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

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

Ralf Schneider

Institut für Informatik

Universität München

Leopoldstr. 11B

D-80802 München (Germany)

KEYWORDS:

spatial database systems, spatial query processing, window queries, spatial access methods, scene organization, global clustering, R-tree, R*-tree

ABSTRACT:

It is a well-established fact that spatial access methods have to be integrated into spatial database systems in order to support efficient query processing. The range of requirements on spatial access methods appears to be almost too high: both, highly selective spatial access, e.g. point queries, as well as set-oriented access to large sets of objects, e.g. large range queries, have to be supported efficiently. The second type of queries has rarely been investigated in the area of spatial access methods, although for these I/O-intensive queries there is a high potential for performance improvement. The scene organization is a technique for supporting efficient set-oriented access to spatial data. It combines large portions of the spatial data in scenes and globally clusters them on secondary storage, i.e. large sets of spatially adjacent objects are mapped onto physically contiguous storage units. In this paper, we present the algorithms for implementing the scene organization on top of the R*- tree, the most efficient variant of the R-tree. In order to evaluate our approach, we implemented it and performed a detailed performance comparison to conventional storage models. For large range queries, the scene organization is superior in performance to the conventional storage models by a speed up factor of up to 30. This speed up is realized without sacrificing performance for highly selective queries, e.g. very small range queries or point queries.