Abstract
Selectivity Estimation for Spatial Joins with Geometric Selections
by: Chengyu Sun, Divyakant Agrawal, Amr El Abbadi
Abstract:
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].
Keywords:
spatial join, geometric selection, selectivity estimation
Date:
02 January 2002
Document: 2002-01
