zbMATH — the first resource for mathematics

Selectivity estimation for spatial joins with geometric selections. (English) Zbl 1054.68813
Jensen, Christian S. (ed.) et al., Advances in database technology - EDBT 2002. 8th international conference on extending database technology, Prague, Czech Republic, March 25-27, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43324-4). Lect. Notes Comput. Sci. 2287, 609-626 (2002).
Summary: Spatial join is an expensive operation that is commonly used in spatial database systems. In order to generate efficient query plans for the queries involving spatial join operations, it is crucial to obtain accurate selectivity estimates for these operations. In this paper we introduce a framework for estimating the selectivity of spatial joins constrained by geometric selections. The center piece of the framework is Euler Histogram, which decomposes the estimation process into estimations on vertices, edges and faces. Based on the characteristics of different datasets, different probabilistic models can be plugged into the framework to provide better estimation results. To demonstrate the effectiveness of this framework, we implement it by incorporating two existing probabilistic models, and compare the performance with the Geometric Histogram and the algorithm recently proposed by Mamoulis and Papadias.
For the entire collection see [Zbl 0987.68743].
68U99 Computing methodologies and applications
68P15 Database theory
Full Text: Link