Partition based spatial-merge join

ABSTRACT

This paper describes PBSM (Partition Based Spatial-Merge), a new algorithm for performing spatial join operation. This algorithm is especially effective when neither of the inputs to the join have an index on the joining attribute. Such a situation could arise if both inputs to the join are intermediate results in a complex query, or in a parallel environment where the inputs must be dynamically redistributed. The PBSM algorithm partitions the inputs into manageable chunks, and joins them using a computational geometry based plane-sweeping technique. This paper also presents a performance study comparing the the traditional indexed nested loops join algorithm, a spatial join algorithm based on joining spatial indices, and the PBSM algorithm. These comparisons are based on complete implementations of these algorithms in Paradise, a database system for handling GIS applications. Using real data sets, the performance study examines the behavior of these spatial join algorithms in a variety of situations, including the cases when both, one, or none of the inputs to the join have an suitable index. The study also examines the effect of clustering the join inputs on the performance of these join algorithms. The performance comparisons demonstrates the feasibility, and applicability of the PBSM join algorithm.

REFERENCES

• Arc95: ESRI, Redlands, CA. "ARC/INFO: The World's GIS. An ESRI White Paper", March 1995.
• Ben75: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• Ben79: J. L. Bentley. "Multidlmensionat Binary Search Trees in Database Applications". In IEEE Trat~sactions on Software Engineering, volume 5(4), 1979.
• BHF93: Ludger Becker , Klaus Hinrichs , Ulrich Finke, A New Algorithm for Computing Joins with Grid Files, Proceedings of the Ninth International Conference on Data Engineering, p.190-197, April 19-23, 1993
• 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
• BKSS94: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
• Bur86: R A. Burrough. "Principles of Geographic hzformation Systems for Land Resources Assessment". Oxford University Press, 1986.
• CDF+94: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• CFR87: 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
• Cor95: Intergraph Corporation. "GIS/AM/FM Information". "http://wwm intergraph'c~m/utihnap'shtmt ", 1995.
• DKL+94: David J. DeWitt , Navin Kabra , Jun Luo , Jignesh M. Patel , Jie-Bing Yu, Client-Server Paradise, Proceedings of the 20th International Conference on Very Large Data Bases, p.558-569, September 12-15, 1994
• DLPY93: D. J. DeWitt, J. Luo, J. M. PateI, and J. Yu. "Paradise -A Parallel Geographic Information System". In Proceedings of the A CM Workshop on Advance~ in Geographic Information Systems, Arlington, Virginia, November 1993.
• DNSS92: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Practical Skew Handling in Parallel Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.27-40, August 23-27, 1992
• GS87: 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]
• Gün93: 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
• HNKT90: 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
• HS95: 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
• KHT89: Masaru Kitsuregawa , Lilian Harada , Mikio Takagi, Join Strategies on KB-Tree Indexed Relations, Proceedings of the Fifth International Conference on Data Engineering, p.85-93, February 06-10, 1989
• LR94: 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
• LR95: 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
• LR96: 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
• MC80: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• MGR91: D.J. Maguire, M. E Goodchild, and D. W. Rhind. "Geographic h~formation Systems" volume 1. Longman Scientific & Technical, copublishect in the US with John Wiley & Sons, Inc. New York, 1991.
• 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]
• NS86: Randal C. Nelson , Hanan Samet, A consistent hierarchical representation for vector data, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.197-206, Aug. 1986
• OM84: 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]
• OM88: J. A. Orenstein , F. A. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application, IEEE Transactions on Software Engineering, v.14 n.5, p.611-629, May 1988 [doi>10.1109/32.6139]
• Ore86: 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
• 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
• PD: J. M. Patel and D. J. DeWitt. "Partition Based Spatial-Merge Join". http://www.cs.wisc.edu/paradise/paradise.papers.html.
• PS88: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Rot91: D. Rotem. "Spatial Join Indices". in IEEE Transactions on Knowledge and Data Engineering, Kobe, April 1991.
• SFGM93: Michael Stonebraker , Jim Frew , Kenn Gardels , Jeff Meredith, The SEQUOIA 2000 storage benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.2-11, May 25-28, 1993, Washington, D.C., United States
• Sto86: M. Stonebraker. "The Case for Shared Nothing". Database Engineering, 9( 1 ), 1986.
• Tig: U.S. Bureau of the Census, Washington, DC. "TIGER~Line Files(TM). 1992 Technical Documentation".
• TY95: Kian-Lee Tan , Jeffrey X. Yu, A Performance Study of Declustering Strategies for Parallel Spatial Databases, Proceedings of the 6th International Conference on Database and Expert Systems Applications, p.157-166, September 04-08, 1995
• Ube94: Michael Ubell, The Montage extensible DataBlade architecture, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.482, May 24-27, 1994, Minneapolis, Minnesota, United States
• 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]
• ZG90: Hansjorrg Zeller , Jim Gray, An adaptive hash join algorithm for multiuser environments, Proceedings of the sixteenth international conference on Very large databases, p.186-197, September 1990, Brisbane, Australia

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Measurement, Performance, Theory