Grid based methods for estimating spatial join selectivity

ABSTRACT

Spatial join is a fundamental operation for many spatial queries in Geographical Information Systems (GIS). Therefore, the query optimizer of a GIS needs to evaluate the selectivity of spatial joins, in order to find the best execution plan for a given query. This situation has made it necessary to find good and efficient estimators for spatial join selectivity. In particular, spatial join estimation with respect to sets of rectangles is necessary. Indeed, in GIS sets of rectangles are generated in order to produce a synthetic representation of real geometric values through the Minimum Bounding Rectangles (MBR).

Several methods for this estimation have been proposed in literature. One of the best methods is based on precalculated histograms, that describe the distribution of rectangles in the reference space using grid based data structures. The size of an histogram for a given dataset can be comparable to the size of the R-tree built on the same dataset [4].

In this paper we present a new technique for estimating spatial join selectivity considering sets of rectangles as datasets. In particular, we propose a technique that is independent of the distribution of the rectangles in the reference space and produces an auxiliary structure which is an order of magnitude smaller than the corresponding histogram. Indeed, the proposed technique is based on very few statistical parameters and on a unique grid shared by all datasets.

REFERENCES

• 1: Y. Theodoridis. The R-tree-portal, 2003. http://www.rtreeportal.org
• 2: D. J. Abel and D. M. Mark. A Comparative Analysis of some Two-dimensional Orderings. Int. J. Geographical Information Systems, 4(1):21--31, 1990.
• 3: Accurate Estimation of the Cost of Spatial Selections, Proceedings of the 16th International Conference on Data Engineering, p.123, February 28-March 03, 2000
• 4: Ning An , Zhen-Yu Yang , Anand Sivasubramaniam, Selectivity Estimation for Spatial Joins, Proceedings of the 17th International Conference on Data Engineering, p.368-375, April 02-06, 2001
• 5: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 6: Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
• 7: 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
• 8: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Selectivity Estimation for Spatial Joins with Geometric Selections, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.609-626, March 25-27, 2002
• 9: Eliseo Clementini , Paolino Di Felice , Peter van Oosterom, A Small Set of Formal Topological Relationships Suitable for End-User Interaction, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.277-295, June 23-25, 1993
• 10: Max J. Egenhofer, Reasoning about Binary Topological Relations, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.143-160, August 28-30, 1991
• 11: Christos Faloutsos , Bernhard Seeger , Agma Traina , Caetano Traina, Jr., Spatial join selectivity using power laws, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.177-188, May 15-18, 2000, Dallas, Texas, United States
• 12: 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
• 13: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• 14: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 15: 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
• 16: Nikos Mamoulis , Dimitris Papadias, Selectivity Estimation of Complex Spatial Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.155-174, July 12-15, 2001
• 17: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 18: Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis, Processing and optimization of multiway spatial joins using R-trees, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.44-55, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303981]
• 19: Ho-Hyun Park , Chin-Wan Chung, Complexity of estimating multi-way join result sizes for area skewed spatial data, Information Processing Letters, v.76 n.3, p.121-129, Dec. 15, 2000 [doi>10.1016/S0020-0190(00)00129-0]
• 20: Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237705]
• 21: Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis, Cost Models for Join Queries in Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.476-483, February 23-27, 1998

INDEX TERMS

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

General Terms:
Management, Theory

Keywords:
GIS, query optimization, spatial join