SDBMS (spatial database management systems) is DBMS (database management systems) for spatial datasets. Selectivity is the number of objects that have an intersection with the query rectangle. Fast selectivity estimation with less error is usable for query optimization and interactive query processing. Wavelet, sampling, and histogram are used for selectivity estimation. This paper focuses on selectivity estimation using histogram method.
Histogram is summary information of dataset. Histograms may be divided into two categories: bucket histograms and cell density based histograms. Bucket histograms always allocate buckets on necessary space, so there is no unnecessary bucket. But a bucket needs much memory for representation. A cell of cell density based histograms can represent with less memory. But cells may be allocated on unnecessary space.
This paper suggests new cell density based histogram method using multiple grids. This method has advantages of both of bucket histograms and cell density based histograms. By using multiple grids, there is no memory loss for unnecessary space. The space which needs more detail representation represents by many cells of grids in detail.
This paper have shown through experiments our method provides more accurate than most other existing methods, and especially existing cell density based histogram method by 9.8 ~ 27.1 times less error.
공간 데이타베이스 관리 시스템은 공간 객체를 저장하는 특수한 데이타베이스 관리 시스템이다. 선택도는 특정 질의의 결과의 수이다. 선택도 추정을 빠르고 적은 오차로 구하는 것은 질의 최적화 및 대화식 질의 처리 등 에서 필요한 기술이다. 선택도 추정을 위해 wavelet, sampling, histogram 등의 기법을 사용하는데 본 논문에서는 히스토그램을 이용한 선택도 추정에 대해 집중적으로 알아본다.
히스토그램은 데이타 분포에 관한 요약 정보이다. 히스토그램은 크게 버킷 히스토그램과 셀 밀도 기반 히스토그램으로 분류 할 수 있다. 버킷 히스토그램은 필요 없는 공간에 버킷을 배치하지 않고 필요한 공간에 버킷을 배치함으로써 필요 없는 버킷이 없는 장점이 있다. 하지만 버킷을 표현하는데 많은 메모리를 사용한다. 셀 밀도 기반 히스토그램은 적은 메모리로 셀을 많이 표현할 수 있다. 하지만 셀이 필요 없는 위치에도 할당되는 경우가 발생할 수 있다.
본 논문은 다수의 그리드를 이용한 새로운 셀 밀도 기반 히스토그램 기법를 제안한다. 이 기법은 버킷 히스토그램과 셀 밀도 기반 히스토그램의 장점을 모두 가진다. 다수의 그리드를 통해 필요 없는 공간에 소요되는 메모리 낭비를 줄이고 필요한 공간에 메모리 사용을 집중한다. 자세한 표현이 필요한 공간에서는 그리드를 이용하여 많은 수의 셀로 자세하게 표현한다.
실험결과 본 논문에서 제안한 기법이 기존 셀 밀도 기반 히스토그램 기법보다 9.8 ~ 23.2배 좋은 성능을 보이는 것을 확인하였고, 대다수의 기존 히스토그램 기법보다 좋은 성능을 보이는 것을 확인하였다.
