Efficient processing of spatial joins using R-trees

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.

REFERENCES

• 1: Becker, L. A.: 'A New Algorithm and a Cost Model for Join Processing with Grid Files', PhD-thesis, University of Siegen, 1992.
• 2: 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
• 3: Burrough P. A.: 'Principles of Geographical Information Systems for Land Resources Assessment', Oxford University Press, 1986.
• 4: Bureau of the Census: "Tiger/Line Precensus Files: 1990 technical documentation', Bureau of the Census, Washington, DC, 1989.
• 5: Bentley J.L., Wood D.: 'An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles', IEEE Trans. on Computers, Vol. C- 29, No. 7, 1980, pp. 571-577.
• 6: 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]
• 7: F. Fotouhi , S. Pramanik, Optimal Secondary Storage Access Sequence for Performing Relational Join, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.318-328, September 1989 [doi>10.1109/69.87978]
• 8: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 9: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• 10: 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
• 11: Lilian Harada , Miyuki Nakano , Masaru Kitsuregawa , Mikio Takagi, Query processing method for multi-attribute clustered relations, Proceedings of the sixteenth international conference on Very large databases, p.59-70, September 1990, Brisbane, Australia
• 12: Erik G. Hoel , Hanan Samet, A qualitative comparison study of data structures for large line segment databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.205-214, June 02-05, 1992, San Diego, California, United States
• 13: Kriegel H.-P., Brinkhoff T., Schneider R.: "An Efficient Map Overlay Algorithm based on Spatial Access Methods and Computational Geometry', Proc. Int. Workshop on Database Management Systems for Geographical Applications, Capri, Italy, 1991, in: Geographic Database Management Systems, Springer, 1992, pp. 194-211.
• 14: Ibrahim Kamel , Christos Faloutsos, Parallel R-trees, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.195-204, June 02-05, 1992, San Diego, California, United States
• 15: 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]
• 16: Merret T., Kambayashi Y., Yasuura H.: "Scheduling of Page-Fetches in Join-Operations', Proc. 7th Int. Conf. on Very Large Data Bases, Cannes, 1981, pp. 488-498.
• 17: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 18: 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
• 19: J. A. Orenstein, Redundancy in spatial databases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.295-305, June 1989, Portland, Oregon, United States
• 20: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 21: Doron Rotem, Spatial Join Indices, Proceedings of the Seventh International Conference on Data Engineering, p.500-509, April 08-12, 1991
• 22: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 23: M. Stonebraker , L. A. Rowe , M. Hirohama, The Implementation of POSTGRES, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.125-142, March 1990 [doi>10.1109/69.50912]
• 24: Statistical Office of the European Communities: 'Regions', 1990.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Design, Performance