Transformation-based spatial join

ABSTRACT

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. A number of spatial join algorithms have recently been proposed in the literature. Most of them, however, perform the join in the original space. Joining in the original space has a drawback of dealing with sizes of objects and thus has difficulty in developing a formal algorithm that does not rely on heuristics. In this paper, we propose a spatial join algorithm based on the transformation technique. An object having a size in the two-dimensional original space is transformed into a point in the four-dimensional transform space, and the join is performed on these point objects. This can be easily extended to n-dimensional cases. We show the excellence of the proposed approach through analysis and extensive experiments. The results show that the proposed algorithm has a performance generally better than that of the R*-based algorithm proposed by Brinkhoff et al. This is a strong indicating that corner transformation preserves clustering among objects and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely affect clustering. We believe that our result will provide a new insight towards transformation-based spatial query processing.

REFERENCES

• 1: 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
• 2: 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
• 3: 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
• 4: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• 5: Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 6: A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
• 7: K. Hinrichs and J. Nievergelt, "The Grid File: A Data Structure Designed to Support Proximity Queries on Spatial Objects," In Proc. Infl Workshop on Graph Theoretic Concepts in Computer Science, pp. 100-113, 1983.
• 8: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 9: 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
• 10: 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
• 11: Hongjun Lu , Beng Chin Ooi , Kian-Lee Tan, On Spatially Partitioned Temporal Join, Proceedings of the 20th International Conference on Very Large Data Bases, p.546-557, September 12-15, 1994
• 12: 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]
• 13: 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
• 14: Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben, The Transformation Technique for Spatial Objects Revisited, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.73-88, June 23-25, 1993
• 15: 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
• 16: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 17: Bernhard Seeger , Hans-Peter Kriegel, Techniques for Design and Implementation of Efficient Spatial Access Methods, Proceedings of the 14th International Conference on Very Large Data Bases, p.360-371, August 29-September 01, 1988
• 18: Bernhard Seeger , Hans-Peter Kriegel, The buddy tree: an efficient and robust access method for spatial data base, Proceedings of the sixteenth international conference on Very large databases, p.590-601, September 1990, Brisbane, Australia
• 19: Hans-Werner Six , Peter Widmayer, Spatial Searching in Geometric Databases, Proceedings of the Fourth International Conference on Data Engineering, p.496-503, February 01-05, 1988
• 20: J. W. Song, K. Y. Whang, and S. W. Kim, SpatiaI Join Processing Using Comer Transformation, Tech. Report CS/TR-96-107, Dept. of Computer Science, KAIST, Dec. 1996.
• 21: Ju-Won Song , Kyu-Young Whang , Young-Koo Lee , Min-Jae Lee , Sang-Wook Kim, Spatial Join Processing Using Corner Transformation, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.688-695, July 1999 [doi>10.1109/69.790844]
• 22: K. Y. Whang and R. Krishnamurthy, Multilevel Grid Files, IBM Research Report RC 11516, 1985.
• 23: Kyu-Young Whang , Ravi Krishnamurthy, The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure, Proceedings of the Second International Symposium on Database Systems for Advanced Applications, p.449-459, April 02-04, 1991
• 24: Kyu Young Whang , Sang Wook Kim , Gio Wiederhold, Dynamic maintenance of data distribution for selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.1, p.29-51, January 1994 [doi>10.1007/BF01231357]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory