Ludwig-Maximilians-Universität München, Institut für Informatik
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.
Bei Problemen, Vorschlägen schicken Sie bitte eine eMail an
wwwmaster@informatik.uni-muenchen.de.
For problems and suggestions send an email message to
wwwmaster@informatik.uni-muenchen.de.
Robert Stabl
(28.11.1994)