Technical Report 94-07

TITLE:

The Impact of Global Clustering on Spatial Database Systems

DATE:

March 1994

AUTHORS:

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

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

Institut für Informatik

Universität München

Leopoldstr. 11B

D-80802 München (Germany)

KEYWORDS:

global clustering, spatial database systems, spatial query processing,spatial joins

ABSTRACT:

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.