서지주요정보
Multi-dimensional selectivity estimation using compressed information = 압축된 정보를 사용한 다차원 선택율 추정
서명 / 저자 Multi-dimensional selectivity estimation using compressed information = 압축된 정보를 사용한 다차원 선택율 추정 / Ju-Hong Lee.
저자명 Lee, Ju-Hong ; 이주홍
발행사항 [대전 : 한국과학기술원, 2001].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8012165

소장위치/청구기호

학술문화관(문화관) 보존서고

DGSM 01008

SMS전송

도서상태

이용가능

대출가능

반납예정일

등록번호

9007510

소장위치/청구기호

서울 학위논문 서가

DGSM 01008 c. 2

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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) 문제를 해결하는 분산 유사성 검색 알고리즘들을 제안한다. 광범위한 실험들에 대한 결과는 본 논문에서 제시된 방법의 우수성을 보여주고 있다.

서지기타정보

서지기타정보
청구기호 {DGSM 01008
형태사항 viii, 106 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 이주홍
지도교수의 영문표기 : Chin-Wan Chung
지도교수의 한글표기 : 정진완
수록잡지명 : "Distributed similarity search algorithm in distributed heterogeneous multimedia databases". Information processing letters, v.75, Issue 1-2, pp.35-42 (2000)
학위논문 학위논문(박사) - 한국과학기술원 : 컴퓨터공학전공,
서지주기 Reference : p. 101-106
주제 Database
Query Optimization
Selectivity Estimation
Discrete Cosine Transform
Data COmpression
선택율추정
질의최적화
데이타베이스
이산여현변환
데이타압축
QR CODE qr code