Iterative spatial join

ABSTRACT

The key issue in performing spatial joins is finding the pairs of intersecting rectangles. For unindexed data sets, this is usually resolved by partitioning the data and then performing a plane sweep on the individual partitions. The resulting join can be viewed as a two-step process where the partition corresponds to a hash-based join while the plane-sweep corresponds to a sort-merge join. In this article, we look at extending the idea of the sort-merge join for one-dimensional data to multiple dimensions and introduce the Iterative Spatial Join. As with the sort-merge join, the Iterative Spatial Join is best suited to cases where the data is already sorted. However, as we show in the experiments, the Iterative Spatial Join performs well when internal memory is limited, compared to the partitioning methods. This suggests that the Iterative Spatial Join would be useful for very large data sets or in situations where internal memory is a shared resource and is therefore limited, such as with today's database engines which share internal memory amongst several queries. Furthermore, the performance of the Iterative Spatial Join is predictable and has no parameters which need to be tuned, unlike other algorithms. The Iterative Spatial Join is based on a plane sweep algorithm, which requires the entire data set to fit in internal memory. When internal memory overflows, the Iterative Spatial Join simply makes additional passes on the data, thereby exhibiting only a gradual performance degradation. To demonstrate the use and efficacy of the Iterative Spatial Join, we first examine and analyze current approaches to performing spatial joins, and then give a detailed analysis of the Iterative Spatial Join as well as present the results of extensive testing of the algorithm, including a comparison with partitioning-based spatial join methods. These tests show that the Iterative Spatial Join overcomes the performance limitations of the other algorithms for data sets of all sizes as well as differing amounts of internal memory.

REFERENCES

• 1: Aref, W. G. and Samet, H. 1992. Uniquely reporting spatial objects: Yet another operation for comparing spatial data structures. In Proc. of the 5th Int. Symposium on Spatial Data Handling. (Charleston, S.C), 178--189.
• 2: Aref, W. G. and Samet, H. 1994a. The spatial filter revisited. In Proc. of the 6th Int. Symposium on Spatial Data Handling, (Edinburgh, Scotland.) T. C. Waugh and R. G. Healey, Eds. International Geographical Union Commission on Geographic Information Systems, Association for Geographical Information, pp. 190--208.
• 3: Walid G. Aref , Hanan Samet, Hashing by proximity to process duplicates in spatial databases, Proceedings of the third international conference on Information and knowledge management, p.347-354, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191307]
• 4: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 5: D. S. Batory , J. R. Barnett , J. F. Garza , K. P. Smith , K. Tsukuda , C. Twichell , T. E. Wise, GENESIS: An Extensible Database Management System, IEEE Transactions on Software Engineering, v.14 n.11, p.1711-1730, November 1988 [doi>10.1109/32.9057]
• 6: 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
• 7: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 8: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel, Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.216-230, March 23-27, 1998
• 9: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, GENESYS: a system for efficient spatial query processing, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.519, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: 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
• 11: Michael J. Carey , David J. DeWitt , Joel E. Richardson , Eugene J. Shekita, Object and File Management in the EXODUS Extensible Database System, Proceedings of the 12th International Conference on Very Large Data Bases, p.91-100, August 25-28, 1986
• 12: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 13: Data Redundancy and Duplicate Detection in Spatial Join Processing, Proceedings of the 16th International Conference on Data Engineering, p.535, February 28-March 03, 2000
• 14: Edelsbrunner, H. 1980. Dynamic Rectangle Intersection Searching. Institute for Information Processing 47, Technical University of Graz, Graz, Austria. Feb.
• 15: Esperança, C. and Samet, H. 1996. Spatial database programming using SAND. In Proc. of the 7th Int. Symposium on Spatial Data Handling, vol. 2. (Delft, The Netherlands). M. J. Kraak and M. Molenaar, Eds. International Geographical Union Commission on Geographic Information Systems, Association for Geographical Information, pp. A29--A42.
• 16: Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, Vector approximation based indexing for non-uniform high dimensional data sets, Proceedings of the ninth international conference on Information and knowledge management, p.202-209, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354820]
• 17: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 18: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• 19: Ralf Harmut Güting , Werner Schilling, A practical divide-and-conquer algorithm for the rectangle intersection problem, Information Sciences: an International Journal, v.42 n.2, p.95-112, July 1987 [doi>10.1016/0020-0255(87)90018-1]
• 20: Herring, J. R. 1996. Oracle7 spatial data optionTM: Advances in relational database technology for spatial data management. Tech. rep., Oracle Corporation. Sept.
• 21: Erik G. Hoel , Hanan Samet, Benchmarking Spatial Join Operations with Spatial Output, Proceedings of the 21th International Conference on Very Large Data Bases, p.606-618, September 11-15, 1995
• 22: Yun-Wu Huang , Matthew C. Jones , Elke A. Rundensteiner, Improving Spatial Intersect Joins Using Symbolic Intersect Detection, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.165-177, July 15-18, 1997
• 23: Glenn S. Iwerks , Hanan Samet, The Spatial Spreadsheet, Proceedings of the Third International Conference on Visual Information and Information Systems, p.317-324, June 02-04, 1999
• 24: Kedem, G. 1981. The quad-cif tree: A data structure for hierarchical on-line algorithms. Computer Science Department TR-91, University of Rochester, Rochester, NY. Sept.
• 25: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 26: Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
• 27: Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.209-220, May 24-27, 1994, Minneapolis, Minnesota, United States
• 28: Ming-Ling Lo , Chinya V. Ravishankar, Generating Seeded Trees from Data Sets, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.328-347, August 06-09, 1995
• 29: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
• 30: Nikos Mamoulis , Dimitris Papadias, Integration of spatial join algorithms for processing multiple inputs, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.1-12, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 31: Gabriele Neyer , Peter Widmayer, Singularities Make Spatial Join Scheduling Hard, Proceedings of the 8th International Symposium on Algorithms and Computation, p.293-302, December 17-19, 1997
• 32: 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
• 33: J. A. Orenstein, Strategies for optimizing the use of redundancy in spatial databases, Proceedings of the first symposium on Design and implementation of large spatial databases, p.115-134, February 1990, Santa Barbara, California, United States
• 34: 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
• 35: Thomas Ottmann , Derick Wood, Space-economical plane-sweep algorithms, Computer Vision, Graphics, and Image Processing, v.34 n.1, p.35-51, April 1986 [doi>10.1016/0734-189X(86)90046-0]
• 36: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 37: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 38: Michael Stonebraker , James Frew , Jeff Dozier, The SEQUOIA 2000 Project, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.397-412, June 23-25, 1993
• 39: Thomas G. Szymanski , Christopher J. Van Wyk, Space efficient algorithms for VLSI artwork analysis, Proceedings of the 20th conference on Design automation, p.734-739, June 27-29, 1983, Miami Beach, Florida, United States
• 40: U.S. Bureau of the Census. 1992. Tiger/Line files. Tech. rep., U.S. Bureau of the Census, Washington, DC.
• 41: Erik D Vengroff , Scott J Vitter, I/O Efficient Scientific Computation Using TPIE, Duke University, Durham, NC, 1995
• 42: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]
• 43: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Performance

Keywords:
Spatial join, external memory algorithms, plane-sweep, spatial databases