The histogram is a data structure of a large dataset for selectivity estimation. Selectivity estimation means the fast approximation of the frequency within the region of a query. In this thesis, we focus on multidimensional histograms, especially 2-dimensional histograms. At the time of selectivity estimation, buckets partially overlapping with a query return the approximated value assuming that all objects within them are uniformly distributed. Since, however, the objects within the region of a query are not likely to be uniformly distributed, the skew in buckets commonly degrades the accuracy of a histogram. Our aim is to utilize the skew information in a bucket to enhance the accuracy of selectivity estimation. We propose a method that explicitly associates the skew information with a bucket. We present new schemes to formally define the skew information, and present algorithms that efficiently find the skew information. We show through experiments on the benchmarking datasets that our proposed method provides better performance than other existing methods.
히스토그램은 선택도 추정(selectivity estimation)에 널리 사용되는 자료구조이다. 선택도 추정이란 질의 내에 속하는 객체 혹은 튜플의 수(selectivity)를 빠르게 근사(estimation)하는 것을 의미한다. 본 연구는 다차원 히스토그램에 초점을 맞추고 있으며, 특별히 응용분야가 많은 2차원 히스토그램을 제안한다. 선택도 추정 시, 질의와 부분적으로 겹치는 버킷은 버킷 내가 균등하다는 가정 하에 근사값을 제시한다. 그러나, 대부분의 경우 버킷 내의 객체들은 균등하게 분포하지 않는다. 버킷 내의 스큐는 히스토그램의 정확도를 손상시킬 수 있다. 본 연구의 목적은 버킷 내의 스큐 정보를 활용하여 선택도 추정의 정확도를 향상시키는 것이다. 본 연구는 정확도 향상을 위한 새로운 기법으로, 스큐 정보를 명시적으로 표현하는 히스토그램을 제안한다. 그리고, 이를 위한 방법론으로 2차원의 스큐를 정의하는 기법과 2차원의 스큐를 효과적으로 찾는 알고리즘을 제안한다. 벤치마킹 데이터셋을 사용한 다양한 실험을 통하여, 본 연구는 기존 연구보다 정확도를 향상시켰음을 확인하였다.
