Spatial hash-joins

ABSTRACT

We examine how to apply the hash-join paradigm to spatial joins, and define a new framework for spatial hash-joins. Our spatial partition functions have two components: a set of bucket extents and an assignment function, which may map a data item into multiple buckets. Furthermore, the partition functions for the two input datasets may be different.We have designed and tested a spatial hash-join method based on this framework. The partition function for the inner dataset is initialized by sampling the dataset, and evolves as data are inserted. The partition function for the outer dataset is immutable, but may replicate a data item from the outer dataset into multiple buckets. The method mirrors relational hash-joins in other aspects. Our method needs no pre-computed indices. It is therefore applicable to a wide range of spatial joins.Our experiments show that our method outperforms current spatial join algorithms based on tree matching by a wide margin. Further, its performance is superior even when the tree-based methods have pre-computed indices. This makes the spatial hash-join method highly competitive both when the input datasets are dynamically generated and when the datasets have pre-computed indices.

REFERENCES

• 1: M. Kitsuregawa, H. Tanaka, and T. Moto-Oka, "Application of hash to data base machine and its architecture," New Generation Computing, vol. 1, no. 1, pp. 66-74, 1983.
• 2: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 3: D. J. DeWitt and R. Gerber, "Multiprocessor hashbased join algorithms," in Proceedings of VLDB 85, pp. 151-164, Stockholm, 1985.
• 4: Masaya Nakayama , Masaru Kitsuregawa , Mikio Takagi, Hash-Partitioned Join Method Using Dynamic Destaging Strategy, Proceedings of the 14th International Conference on Very Large Data Bases, p.468-478, August 29-September 01, 1988
• 5: M. Kitsuregawa , M. Nakayama , M. Takagi, The effect of bucket size tuning in the dynamic hybrid GRACE hash join method, Proceedings of the 15th international conference on Very large data bases, p.257-266, July 1989, Amsterdam, The Netherlands
• 6: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• 7: 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]
• 8: 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
• 9: 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
• 10: 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
• 11: Doron Rotem, Spatial Join Indices, Proceedings of the Seventh International Conference on Data Engineering, p.500-509, April 08-12, 1991
• 12: 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
• 13: 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
• 14: 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
• 15: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• 16: 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]
• 17: 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
• 18: 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
• 19: 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
• 20: 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
• 21: 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
• 22: 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
• 23: Christos Faloutsos , Yi Rong, DOT: A Spatial Access Method Using Fractals, Proceedings of the Seventh International Conference on Data Engineering, p.152-159, April 08-12, 1991
• 24: B. of Census, "Tiger/lines precensus files: 1990 technical documentation," Technical report, Bureau of Census, Washington, DC, 1989.
• 25: 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

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:
Measurement, Performance, Theory