Selectivity Estimation Using Compressed Spatial Histogram


The KIPS Transactions:PartD, Vol. 11, No. 2, pp. 281-292, Apr. 2004
10.3745/KIPSTD.2004.11.2.281,   PDF Download:

Abstract

Selectivity estimation for spatial query is very important process used in finding the most efficient execution plan. Many works have been performed to estimate accurate selectivity. Although they deal with some problems such as false-count, multi-count, they can not get such effects in little memory space. Therefore, we propose a new technique called MW Histogram which is able to compress summary data and get reasonable results and has a flexible structure to react dynamic update. Our method is based on two techniques : (a) MinSkew partitioning algorithm which deal with skewed spatial datasets efficiently (b) Wavelet transformation which compression effect is proven. The experimental results showed that the MW Histogram which the buckets and wavelet coefficients ratio is 0.3 is lower relative error than MinSkew Histogram about 5%~20% queries, demonstrates that MW histogram gets a good selectivity in little memory.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. J. Hui, L. J. Yeol, K. S. Ho, L. G. Ho, "Selectivity Estimation Using Compressed Spatial Histogram," The KIPS Transactions:PartD, vol. 11, no. 2, pp. 281-292, 2004. DOI: 10.3745/KIPSTD.2004.11.2.281.

[ACM Style]
Ji Jeong Hui, Lee Jin Yeol, Kim Sang Ho, and Lyu Geun Ho. 2004. Selectivity Estimation Using Compressed Spatial Histogram. The KIPS Transactions:PartD, 11, 2, (2004), 281-292. DOI: 10.3745/KIPSTD.2004.11.2.281.