Ludwig-Maximilians-Universität München, Institut für Informatik
Technical Report 93-05
- TITLE:
-
Query Processing of Spatial Objects: Complexity versus Redundancy
- DATE:
-
March 1993
- AUTHORS:
- Hans-Peter Kriegel
<kriegel@dbs.informatik.uni-muenchen.de>
- Michael Schiwietz
<michael@dbs.informatik.uni-muenchen.de>
- Institut für Informatik
- Universität München
- Leopoldstr. 11B
- D-80802 München (Germany)
- KEYWORDS:
-
spatial database systems, spatial query processing, approximations, processing, approximations,
- ABSTRACT:
The management of complex spatial objects in applications, such as geography
and cartography, imposes stringent new requirements on spatial database systems,
in particular on efficient query processing. As shown before, the performance
of spatial query processing can be improved by decomposing complex spatial
objects into simple components. Up to now, only decomposition techniques
generating a linear number of very simple components, e.g. triangles or
trapezoids, have been considered. In this paper, we will investigate the natural
trade-off between the complexity of the components and the redundancy, i.e. the
number of components, with respect to its effect on efficient query processing.
In particular, we present two new decomposition methods generating a better
balance between the complexity and the number of components than previously
known techniques. We compare these new decomposition methods to the traditional
undecomposed representation as well as to the well-known decomposition into
convex polygons with respect to their performance in spatial query processing.
This comparison points out that for a wide range of query selectivity the new
decomposition techniques clearly outperform both the undecomposed representation
and the convex decomposition method. More important than the absolute gain in
performance by a factor of up to an order of magnitude is the robust performance
of our new decomposition techniques over the whole range of query selectivity.
Bei Problemen, Vorschlägen schicken Sie bitte eine eMail an
wwwmaster@informatik.uni-muenchen.de.
For problems and suggestions send an email message to
wwwmaster@informatik.uni-muenchen.de.
Robert Stabl
(28.11.1994)