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

Technical Report 93-04

Approximation-based Query Processing in Spatial Database Systems
March 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 objects, point queries, spatial query processing, spatial access methods, object approximations, conservative approximations, convex approximations, R-Tree, R*-tree
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.

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