Selectivity estimation using compressed spatial information

Selectivity estimation using compressed spatial information

Spatial selectivity estimation is one of the essential studies to get query responses rapidly and accurately with the limitation of memory space. Currently, there exist several spatial selectivity estimation techniques such as random sampling, histogram, and parametric. Especially, Cumulative Density Histogram guarantees accurate estimation for rectangle object which has multiple-count problem. However, it requires large memory space because of retaining four sub-histograms for spatial data. Therefore in this paper, we propose a new technique Cumulative Density Wavelet Histogram, called CDWH, which is the combination of Cumulative Density Histogram and Haar Wavelet Transform, a compressed technique. The proposed method simultaneously takes full advantage of their strong points, high accuracy provided by the former and economization of memory space supported by the latter. Consequently, our technique is able to support estimates with relatively low error and retain similar estimates even if memory space is small.