Ludwig-Maximilians-Universität München, Institut für Informatik
Technical Report 94-05
- TITLE:
-
TITLE:Multi-Step Processing of Spatial Joins
- DATE:
-
March 1994
- AUTHORS:
- Thomas Brinkhoff
<brink@informatik.uni-muenchen.de>
- Hans-Peter Kriegel
<kriegel@informatik.uni-muenchen.de>
- Ralf Schneider
<ralf@informatik.uni-muenchen.de>
- Bernhard Seeger
<bseeger@informatik.uni-muenchen.de>
- Institut für Informatik
- Universität München
- Leopoldstr. 11B
- D-80802 München (Germany)
- KEYWORDS:
-
spatial database systems, multi-step query processing, spatial query processing,
spatial query processing,approximations, decompositions
- ABSTRACT:
Spatial joins are one of the most important operations for combining
spatial objects of several relations. In this paper, spatial join processing
is studied in detail for extended spatial objects in two-dimensional data
space. We present an approach for spatial join processing that is based
on three steps. First, a spatial join is performed on the minimum bounding
rectangles of the objects returning a set of candidates. Various
approaches for accelerating this step of join processing have been
examined at the last year's conference. In this paper, we focus on
the problem how to compute the answers from the set of candidates
which is handled by the following two steps. First of all, sophisticated
approximations are used to identify answers as well as to filter out false
hits from the set of candidates. For this purpose, we investigate various
types of conservative and progressive approximations. In the last step,
the exact geometry of the remaining candidates has to be tested against
the join predicate. The time required for computing spatial join predicates
can essentially be reduced when objects are adequately organized
in main memory. In our approach, objects are first decomposed into
simple components which are exclusively organized by a main-memory
resident spatial data structure. Overall, we present a complete approach
of spatial join processing on complex spatial objects. The performance
of the individual steps of our approach is evaluated with data sets from
real cartographic applications. The results show that our approach reduces
the total execution time of the spatial join by factors.
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)