다수의 그리드를 이용한 셀 밀도 기반 히스토그램 기법

Abstract

공간 데이타베이스 관리 시스템은 공간 객체를 저장하는 특수한 데이타베이스 관리 시스템이다. 선택도는 특정 질의의 결과의 수이다. 선택도 추정을 빠르고 적은 오차로 구하는 것은 질의 최적화 및 대화식 질의 처리 등 에서 필요한 기술이다. 선택도 추정을 위해 wavelet, sampling, histogram 등의 기법을 사용하는데 본 논문에서는 히스토그램을 이용한 선택도 추정에 대해 집중적으로 알아본다. 히스토그램은 데이타 분포에 관한 요약 정보이다. 히스토그램은 크게 버킷 히스토그램과 셀 밀도 기반 히스토그램으로 분류 할 수 있다. 버킷 히스토그램은 필요 없는 공간에 버킷을 배치하지 않고 필요한 공간에 버킷을 배치함으로써 필요 없는 버킷이 없는 장점이 있다. 하지만 버킷을 표현하는데 많은 메모리를 사용한다. 셀 밀도 기반 히스토그램은 적은 메모리로 셀을 많이 표현할 수 있다. 하지만 셀이 필요 없는 위치에도 할당되는 경우가 발생할 수 있다. 본 논문은 다수의 그리드를 이용한 새로운 셀 밀도 기반 히스토그램 기법를 제안한다. 이 기법은 버킷 히스토그램과 셀 밀도 기반 히스토그램의 장점을 모두 가진다. 다수의 그리드를 통해 필요 없는 공간에 소요되는 메모리 낭비를 줄이고 필요한 공간에 메모리 사용을 집중한다. 자세한 표현이 필요한 공간에서는 그리드를 이용하여 많은 수의 셀로 자세하게 표현한다. 실험결과 본 논문에서 제안한 기법이 기존 셀 밀도 기반 히스토그램 기법보다 9.8 ~ 23.2배 좋은 성능을 보이는 것을 확인하였고, 대다수의 기존 히스토그램 기법보다 좋은 성능을 보이는 것을 확인하였다.