누적밀도 웨이블릿 히스토그램을 이용한 공간 선택율 추정 = Spatial Selectivity Estimation using Cumulative Wavelet Histograms

국문 초록 (Abstract)

선택율 추정 기법들의 공통적인 목표는 데이타의 요약 정보를 적은 저장 공간에 유지하고, 추정된 값과 질의 결과에 대한 오차를 최소화하는 것이다. 방대한 양의 공간 데이타에 대한 선택율 추정의 경우, 정확한 결과를 얻기 위해서는 공간 데이타의 분포를 반영하는 요약 정보를 필요로 하며, 그러한 요약 정보를 생성하기 위해서는 많은 저장 공간을 필요로 한다.
따라서, 이 논문에서는 적은 저장 공간을 사용하면서, 정확성 높은 선택율을 추정하는 누적밀도 웨이블릿 히스토그램을 제안한다. 이 히스토그램은 기존의 누적밀도 히스토그램에 유지되는 각 서브 히스토그램에 대해 웨이블릿 변환을 적용함으로써, 보다 적은 저장 공간에서 높은 정확도의 선택율을 얻을 수 있다. 우리는 실험결과를 통하여 기존 히스토그램의 저장 공간에 25%~50%만을 사용하여 높은 정확도의 선택율 추정 결과를 보임으로써, 기존의 다른 선택율 추정기법들이 갖는 저장공간에 대한 제약사항을 해결함과 동시에 적은 저장공간을 사용하여 높은 정확도의 선택율 추정이 가능함을 확인 하였다. 이 논문에서 제안된 기법은 공간 데이타베이스에서의 공간 범위 질의에 대한 정확성 높은 선택율을 추정하기 위해 사용될 수 있다.

다국어 초록 (Multilingual Abstract)

The purpose of selectivity estimation is to maintain the summary data in a very small memory space and to minimize the error of estimated value and query result. In case of estimating selectivity for large spatial data, the existing works need summary information which reflect spatial data distribution well to get the exact result for query. In order to get such summary information, they require a much memory space.
Therefore in this paper, we propose a new technique cumulative density wavelet Histogram, called CDW Histogram, which gets a high accurate selectivity in small memory space. The proposed method is to utilize the sub-histograms created by CD histogram. The each sub-histograms are used to generate the wavelet summary information by applying the wavelet transform. This fact gives us good selectivity even if the memory size is very small. The experimental results show that the proposed method simultaneously takes full advantage of their strong points - gets a good selectivity using the previous histogram in (25%~50%) memory space and is superior to the existing selectivity estimation techniques. The proposed technique can be used to accurately quantify the selectivity of the spatial range query in databases which have very restrictive memory.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. 누적밀도 웨이블릿 히스토그램
• 4. 선택율 추정
• 5. 실험 및 평가
• 6. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "일반화된 누적밀도 히스토그램을 이용한 공간 선택율 추정" 11 (11): 963-990, 2004.

2 "압축된 공간 히스토그램을 이용한 선택율 추정 기법" 11 (11): 281-292, 2004.

3 "다차원 히스토그램을 이용한 공간 위상 술어의 선택도 추정 기법" 6 (6): 841-850, 1999.4.

4 "Wavelet-based cost Estimation for Spatial Queries" 2001-, 2001

5 "Wavelet for Computer Graphics Theory and Applications" Morgan Kaufmann 1996.

6 "Spatial Selectivity Estimation using Compressed Histogram Information" 489-3399 494, 2005.3.

7 "Selectivity for spatial joins with geometric selections" 609-626, 2002.

8 "Selectivity estimation in spatial databases" 13-24, 1999.

9 "Selectivity Estimation for Spatial Databases" 2003.11

10 "Improved Histograms for Selectivity Estimation of Range Predicates" 294-305, 1996.

11 "Dynamic Maintenance of Wavelet-Based Histograms" 101-110, 2000.

12 "Approximate Computation of Multidimensional Aggregates of Sparse Data using Wavelets" 193-204, 1999.

13 "Analyzing Range Queries on Spatial Data" 525-534, 2000.