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

Technical Report 94-07

The Impact of Global Clustering on Spatial Database Systems
March 1994
Thomas Brinkhoff <>
Hans-Peter Kriegel <>
Institut für Informatik
Universität München
Leopoldstr. 11B
D-80802 München (Germany)
global clustering, spatial database systems, spatial query processing,spatial joins
Global clustering has rarely been investigated in the area of spatial database systems although dramatic performance improvements can be achieved by using suitable techniques. In this paper, we propose a simple approach to global clustering called cluster organization. We will demonstrate that this cluster organization leads to considerable performance improvements without any algorithmic overhead. Based on real geographic data, we perform a detailed empirical performance evaluation and compare the cluster organization to other organization models not using global clustering. We will show that global clustering speeds up the processing of window queries as well as spatial joins without decreasing the performance of the insertion of new objects and of selective queries such as point queries. The spatial join is sped up by a factor of about 4, whereas non-selective window queries are accelerated by even higher speed up factors.

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