Spatial joins using seeded trees

ABSTRACT

Existing methods for spatial joins assume the existence of indices for the participating data sets. This assumption is not realistic for applications involving multiple map layer overlays or for queries involving non-spatial selections. In this paper, we explore a spatial join method that dynamically constructs index trees called seeded trees at join time. This methods uses knowledge of the data sets involved in the join process.Seeded trees are R-tree like structures, and are divided into the seed levels and the grown levels. The nodes in the seed levels are used to guide tree growth during tree construction. The seed levels can also be used to filter out some input data during construction, thereby reducing tree size. We develop a technique that uses intermediate linked lists during tree construction and significantly speeds up the tree construction process. The technique allows a large number of random disk accesses during tree construction to be replaced by smaller numbers of sequential accesses.Our performance studies show that spatial joins using seeded trees outperform those using other methods significantly in terms of disk I/O. The CPU penalties incurred are also lower except when seed-level filtering is used.

REFERENCES

• BKS93: 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
• BKSS90: 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
• FSR87: Christos Faloutsos , Timos Sellis , Nick Roussopoulos, Analysis of object oriented spatial access methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.426-439, May 27-29, 1987, San Francisco, California, United States
• Gun93: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• Gut84: 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
• LH92: Wei Lu , Jiawei Han, Distance-Associated Join Indices for Spatial Range Search, Proceedings of the Eighth International Conference on Data Engineering, p.284-292, February 03-07, 1992
• NHS84: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• OR93: Frank Olken , Doron Rotem, Sampling from Spatial Databases, Proceedings of the Ninth International Conference on Data Engineering, p.199-208, April 19-23, 1993
• Ore89: 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
• Ore90: Jack Orenstein, A comparison of spatial query processing techniques for native and parameter spaces, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.343-352, May 23-26, 1990, Atlantic City, New Jersey, United States
• Ore91: Jack A. Orenstein, An Algorithm for Computing the Overlay of k-Dimensional Spaces, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.381-400, August 28-30, 1991
• Rot91: Doron Rotem, Spatial Join Indices, Proceedings of the Seventh International Conference on Data Engineering, p.500-509, April 08-12, 1991
• Sam90: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• SE90: Jeffrey Star and John Estes. Geographic Informatzon Systems. Prentice Hall, Englewood Cliffs, New Jersey, 1990.
• SRF87: 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
• Val87: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Experimentation, Performance