Ludwig-Maximilians-Universität München, Institut für Informatik

Technical Report 93-22

A Technique for Global Clustering Using Spatial Access Methods
October 1993
Thomas Brinkhoff <>
Hans-Peter Kriegel <>
Ralf Schneider
Institut für Informatik
Universität München
Leopoldstr. 11B
D-80802 München (Germany)
spatial database systems, spatial query processing, window queries, spatial access methods, scene organization, global clustering, R-tree, R*-tree
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.

Bei Problemen, Vorschlägen schicken Sie bitte eine eMail an
For problems and suggestions send an email message to
Robert Stabl (28.11.1994)