Spatial Selectivity Estimation of Window Query

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.