Technical Report 93-04

TITLE:

Approximation-based Query Processing in Spatial Database Systems

DATE:

March 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 objects, point queries, spatial query processing, spatial access methods, object approximations, conservative approximations, convex approximations, R-Tree, R*-tree

ABSTRACT:

The management of geometric objects is a prime example of an application where efficiency is the bottleneck; this bottleneck cannot be eliminated without using suitable access structures. The most popular approach for handling complex spatial objects in spatial access methods is to use their minimum bounding boxes as a geometric key. Obviously, the rough approximation by bounding boxes provides a fast but inaccurate filter for the set of answers to a query. In order to speed up the query processing by a better approximation quality, we investigate six different types of approximations. Depending on the complexity of the objects and the type of queries, the approximations 5-corner, ellipse and rotated bounding box clearly outperform the bounding box. An important ingredient of our approach is to organize these approximations in efficient spatial access methods originally designed for bounding boxes.