고 밀도 영역을 이용한 향상된 2차원 히스토그램 기법

Abstract

히스토그램은 데이타베이스 시스템에서 질의 결과 크기를 추정하는 데 널리 이용되고 있다. 히스토그램 기법에서 질의 결과 크기에 대한 추정은 각 버킷 영역 내의 객체들이 균등하게 분포한다는 가정 하에 이루어진다. 그러나, 주어진 질의 영역 내의 객체들은 균등하게 분포하지 않을 수 있다. 다시 말해서, 버킷 영역 내에 높은 밀도의 객체 군집 즉 클러스터가 존재할 수 있으며 이로 인하여 히스토그램의 정확도가 현저히 저하될 수 있다. 본 연구의 목적은 히스토그램의 정확도를 향상시키는 데 있다. 이를 위하여 본 연구는 클러스터를 고려한 새로운 히스토그램 기법을 제안한다. 제안하는 기법은 주어진 데이타 분포 내에 존재하는 고 밀도 영역을 탐색하고 이를 히스토그램 생성에 활용한다. 제안하는 기법은 클러스터에 의한 정확도 저하를 효과적으로 감소시킴으로써 데이타가 균등하게 분포하지 않은 상황에서 향상된 성능을 제공할 수 있다. 실험을 통해 본 연구는 제안하는 기법이 기존 기법의 성능을 최대 74% 향상시킴을 확인하였다.