멀티미디어 응용을 위한 차원 축소에 기반한 효율적인 색인 및 질의 처리

Abstract

멀티미디어 정보 검색에서 멀티미디어 데이터는 고차원 공간상의 벡터로 표현된다. 두 벡터간의 유사도를 계산하기 위한 척도로는 유클리드 거리가 널리 사용된다. 그러나 고차원 공간에서 유클리드 거리를 계산하는 것은 많은 연산을 필요로 한다. 따라서, 효율적인 질의 처리를 위해서는 벡터들 간의 유사도 계산을 빠르게 하는 것이 매우 중요하다. 효율적인 유사도 계산을 통해 질의 처리 성능을 높이기 위하여, 본 학위논문에서는 고차원 벡터의 놈과 각도 성분을 기반으로 하는 유클리드 거리의 근사 함수를 제안한다. 두 벡터간의 각도 성분을 근사하기 위하여, 본 학위논문에서는 기준 벡터라는 개념을 도입한다. 제안하는 기법은 근사된 각도 성분을 이용하여 유클리드 거리를 근사함으로써, 기존의 Cauchy-Schwartz 부등식을 이용하는 근사 기법에 비교하여 거리 근사 오차를 크게 줄일 수 있다. 또한, 제안하는 기법에 의한 거리 근사 값은 실제 유클리드 거리보다 항상 작거나 같음을 이론적으로 증명한다. 이는 근사된 거리를 이용한 멀티미디어 정보 검색에서 착오 기각을 발생하지 않음을 의미한다. 고차원 특징 벡터를 효율적으로 검색하기 위하여 다양한 색인 기법이 제안되어 왔다. 그러나 특징 벡터의 차원이 증가하면서 색인 기법의 효율성이 급격히 떨어지는 차원의 저주 문제가 발생한다. 차원의 저주 문제를 해결하기 위하여 색인하기 이전에 원 특징 벡터를 저차원 공간상의 벡터로 사상하는 차원 축소 기법이 제안된 바 있다. 본 학위논문에서는 벡터의 놈과 각도 성분을 이용하여 유클리드 거리를 근사하는 함수를 기반으로 하는 새로운 차원 축소 기법을 제안한다. 먼저, 유클리드 거리 근사를 위하여 추정된 각도의 오차의 발생 원인을 분석하고, 이 오차를 줄이기 위한 기본 방향을 제시한다. 제안하는 새로운 차원 축소 기법은 고차원 특징 벡터를 다수의 특징 서브 벡터들의 집합으로 분리하고, 각 특징 서브 벡터로부터 놈과 각도 성분을 근사하여 차원을 축소하는 기법이다. 각도 성분을 정확하게 근사하기 위해서는 올바른 기준 벡터의 설정이 필수적이다. 따라서 본 학위논문에서는 최적 기준 벡터의 조건을 제시하고, Levenberg-Marquardt 알고리즘을 이용하여 기준 벡터를 선정하는 방법을 제안한다. 또한, 축소된 저차원 공간상의 벡터들을 위한 새로운 거리 함수를 정의하고, 이 거리 함수가 유클리드 거리 함수의 하한 함수가 됨을 이론적으로 증명한다. 이는 제안된 기법이 착오 기각의 발생을 허용하지 않으면서 효과적으로 차원을 줄일 수 있음을 의미하는 것이다. 다차원 데이터 벡터를 색인하기 위하여 R*-tree 색인 구조가 널리 사용되어왔다. R*-tree를 사용한 검색에서 정답을 보장하면서 효율적으로 검색하기 위해서는 제약조건이 존재한다. R*-tree는 최소 경계 사각형(Minimum bounding Rectangle, MBR)을 기반으로 하기 때문에, 효율적인 검색을 위해서는 질의 영역이 MBR의 형태로 표현되어야 한다. 또한, 질의 벡터와 MBR까지의 거리는 질의 벡터와 해당 MBR 내의 어떤 벡터와의 거리보다 항상 작거나 같아야 한다. 본 학위논문에서는 이러한 제약조건을 만족하기 위하여 새로운 질의 영역을 정의한다. 정의한 질의 영역은 실제 질의 영역을 모두 포함한다. 또한, 질의 벡터와 MBR까지의 거리가 MBR 내부의 모든 벡터와의 거리 보다 항상 작거나 같다는 관계를 유지하기 위하여, MBR 확장 기법을 제안한다. 끝으로, 다양한 실험에 의한 성능 평가를 통하여 제안하는 방법의 우수성을 규명한다. 실험은 다양한 차원의 합성 데이터와 실제 데이터인 Corel 영상 데이터를 사용하여 진행하였다. 유클리드 거리에 대한 근사 함수에 대한 실험 결과, 제안하는 기법이 Cauchy-Schwartz 부등식을 이용한 기존의 방법에 비하여 최대 6.5배까지 성능이 향상됨을 확인하였다. 또한, 제안하는 차원 축소 기법과 R*-tree 색인을 이용한 검색 실험 결과, 제안하는 기법이 기존의 기법에 비하여 최대 8배까지 성능이 향상됨을 확인하였다.; In multimedia information retrieval, multimedia data are represented as vectors in high-dimensional space. The Euclidean distance is widely used as the measure for evaluating the similarity between two vectors. However, the complexity of computing the Euclidean distance in high-dimensional space is very high. To reduce similarity computation and improve query processing, this dissertation proposes the function that approximates the Euclidean distance based on the norm and angle components of a vector. To this, the proposed method introduces an additional vector called a reference vector for estimating the angle between the two vectors, and approximates the Euclidean distance accurately by using the estimated angle. This makes the approximation errors reduced significantly compared with the previous method using the Cauchy-Schwartz inequality. Also, it is formally proved that the value approximated by the proposed method is always smaller than the actual Euclidean distance. This means that multimedia information retrieval using the proposed approximation function does not incur any false dismissals. To search high-dimensional vectors effectively, a variety of indexing methods have been proposed. However, the performance of these indexing methods degrades dramatically with increasing dimensionality, which is known as the dimensionality curse. To resolve the dimensionality curse, dimensionality reduction methods have been proposed. They map feature vectors in high-dimensional space into vectors in low-dimensional space before the data are indexed. In this dissertation, a novel method for dimensionality reduction is proposed. The proposed dimensionality reduction is based on a function that approximates the Euclidean distance. Firstly, the causes of errors in angle approximation during the approximation of the Euclidean distance is identified and basic solutions to reduce that errors are discussed. Then a new method for dimensionality reduction is proposed. The proposed dimensionality reduction method extracts a set of subvectors from a feature vector and maintains only the norm and the estimated angle for every subvector. The selection of a good reference vector is important for accurate estimation of the angle component. Thus, in this dissertation, criteria for being a good reference vector are presented, and a method that chooses a good reference vector by using the Levenberg-Marquardt algorithm is proposed. Also, a novel distance function is defined and formally proved that the distance function consistently lower-bounds the Euclidean distance. This implies that the proposed approach does not incur any false dismissals in reducing the dimensionality. To index multidimensional data vectors, R*-tree indexing structure are widely used. However, there are some constraints for efficient and correct retrieval using the R*-tree. Because R*-tree is based on minimum bounding rectangle, query range should be represented as a form of MBR for efficient retrieval. Additionally, distance between query vector and MBR must be less than or equal to distance between query vector and data vector within corresponding MBR in the indexed space. To satisfy these constraints, new range including all query range given by user is defined. Also, to preserve the relationship of distance, MBR extension method is proposed in the dissertation. Finally, the superiority of the proposed methods was verified via extensive experiments with synthetic and real-life Corel data sets. Experiments for functions approximating the Euclidean distance showed that the proposed method outperforms the method using the Cauchy-Schwartz inequality by up to 6.5 times in terms of candidates. Experimental results for retrieval using the proposed dimensionality reduction and R*-tree index showed that the proposed methods outperforms the previous methods by up to 8 times.