Multi-step processing of spatial joins

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 [BKS 93a]. In this paper, we focus on the problem how to compute the answers from the set of candidate 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.

REFERENCES

• AA 83: Asano Ta., Asano Te.: 'Minimum Partition of Polygonal Regions into Trapezoids', Proc. 24th IEEE Annual Symp. on Foundations of Computer Science, 1983, pp. 233-241.
• BG 90: Blankenagel G., Gating H.: 'Internal and External Algorithms for the Points-in-Regions Problem - the IN- SIDE Join of Geo-Relational Algebra', Algorithmica, 1990, pp. 251-276.
• BHKS 93: Thomas Brinkhoff , Holger Horn , Hans-Peter Kriegel , Ralf Schneider, A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.357-376, June 23-25, 1993
• BK 94: Brinkhoff T., Kriegel H.-P.: 'The Impact of Global Clusterin8 on Spatial Database Systems ', Technical report, University of Munich, 1994.
• BKS 93a: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• BKS 93b: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider, Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems, Proceedings of the Ninth International Conference on Data Engineering, p.40-49, April 19-23, 1993
• BKSS 90: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• BZ 91: Dan Benson , Greg Zick, Symbolic and spatial database for structural biology, Conference proceedings on Object-oriented programming systems, languages, and applications, p.329-339, October 06-11, 1991, Phoenix, Arizona, United States
• DB 83: Dori D., Ben-Bassat M.: 'Circumscribing a Convex Polygon by a Polygon of Fewer Sides with Minimal Area Addition', Computer Vision, Graphics, and Image Processing, Vol. 24, 1983, pp. 131-159.
• Fal 88: C. Faloutsos, Gray Codes for Partial Match and Range Queries, IEEE Transactions on Software Engineering, v.14 n.10, p.1381-1393, October 1988 [doi>10.1109/32.6184]
• Gün 89: Oliver Günther, The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases, Proceedings of the Fifth International Conference on Data Engineering, p.598-605, February 06-10, 1989
• Gün 93: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• Gut 84: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• Jag 90a: H. V. Jagadish, Spatial Search with Polyhedra, Proceedings of the Sixth International Conference on Data Engineering, p.311-319, February 05-09, 1990
• Jag 90b: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• KBS 93: Kriegel H.-P., Brinkhoff T., Schneider R.: 'Ej#%ient Spatial Query Processing in Geographic Database Systems', IEEE Data Engineering Bulletin, Vol. 16, No. 3, 1993, pp. 10-15.
• KHS 91: Hans-Peter Kriegel , Holger Horn , Michael Schiwietz, The Performance of Object Decomposition Techniques for Spatial Query Processing, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.257-276, August 28-30, 1991
• ME 92: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• Ore 86: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• PS 85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Sam 90: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• SH 76: Shamos M. I., Hoey D. J.: 'Geometric Intersection Problems', Proc. 17th Annual Conf. on Foundations of Computer Science, pp. 208-215, 1976.
• SK 91: Ralf Schneider , Hans-Peter Kriegel, The TR*-Tree: A New Representation of Polygonal Objects Supporting Spatial Queries and Operations, Proceedings of the International Workshop on Computational Geometry - Methods, Algorithms and Applications, p.249-263, March 21-22, 1991
• SRF 87: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• Wel91: Welzl E.: 'Smallest Enclosing Disks (Balls and Ellipsoids)', Technical report B91-09, Freie University of Berlin, 1991.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Geometrical problems and computations

General Terms:
Algorithms, Performance