Recent studies show that binary codes are a powerful means to perform large-scale image searching and feature matching. Binary codes require significantly less storage space while enabling efficient computation in the Hamming space. At the core of the algorithms that utilize binary codes is the nearest neighbor problem. Although the distance in the Hamming space can be computed efficiently, a linear search against a large-scale dataset creates a bottleneck. Some approximate nearest neighbor (ANN) search algorithms have been proposed to overcome this limitation; the hierarchical clustering tree (HCT) was proved to outperform the well-known locality sensitive hashing. HCT recursively clusters the input binary codes by assigning each binary code to only one cluster, which leads to a quantization error. As a solution to this problem, in this thesis, we propose two algorithms to create hierarchical soft clustering tree (HSCT) by assigning a data point to multiple nearby clusters in the Hamming space. One is a fuzzy hierarchical soft clustering tree (FHSCT) which soft assigns a data point to multiple nearby clusters based on fuzzy membership weight without considering an expected query point. To increase search precision, the other algorithm, query-aware hierarchical soft clustering tree (QAHSCT) is proposed. QAHSCT assigns a binary code to a cluster based on the probability that the query point nearest to the binary code is assigned to the cluster. Because query points are not available when building trees, the exact distance between a query point and cluster center cannot be obtained. Therefore, distance distribution is used instead, which is approximated using Poisson binomial distribution. Experiments show that our proposed methods outperform the previous ANN search methods in terms of search speed without sacrificing search precision.
이미지 검색과 특징값 매칭 등에 관한 최신 연구에서 이진 코드의 중요성이 부각되고 있다. 이진 코드는 실수값 데이터에 비하여 저장 공간 소모가 현저히 적으면서, 해밍 공간에서 고속의 거리 계산이 가능한 장점이 있다. 이진 코드를 활용하는 알고리즘은 크게 이진 코드 생성과 최근접 이웃 탐색으로 구성되며, 최근접 이웃 탐색 방법으로는 주로 선형 탐색이 사용되었다. 하지만, 검 색 대상이 되는 데이터가 아주 많을 경우에는 선형 탐색으로 만족할 만한 처리 속도를 얻을 수 없는 문제가 있다. 이러한 문제를 해결하기 위하여 근사 최근접 이웃 탐색 방법들이 제안되었고, 계층적 군집 트리가 가장 좋은 성능을 내는 것으로 알려져 있다. 계층적 군집 트리는 이진 코드를 한 개의 군집에만 할당을 하기 때문에 양자화 오류가 발생하게 되고, 질의 이진 코드와 여러 군집 센터로의 거리가 유사할 경우에는 검색 성능이 매우 낮아지게 된다. 이를 해결하기 위하여 본 논문에서는 하나의 이진 코드를 복수개의 군집에 할당하면서 계층적 군집 트리를 생성하는 두 가지 방법을 제안한다. 첫 번째는 퍼지 군집화 이론에 기반한 계층적 중복 군집 트리로써 기존의 계층적 군집 트리보다 빠른 검색 성능을 보인다. 하지만, 질의 이진 코드에 대한 고려 없이 검색 대상이 되는 이진 코드 간의 거리만을 이용하여 군집화를 하는 단점이 있고, 이를 개선하기 위하여 질의 인지형 계층적 중복 군집 트리 생성 방법을 제안한다. 질의 이진 코드가 특정 군집에 할당될 확률을 포아송 이항 분포를 이용하여 근사화하여 구하고, 이 확률에 기반하여 중복적으로 데이터를 할당할 군집들을 결정하게 된다. 이진 코드의 근사 최근접 이웃 탐색을 위한 기존의 방법들과 비교 실험에서 제안 방법이 검색 정확도는 유지하면서 더 빠른 검색 속도를 보장하는 것을 확인하였다.
