一种基于窗口查询的空间选择率估算方法

Spatial Selectivity Estimation of Window Query

针对任意空间查询区域提出了一种基于CD直方图选择率的估计方法,确定了影响空间点(x,y)直方图估计值的相关格子,并对其中确定的部分直接引用,对于不确定的部分则充分利用格子提供的信息进行了修正,从而可以较为精确地计算出空间点(x,y)的估计值,为提高查询选择率估计值的准确性奠定了基础。

Spatial selectivity is significant to improve the accuracy of spatial query cost estimation. This paper proposes an accurate spatial selectivity estimation method based on Cumulative Density （CD） Histogram, which can deal with any arbitrary spatial query window. The method firstly estimates the histogram values of four corners of the spatial query window in Hll, Hlr, Hul, Hur histogram （recorded as S1, S2, S3 , S4 respectively）, and then the selectivity estimation of the spatial query is S1- S2- S3 ＋ S4. For estimate the value of any point in the histogram, the paper firstly ravels these grids which can affect estimation value of point（x, y） in histogram according to the principle of CD Histogram. We directly use these values of grids with certain values. To these grids without certain values, we amend it through the information provided by CD Histogram. These will make the amending more accurately, and improve the accuracy of selectivity estimation. This method can accurately estimate the query selectivity at arbitrary spatial query windows without add any additional assumption and storage disk, which can apply to a variety of vector data types, such as discrete, continuous distribution geographic data type, etc.