Selectivity Estimation Using Compressed Spatial Histogram 


Vol. 11,  No. 2, pp. 281-292, Apr.  2004
10.3745/KIPSTD.2004.11.2.281


PDF
  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
  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.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals