Multidimensional histograms have been widely used in summarizing the distribution of large data sets for various types of query processing in practice. As noted in the literature, some of existing index structures can be utilized as a good start point for the construction of multidimensional histograms. When an index structure already exists and is used for some application, the process of constructing a histogram can be accelerated by using the data partition information implied in the index.
In this paper, we propose an efficient multidimensional histogram method based on the use of the $R^* -tree$, which is a popular index structure for multidimensional data. The compact representation of the target data obtainable from the $R^* -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 histograms. We present a hill climbing technique for skew-tolerant organization of histograms. We focus on the histograms for two or three dimensional data objects that are used in many real-world applications in practice such as geographic information processing. Through performance experiments, we show that the proposed method works better than other existing methods in terms of accuracy as well as computational efficiency.
다차원 히스토그램은 다양한 질의 처리를 위해 데이터 셋의 분포를 요약하는 데 널리 사용되고 있다. 논문에서 언급된 것과 같이, 몇몇 인덱스 구조는 다차원 히스토그램의 생성을 위한 좋은 시작점으로 활용될 수 있다. 인덱스 구조가 이미 존재하고, 어떤 목적을 위해 사용되고 있는 경우에, 이러한 인덱스로부터 얻을 수 있는 데이터 분할 정보를 이용하여 히스토그램을 생성하는 과정을 효율적으로 수행할 수 있다.
본 논문에서, 우리는 다차원 데이터에 대해 널리 활용되는 인덱스 구조인 $R^* -tree$ 의 이용에 기반을 두는 효율적인 히스토그램 기법을 제안한다. R*-tree로부터 획득되는 데이터의 간결한 형태는 데이터 접근을 최소화하며 빠른 히스토그램의 생성을 가능하게 한다. 계산 시간의 이점과 더불어, 제안하는 기법은 기존 기법에 비해 히스토그램의 정확도 측면에서도 뛰어난 성능을 제공한다. 우리는 데이터 분포의 불균등에 잘 견디는 히스토그램 구성을 위해 hill climbing 전략을 제시했다. 우리는 지리 정보 처리와 같이 실제 많은 분야에서 사용되는 2차원 또는 3차원 데이터 객체를 위한 히스토그램에 초점을 두었다. 우리는 성능 평가 실험을 통해, 제안하는 기법이 기존 기법에 비해 속도뿐만 아니라 정확도에서도 뛰어남을 보였다.
