The histogram, which is a simple representation for distribution of a large data set, is widely used for estimation of the query result sizes that has many applications for various types of query processing. Estimates for the histogram buckets that partially overlap with the query region are computed based on the assumption that all the data objects in a bucket are uniformly distributed. However, it has been shown to be intractable to organize histogram buckets such that objects in every bucket are uniformly distributed. In most heuristic histogram methods, there often exist skews or clusters of objects in data distributions within the histogram buckets, which degrades the accuracy of the estimates. In this dissertation, we explore the issue of how to construct effective histograms for estimation of the result sizes of multi-dimensional range queries. We propose three new histogram methods: the skew-tolerant histogram, the quad tree-based histogram, and the minimal-skew cover histogram.
In the first part of this dissertation, we propose a new histogram method, called the skew-tolerant histogram for two or three dimensional geographic data objects that are used in many real-world applications in practice. The proposed method provides a significantly enhanced accuracy in a robust manner even for the data set that has a highly skewed distribution. When constructing a histogram, our method detects and utilizes the clusters of objects present in various parts of a data set. By directly utilizing clusters in organizing buckets, our proposed method can provide an enhanced accuracy in a robust manner over skewed distributions. Through extensive performance experiments, we show a considerable accuracy improvement of the proposed method.
In the second part of this dissertation, we propose a new histogram method, called the quad tree-based histogram that is based on the use of the existing quad tree for multi-dimensional data sets. The compact representation of the target data distribution obtainable from the existing quad tree allows us a fast construction of histograms with the minimum number of scanning of the underlying data. In addition to the advantage of computation time, the proposed method also provides a better performance than other existing methods with respect to the quality of the histogram. We present an iterative technique for skew-tolerant organization of histograms and give extensive experimental results that show that our method provides better performance than other existing methods in accuracy as well as computational efficiency.
In the last part of this dissertation, we propose a new histogram method, called the minimal-skew cover histogram. In our method, the target space is divided into several partitions and then a hierarchy of partitions, i.e., a space partitioning tree, is constructed. In attempting to construct a set of buckets such that data in each bucket are as uniformly distributed as possible, we exploit the covers or the vertex cuts of a space partitioning tree, where each cover divides the target space in a different manner. Among all the possible covers, a minimal skew cover, i.e., where the sum of skews of nodes in the cover is the minimum, is searched and organized into a set of histogram buckets. The results of extensive performance experiments demonstrate that our method provides a significant improvement in terms of estimation accuracy over other existing methods and the robustness to the skew of data distribution.
히스토그램은 데이터 분포에 관한 요약 정보이며, 데이터베이스 질의 처리 과정에서 질의 결과 크기 즉 선택도를 추정하는 데 널리 활용되고 있다. 히스토그램 버킷 내 모든 데이터가 균등하게 분포한다는 가정 하에, 버킷에 대한 추정이 이루어진다. 그러나, 모든 버킷 내 데이터들이 균등하게 분포하는 최적 히스토그램의 생성 문제는 $\It{NP-hard}$임이 증명되었다. 대부분의 기존 히스토그램 기법들은 발견적 해결 방식에 기초하며, 버킷 영역 내 데이터 불균등이 자주 발생하기 때문에 선택도 추정의 정확도가 크게 저해될 수 있다. 본 논문은 다차원 영역 질의의 결과 크기를 추정하는 데 효과적인 히스토그램 기법들을 제안한다.
본 논문의 첫 번째 부분에서, 우리는 다양한 응용이 존재하는 $ 2 \sim 3차원$ 지리 데이터를 위한 히스토그램 기법을 제안한다. 제안하는 기법은 주어진 데이터 셋 내에 존재하는 높은 밀도를 가지는 객체들의 군집을 탐색하고 이를 히스토그램 버킷으로 구성한다. 데이터 분포의 균등함을 저해할 수 있는 고-밀도 객체 군집을 버킷으로 구성함으로써, 제안하는 기법은 데이터 셋이 균등하지 않은 여러 상황에서 기존 방식들보다 일관성 있게 향상된 추정 정확도를 제공한다. 다양한 성능 평가 실험을 통하여 우리는 제안하는 기법이 기존 방식보다 유의성 있게 향상된 추정 정확도를 제공함을 보인다.
본 논문의 두 번째 부분에서, 우리는 기존 다차원 인덱스 구조를 이용하는 새로운 다차원 히스토그램 기법을 제안한다. 인덱스 구조로부터 획득 가능한 데이터 분포에 관한 간략한 정보는 히스토그램을 신속하게 생성하는 데 이용될 수 있다. 우리는 데이터 셋에 대한 최소 횟수의 읽기만을 수행하며 히스토그램을 구성하는 새로운 기법을 제안한다. 인덱스 구조로서 가장 널리 사용되고 있는 다차원 인덱스 중의 하나인 Quad tree가 이용되었다. 다양한 성능 평가 실험을 통하여 우리는 제안하는 기법이 기존 방식들보다 향상된 추정 정확도뿐만 아니라 높은 계산 효율성을 제공함을 보인다.
본 논문의 마지막 부분에서, 우리는 공간 분할 트리의 최소 데이터-불균등 커버를 이용한 새로운 다차원 히스토그램 기법을 제안한다. 제안하는 기법은 주어진 데이터 공간을 여러 하위공간들로 분할하고 분할된 하위공간들의 포함 관계를 나타내는 공간 분할 트리를 생성한다. 공간 분할 트리에 대한 노드 컷 혹은 커버들은 주어진 데이터 공간을 서로 다른 방식으로 분할한다. 제안하는 기법은 모든 가능한 커버들 중 커버 내 노드의 데이터-불균등 수치의 합이 최소가 되는 최소 데이터-불균등 커버를 탐색하고 이를 히스토그램으로 구성한다. 다양한 성능 평가 실험의 결과는 제안하는 기법이 기존 방식들에 비해 월등히 향상된 추정 정확도를 제공함을 보인다.
