Ludwig-Maximilians-Universität München, Institut für Informatik
Technical Report 93-03
- TITLE:
-
Efficient Processing of Spatial Joins Using R-trees
- DATE:
-
March 1993
- AUTHORS:
- Thomas Brinkhoff
<brink@informatik.uni-muenchen.de>
- Hans-Peter Kriegel
<kriegel@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, spatial join,
spatial access methods, R-tree, R*-tree
- ABSTRACT:
-
Spatial joins are one of the most important operations for combining
spatial objects of several relations. The efficient processing of a spatial join is extremely important since its execution time is superlinear
in the number of spatial objects of the participating relations, and this
number of objects may be very high. In this paper, we present a first
detailed study of spatial join processing using R-trees, particularly
R*-trees. R-trees are very suitable for supporting spatial queries and
the R*-tree is one of the most efficient members of the R-tree family.
Starting from a straightforward approach, we present several techniques for improving its execution time with respect to both, CPU-
and I/O-time. Eventually, we end up with an algorithm whose total
execution time is improved over the first approach by an order of magnitude. Using a buffer of reasonable size, I/O-time is almost optimal, i.e. it almost corresponds to the time for reading each required
page of the relations exactly once. The performance of the various
approaches is investigated in an experimental performance comparison where several large data sets from real applications are used.
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)