Selectivity Estimation for Spatial Joins with Geometric Selections

Spatial join is an expensive operation that is commonly used in spatialdatabase systems. In order to generate efficient query plans for thequeries involving spatial join operations, it is crucial to obtainaccurate selectivity estimates for these operations. In this paperwe introduce a framework for estimating the selectivity of spatialjoins constrained by geometric selections. The center piece of theframework is Euler Histogram, which decomposes the estimationprocess into estimations on vertices, edges and faces. Based on thecharacteristics of different datasets, different probabilistic modelscan be plugged into the framework to provide better estimation results.To demonstrate the effectiveness of this framework, we implement itby incorporating two existing probabilistic models, and comparethe performance with the Geometric Histogram [AnYS01] andthe algorithm recently proposed by Mamoulis and Papadias[MamoulisP01].