For multimedia databases, the fuzzy query consists of a logical combination of content based similarity queries on features such as the color and the shape which are represented in continuous dimensions. Since the similarity query is intrinsically multi-dimensional, the multi-dimensional selectivity estimation is required in order to optimize a fuzzy query. For traditional databases, the query optimizer requires the multi-dimensional selectivity estimation for queries referencing multiple attributes from the same relation. The histogram is popularly used for the selectivity estimation. But the histogram has shortcomings as follows: First, it is difficult to estimate the selectivity of a similarity query using the histogram, since the typical similarity query has the shape of the hyper sphere and the range of features is continuous. Second, the histogram is efficient and practically the most preferable at a low dimensionality, particularly 1-dimension. However it suffers from the `dimensionality curses` at a high dimensionality, since the number of buckets is increased explosively. This causes severe problems of the high storage overhead and the high error rate at a high dimensionality. Third, most histograms do not support dynamic updates. This causes the periodical reconstruction of the histogram.
With above motivations, we propose a novel approach for the multi-dimensional selectivity estimation of a query in continuous dimensions. Compressed information from a large number of small-sized buckets is maintained using the discrete cosine transform (DCT). This enables low error rates and low storage overheads even in a high dimensionality. Using the continuity property of the DCT we can make rectangles of any sizes in the data space in order to get approximate selectivity answers of queries of any shapes. In addition, this approach supports dynamic data updates, therefore it has the advantage of eliminating the overhead of periodical reconstructions of the compressed information. As applications of multi-dimensional selectivity estimation in multimedia databases, we applied the method to the selectivity estimation of the similarity query like the nearest neighbor query frequently used in multimedia databases and proposed novel distributed similarity search algorithms that solve the collection fusion problem for multimedia databases on the distributed heterogeneous environment like the Web. Extensive experimental results show advantages of the proposed approach
멀티미디어 데이터 베이스에서 사용되는 퍼지 질의는 유사성 질의의 논리적인 결합으로 구성되어 있으며, 유사성 질의는 연속된 값으로 표시되는 색과 질감과 같은 특징에 대한 내용 기반 검색을 말한다. 유사성 질의는 본질적으로 다차원이기 때문에 퍼지 질의를 최적화하려면 다차원 선택율 추정이 필요하다. 전통적인 데이터베이스에서는 질의 최적화기가 질의를 최적화할 때, 질의의 애트리뷰트들이 같은 릴레이션에 속하면, 다차원 선택율 추정이 필요하다. 선택율 추정에는 대부분 히스토그램이 사용되고 있다. 그러나 히스토그램에는 다음과 같은 단점들이 있다. 첫째, 유사성질의는 그 형태가 구형이고 연속된 범위를 가지므로 선택율을 추정하기 어렵다. 두번째, 히스토그램은 낮은 차원에서는, 특히 일차원에서는, 효율적이고 실용적으로 가장 많이 사용되고 있으나, 차원이 증가함에 따라서 버켓의 개수가 폭발적으로 증가하는 현상이 발생하여 고차원에서는 사용할 수 없다. 즉, 히스토그램은 고차원에서는 많은 저장 공간의 요구와 높은 에러율이라는 심각한 문제를 야기한다. 세번째, 대부분의 히스토그램은 동적인 데이터 갱신을 지원하지 않는다. 즉 히스토그램을 정기적으로 새로 구축해주어야 한다.
이상과 같은 문제점들을 해결하기 위해서, 연속적인 차원에서의 다차원 선택율 추정에 관한 새로운 기법을 제안한다. 제안된 방법은 이산 여현 변환 (Discrete Cosine Transform, DCT)을 사용하여 많은 개수의 크기가 작고 버켓들로부터 압축된 정보를 구한다. 이 방법은 고차원에서도 에러율이 작고 저장 공간을 적게 필요로 한다. 또한 DCT의 연속 성질을 활용하면 임의의 형태를 갖는 질의의 선택율을 추정하기 위해서 데이터 공간 안에 임의의 크기의 직각형을 만들 수 있다. 또한 이 방법은 동적인 데이터 갱신을 지원하기 때문에 압축된 정보를 주기적으로 다시 만들어 주어야 하는 부담이 없다는 장점이 있다. 제안된 방법의 응용으로서, 멀티미디어 데이터베이스에서 자주 사용되는 최근접 질의와 같은 유사성 질의의 선택율 추정에 적용하였고, 분산되어 있고 이질적인 특성을 갖는 웹과 같은 환경에서 멀티미디어 데이터베이스의 수집 융합 (Collection Fusion) 문제를 해결하는 분산 유사성 검색 알고리즘들을 제안한다. 광범위한 실험들에 대한 결과는 본 논문에서 제시된 방법의 우수성을 보여주고 있다.
