KR100429792B1 - 특징 벡터 공간의 인덱싱 방법 및 검색 방법 - Google Patents

Abstract

고차원 특징 벡터 공간을 인덱싱하는 방법이 개시된다. 또한, 상기 인덱싱 방법에 의하여 인덱싱된 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 빠르게 검색하는 방법이 개시된다. 본 발명에 따른 특징 벡터 공간의 인덱싱 방법은 (a) 특징 벡터 공간을 복수 개의 근사 영역들로 분할하는 단계와, (b) 임의의 근사 영역을 선택하여 선택된 근사 영역이 희박한지 조밀한지를 식별하는 단계, 및 (c) 상기 (b) 단계에서 근사 영역이 희박한 근사 영역으로 식별되면 해당 근사 영역은 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계를 포함하는 것을 특징으로 한다. 본 발명에 따른 특징 벡터 공간의 인덱싱 방법에 따라 인덱싱된 고차원의 특징 벡터 데이터 공간에서는 유사도 검색, 불러들임 및 브라우징과 같은 기능들을 스케일적이고 효율적으로 지원된다. 이로써, 데이터베이스의 크기가 증가되어도 유사도 검색 및 블러들임을 하는데 요구되는 시간이 그다지 증가되지 않는다.

Description

특징 벡터 공간의 인덱싱 방법 및 검색 방법{Indexing method of feature vector space and retrieval method}

본 발명은 특징 벡터 공간의 인덱싱 방법에 관한 것으로, 특히 고차원 특징 벡터 공간을 인덱싱하는 방법에 관한 것이다. 또한, 본 발명은 상기 인덱싱 방법에 의하여 인덱싱된 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를빠르게 검색하는 방법에 관한 것이다.

영상 또는 동영상의 색 특징 또는 텍스쳐 특징과 같은 특징 성분들(feature elements)은 벡터들로써 표현될 수 있다. 이러한 벡터들은 특징 벡터들이라 칭하여진다. 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 검색할 수 있도록 특징 벡터들이 속하는 벡터 공간내에서 상기 특징 벡터들을 인덱싱한다.

종래의 특징 벡터 공간의 인덱싱 방법에 따르면, 저차원 특징 벡터 공간을 인덱싱하는데는 R 트리 또는 X 트리라고 불리우는 트리 구조의 데이터 분할(data partitioning) 방법 또는 공간 분할 방법이 사용된다. 또한, 종래의 특징 벡터 공간의 인덱싱 방법에 따르면, 고차원 특징 벡터 공간을 인덱싱하는데는 특징 벡터 공간내에서 유사한 특징을 가지는 벡터들을 동일한 하이퍼 큐브(hyper cube)내에 속하는 것으로 결정함으로써 인덱싱하는 벡터 근사화(Vector Approximation: VA)가 사용된다.

하지만, 고차원 특징 벡터 공간의 경우에는 상기 특징 벡터 공간내에 속하는 특징 벡터들을 상기와 같은 벡터 근사화를 기초로 하는 종래의 인덱싱 방법을 사용하여 인덱싱하면 쿼리 벡터와 유사한 특징 벡터를 검색할 때 시간이 많이 소요되는 경우가 있다. 즉, 검색하는데 필요한 시간을 줄일 수 있는 인덱싱 방법에 대한 욕구가 여전히 존재한다.

본 발명이 이루고자 하는 기술적 과제는 특징 벡터 공간내에 존재하는 특징 벡터들의 밀도에 따라 적응적으로 인덱싱함으로써 쿼리 벡터와 유사한 특징 벡터를검색할 때 필요한 시간을 줄일 수 있는 특징 벡터 공간의 인덱싱 방법을 제공하는 것이다.

본 발명이 이루고자 하는 또 다른 기술적 과제는 상기 특징 벡터 공간의 인덱싱 방법에 의하여 인덱싱된 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 빠르게 검색하는 방법을 제공하는 것이다.

도 1은 본 발명의 실시예에 따른 특징 벡터 공간의 인덱싱 방법의 주요 단계들을 나타낸 흐름도이다.

도 2는 도 1의 방법에 따라 인덱싱되는 특징 벡터 공간의 일예를 나타낸 도면이다.

도 3는 도 2의 특징 벡터 공간을 인덱스한 트리 구조의 일예를 나타낸 도면이다.

도 4는 도 1의 특징 벡터 공간의 인덱싱 방법에 의하여 인덱싱된 특징 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 검색하는 본 발명에 따른 검색 방법의 주요 단계들을 나타낸 흐름도이다.

상기 과제를 이루기 위하여 본 발명의 일측면에 따른 특징 벡터 공간의 인덱싱 방법은 트리 구조를 사용하여 특징 벡터 공간을 인덱싱하는 방법에 있어서, 특징 벡터 엘리먼트의 분포가 희박한 근사 영역을 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계;를 포함하는 것을 특징으로 한다.

또한, 상기 과제를 이루기 위하여 본 발명의 다른 측면에 따른 특징 벡터 공간의 인덱싱 방법은 (a) 특징 벡터 공간을 복수 개의 근사 영역들로 분할하는 단계; (b) 임의의 근사 영역을 선택하여 선택된 근사 영역이 희박한지 조밀한지를 식별하는 단계; 및 (c) 상기 (b) 단계에서 근사 영역이 희박한 근사 영역으로 식별되면 해당 근사 영역은 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계;를 포함하는 것을 특징으로 한다.

또한, 상기 (b) 단계 및 (c) 단계는, 상기 (a) 단계에서 분할된 모든 근사 영역들에 대하여 반복되는 것이 바람직하다.

또한, 상기 (c) 단계 이전에, (c-1) 상기 (b) 단계에서 선택된 근사 영역이 조밀한 근사 영역인 것으로 식별되면 해당 근사 영역을 비특이 노드로써 인덱스하고, 해당 근사 영역을 복수 개의 서브 근사 영역들로 분할하여, 분할된 서브 근사 영역들에 대하여 상기 (b) 단계를 반복하는 단계;를 더 포함하는 것이 바람직하다.

또한, 상기 특징 벡터 공간의 인덱싱 방법은 상기 (c) 단계 이후에, (d) 모든 하이퍼 큐브들이 특이 노드로써 인덱스되었는지를 식별하는 단계; (e) 모든 하이퍼 큐브들이 특이 노드로써 인덱스되지 않은 것으로 식별되면 다음 하이퍼 큐브를 선택하여 상기 단계(b) 이후의 단계들을 반복적으로 수행하는 단계; 및 (f) 모든 하이퍼 큐브들이 특이 노드로써 인덱스된 것으로 식별되면 인덱싱을 종료하는 단계;를 더 포함하는 것이 바람직하다.

또한, 상기 복수 개의 근사 영역들은 임의의 인덱싱 방법에서 사용되는 서브 공간들일 수 있다.

대안적으로, 상기 복수 개의 근사 영역들은 MDS(multi-dimensional scaling), 패스트맵(Fast-map), 또는 국부 감지 해싱(locality sensitive hashing)중에서 선택된 하나의 인덱싱 방법에서 사용되는 서브 공간들이어도 무방하다.

또한, 상기 (c) 단계는, (c') 상기 (b) 단계에서 근사 영역이 희박한 근사 영역으로 식별되면 해당 근사 영역은 상기 해당 근사 영역과 인접한 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계;인 것도 가능하다.

또한, 상기 다른 과제를 이루기 위하여 본 발명에 따른 특징 벡터 공간내에서의 검색 방법은 트리 구조를 사용하여 특징 벡터 엘리먼트가 희박한 근사 영역을 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계를 포함하는 인덱싱 방법에 의하여 인덱싱된 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 검색하는 방법에 있어서, (a) 쿼리 벡터가 속하는 특이 노드를 결정하는 단계; (b) 결정된 특이 노드에 해당하는 하이퍼 큐브내에서 쿼리 벡터의 엘리먼트와 가장 가까운 엘리먼트 사이의 거리를 제1 임계값으로 설정하는 단계; 및 (c) 특징 벡터와 비특이 노드로 인덱스된 하이퍼 큐브 사이의 거리가 소정의 제1 임계값보다 크거나 같으면 해당 노드의 모든 자식 노드들을 제외하는 단계;를 포함하는 것을 특징으로 한다.

이하 첨부된 도면들을 참조하여 본 발명의 바람직한 실시예들을 상세히 설명하기로 한다.

도 1에는 본 발명의 실시예에 따른 특징 벡터 공간의 인덱싱 방법의 주요 단계들을 흐름도로써 나타내었다. 도 1을 참조하여 본 발명의 실시예에 따른 특징 벡터 공간의 인덱싱 방법을 설명하면, 먼저, 특징 벡터 공간을 복수 개의 하이퍼 큐브들로 분할한다(단계 102). 본 실시예에서는 특징 벡터 공간이 복수 개의 하이퍼 큐브들로 분할되는 것을 예로써 설명하지만, 특징 벡터 공간은 임의의 인덱싱 방법, 또는 MDS(multi-dimensional scaling), 패스트맵(Fast-map), 및 국부 감지 해싱(locality sensitive hashing)과 같은 보다 향상된 인덱싱 방법에서 사용되는 서브 공간들로 분할되는 것도 가능하다. 도 2에는 도 1의 방법에 따라 인덱싱되는특징 벡터 공간의 일예를 나타내었다. 한편, n은 소정의 양의 정수라 할 때, 상기 특징 벡터 공간내의 특징 벡터들은 n 차원 벡터에 의하여 표현될 수 있다. 다시 말하면, N은 양의 정수라 할 때 N 개의 특징 벡터들을 포함하는 데이터베이스를 D라 할 때, 이러한 특징 벡터들은 벡터 공간내의 n 차원 벡터로써 표현될 수 있다.

다음으로, 분할된 하이퍼 큐브들을 트리 구조를 사용하여 루트 노드의 자식 노드들로써 인덱스한다(단계 104). 트리는 기본적으로 루트 노드를 가지고, 루트 노드에 속하는 복수 개의 자식 노드들이 트리 형태로 분류된다. 도 3에는 도 2의 특징 벡터 공간을 인덱스한 트리 구조의 일예를 나타내었다.

이제, 루트 노드(302)의 자식 노드에 속하는 임의의 하나의 하이퍼 큐브를 선택하여 조밀한 큐브인지 희박한 큐브인지를 식별(단계 106)한다. 여기서, 루트 노드(302)는 초기 하이퍼 큐브에 해당하며, 상기 루트 노드의 자식 노드들은의 서브 큐브들에 해당한다. 루트 노드는 트리의 레벨 0에 해당한다고 칭할 수 있다. 또한, 루트 노드의 자식 노드들은 레벨 1에 해당한다고 칭할 수 있고, 상기 루트 노드의 자식 노드의 자식 노드는 레벨 2에 해당한다고 칭할 수 있다.

만일, 단계(106)에서 선택된 하이퍼 큐브가 조밀한 큐브인 것으로 식별되면 해당 큐브를 비특이 노드로써 인덱스(단계 108)하고, 해당 큐브를 복수 개의 하이퍼 큐브들로 분할한다(단계 110). 반면에, 단계(106)에서 선택된 하이퍼 큐브가 희박한 큐브인 것으로 식별되면 해당 큐브를 인접하는 희박한 큐브와 함께 하나의 특이 노드로써 인덱스한다(단계 120). 본 실시예에서는 선택된 하이퍼 큐브가 희박한큐브인 것으로 식별되면 단계(120)에서 해당 큐브를 인접하는 희박한 큐브와 함께 하나의 특이 노드로써 인덱스하는 것을 예로써 설명하지만 선택된 하이퍼 큐브가 희박한 큐브인 것으로 식별되면 해당 큐브를 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 큐브와 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 것도 가능하다.

다음으로, 해당 큐브가 복수 개의 하이퍼 큐브들로 분할된 경우에는 분할된 개별 하이퍼 큐브들에 대하여 상기 단계(106) 이후의 단계들이 반복적으로 수행된다.

본 실시예에서는, 도 2를 참조하면, 희박한 큐브로 식별된 하이퍼 큐브(202)와 하이퍼 큐브(204)는 하나의 특이 노드(304)로써 인덱스된다. 반면에, 조밀한 큐브로 식별된 하이퍼 큐브(206)와 하이퍼 큐브(208)은 각각 비특이 노드(306)과 비특이 노드(308)로 인덱스된다. 또한, 조밀한 큐브로 식별된 하이퍼 큐브(206)는 다시 복수 개의 서브 하이퍼 큐브들(206₁, 206₂, 206₃, 206₄)로 분할된다. 분할된 복수 개의 서브 하이퍼 큐브들(206₁, 206₂, 206₃, 206₄)에 대하여 조밀한 큐브인지 희박한 큐브인지를 식별하여, 예를들어, 조밀한 큐브로써 식별된 큐브(206₄)는 비특이 노드(310)로써 인덱스된다. 반면에, 희박한 큐브들로써 식별된 큐브들(206₁, 206₂, 206₃)은 하나의 특이 노드(312)로써 인덱스된다. 조밀한 큐브로 식별된 하이퍼 큐브(206₄)는 다시 복수 개의 서브 하이퍼 큐브들(206_{4_1}, 206_{4_2}, 206_{4_3}, 206_{4_4})로분할된다. 다음으로, 분할된 복수 개의 서브 하이퍼 큐브들(206_{4_1}, 206_{4_2}, 206_{4_3}, 206_{4_4})에 대하여 조밀한 큐브인지 희박한 큐브인지를 식별하여, 조밀한 큐브로써 식별된 큐브(206_{4_1})는 비특이 노드로써 인덱스하고, 다시 분할한 결과로써는 모든 분할된 큐브들이 희박한 큐브들로써 식별되어 하나의 특이 노드(314)로써 인덱스된다. 반면에, 희박한 큐브로써 식별된 큐브들(206_{4_1}, 206_{4_2}, 206_{4_3})은 하나의 특이 노드(316)로써 인덱스된다.

이제, 모든 하이퍼 큐브들이 특이 노드로써 인덱스되었는지를 식별(단계 130)하여 모든 하이퍼 큐브들이 특이 노드로써 인덱스되지 않은 것으로 식별되면 다음 하이퍼 큐브를 선택(단계 132)하여 단계(106) 이후의 단계들을 반복적으로 수행한다. 반면에, 단계(130)에서 모든 하이퍼 큐브들이 특이 노드로써 인덱스된 것으로 식별되면 인덱싱이 종료된다.

즉, 다시 도 2를 참조하면, 조밀한 큐브로 식별된 하이퍼 큐브(208)는 다시 복수 개의 서브 하이퍼 큐브들(208₁, 208₂, 208₃, 208₄)로 분할된다. 다음으로, 분할된 복수 개의 서브 하이퍼 큐브들(208₁, 208₂, 208₃, 208₄)에 대하여 조밀한 큐브인지 희박한 큐브인지를 식별하여, 조밀한 큐브로써 식별된 큐브(208₁)는 비특이 노드로써 인덱스되지만, 상기 큐브(208₁)를 다시 분할한 결과로써는 모든 분할된 큐브들이 희박한 큐브들로써 식별되어 하나의 특이 노드(318)로써 인덱스된다. 반면에, 희박한 큐브로써 식별된 큐브들(208₂, 208₃, 208₄)는 하나의 특이 노드(320)로써 인덱스된다.

이하에서는, 상기와 같은 특징 벡터 공간의 인덱싱 방법에 의하여 인덱싱된 특징 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 검색하는 방법을 설명한다. 도 4에는 도 1의 특징 벡터 공간의 인덱싱 방법에 의하여 인덱싱된 특징 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 검색하는 본 발명에 따른 검색 방법의 주요 단계들을 흐름도로써 나타내었다. 이하에서는 데이터베이스에 해당하는 특징 벡터 공간내의 쿼리 벡터를 q로 나타내고, n은 특징 벡터를 기술하기 위한 특징 벡터 공간의 차원 수를 나타내는 양의 정수라 할 때, 상기 쿼리 벡터 q는으로 정의되는 특징 공간내에 놓인다고 가정한다. 다음으로, 데이터베이스 D로부터 q에 가장 가까운 엘리먼트, 즉, 특징 벡터를 찾기 위하여 다음의 단계들을 수행한다.

먼저, 쿼리 벡터가 속하는 특이 노드를 결정한다(단계 402). 다음으로, 결정된 특이 노드에 해당하는 하이퍼 큐브내에서 쿼리 벡터의 엘리먼트와 가장 가까운 엘리먼트 사이의 거리를 e로 설정한다(단계 404).

루트 노드의 자식 노드들 중에서 임의의 노드를 선택하여 선택된 노드가 특이 노드인지 비특이 노드인지를 식별(단계 410)한다. 다시 말하면, 쿼리 벡터 q가 인덱스 트리의 어떤 한 노드에 해당하는 하이퍼 큐브에 놓인다고 가정하고, q가 조밀한 노드에 놓이는지 희박한 노드에 놓이는지를 결정한다. 만일, 단계(410)에서 선택된 노드가 비특이 노드인 것으로 식별되면 특징 벡터 q와 비특이 노드로인덱스된 하이퍼 큐브사이의 거리을,

에 따라 계산한다(단계 412). 여기서, 특징 벡터 공간내의 임의의 구간는 쌍로 나타낼 수 있으며, 특징 벡터 공간내의 하이퍼 큐브는 구간의 시퀀스로써 나타낼 수 있다.

다음으로,이 e보다 작은지를 식별(단계 414)하여,이 e보다 작은 것으로 식별되면 해당 노드의 자식 노드를 선택(단계 416)한다. 이때,의 조건을 만족하는 엘리먼트가 존재하는 경우에는를로 업데이트하는 것이 보다 바람직하다. 이는 인덱스 및 검색 구조를 쿼리 벡터와 가장 유사한 특징을 가지는 하나의 엘리먼트만을 빠르게 찾는 것으로 설계하고자 하는 경우에 특히 바람직하다.

반면에,이 e보다 크거나 같은 것으로 식별되면 해당 노드의 모든 자식 노드들을 제외한다(단계 418).

또한, 단계(410)에서 선택된 노드가 특이 노드인 것으로 식별되면, 그 노드에 해당하는 하이퍼 큐브 공간을 저차원 공간으로 변환(단계 420)한다. 즉, 단계(410)에서 q가 희박한 노드에 놓이는 것으로 결정되면, 상기 쿼리 벡터를 그 쿼리 벡터에 해당하는 저차원 서브 공간상에 투영한다.

다음으로, 특징 벡터 q와 특이 노드로 인덱스된 하이퍼 큐브내의 모든엘리먼트사이의 거리을,

에 따라 계산한다(단계 422). 다음으로,의 조건을 만족하는 엘리먼트들을 후보 엘리먼트들로써 결정한다(단계 424). 이때, 도 4에는 도시하지 않았으나의 조건을 만족하는 엘리먼트가 존재하는 경우에는를로 업데이트하는 것이 보다 바람직하다. 이는 인덱스 및 검색 구조를 쿼리 벡터와 가장 유사한 특징을 가지는 하나의 엘리먼트만을 빠르게 찾는 것으로 설계하고자 하는 경우에 특히 바람직하다.

이제, 모든 특이 노드들에 대하여 검색되었는지를 식별(단계 430)하여 검색되지 않은 특이 노드가 남아 있는 것으로 식별되면 다음 노드를 선택(단계 432)하여, 단계(410) 이후의 과정들을 반복적으로 수행한다. 반면에, 모든 특이 노드들에 대하여 검색된 것으로 식별되면 소정 개수의 엘리먼트를 최종 검색된 엘리먼트로써 결정한다(단계 440).

상기와 같은 검색 방법에 따르면, 쿼리 벡터와 엘리먼트 사이의 거리가 상기 쿼리 벡터가 속하는 특이 노드에 해당하는 하이퍼 큐브내에서 쿼리 벡터와 가장 가까운 거리로 결정되는 소정의 임계값 e보다 크거나 같은 것으로 식별되면 해당 노드의 모든 자식 노드들을 유사도 검색에서 제외하고, 제외되는 모든 자식 노드들에 속한 노드들에 해당하는 하이퍼 큐브들은 더 이상 쿼리 벡터에 대한 유사도측정에 적용되지 않는다. 더욱이, 유사도 측정에 사용되는 소정의 임계값을 반복적으로 업데이트함으로써 보다 빠른 불러들임(retrieval)이 가능하다.

즉, 본 발명에 따른 특징 벡터 공간의 인덱싱 방법에 따라 인덱싱된 고차원의 특징 벡터 데이터 공간에서는 유사도 검색, 불러들임 및 브라우징과 같은 기능들을 스케일적이고 효율적으로 지원된다. 이로써, 데이터베이스의 크기가 증가되어도 유사도 검색 및 블러들임을 하는데 요구되는 시간이 그다지 증가되지 않는다.

또한, 상기와 같은 본 발명에 따른 특징 벡터 공간의 인덱싱 방법 및 검색 방법은 개인용 또는 서버급의 컴퓨터내에서 실행되는 프로그램으로 작성 가능하다. 상기 프로그램을 구성하는 프로그램 코드들 및 코드 세그멘트들은 당해 분야의 컴퓨터 프로그래머들에 의하여 용이하게 추론될 수 있다. 또한, 상기 프로그램은 컴퓨터 독취 가능 기록 매체에 저장될 수 있다. 상기 기록 매체는 자기기록매체, 광기록 매체, 및 전파 매체를 포함한다.

상술한 바와 같이 본 발명에 따른 특징 벡터 공간의 인덱싱 방법에 따라 인덱싱된 고차원의 특징 벡터 데이터 공간에서는 유사도 검색, 불러들임 및 브라우징과 같은 기능들을 스케일적이고 효율적으로 지원된다. 이로써, 데이터베이스의 크기가 증가되어도 유사도 검색 및 블러들임을 하는데 요구되는 시간이 그다지 증가되지 않는다.

Claims (17)

1. 트리 구조를 사용하여 특징 벡터 공간을 인덱싱하는 방법에 있어서,

   (a) 특징 벡터 공간을 복수 개의 근사 영역으로 분할하는 단계;

   (b) 특징 벡터 엘리먼트의 분포가 조밀한 근사 영역을 비특이 노드로써 인덱스하는 단계; 및

   (c) 특징 벡터 엘리먼트의 분포가 희박한 근사 영역을 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계;를 포함하는 것을 특징으로 하는 특징 벡터 공간의 인덱싱 방법.
2. (a) 특징 벡터 공간을 복수 개의 근사 영역들로 분할하는 단계;

   (b) 임의의 근사 영역을 선택하여 선택된 근사 영역이 희박한지 조밀한지를 식별하는 단계;

   (c-1) 상기 (b) 단계에서 선택된 근사 영역이 조밀한 근사 영역인 것으로 식별되면 해당 근사 영역을 비특이 노드로써 인덱스하고, 해당 근사 영역을 복수 개의 서브 근사 영역들로 분할하여, 분할된 서브 근사 영역들에 대하여 상기 (b) 단계를 반복하는 단계; 및

   (c) 상기 (b) 단계에서 근사 영역이 희박한 근사 영역으로 식별되면 해당 근사 영역은 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계;를 포함하는 것을 특징으로 하는 특징 벡터 공간의 인덱싱 방법.
3. 제2항에 있어서, 상기 (b) 단계 및 (c) 단계는,

   상기 (a) 단계에서 분할된 모든 근사 영역들에 대하여 반복되는 것을 특징으로 하는 특징 벡터 공간의 인덱싱 방법.
4. 삭제
5. 제4항에 있어서, 상기 (b) 단계 및 (c) 단계는,

   상기 (a) 단계에서 분할된 모든 근사 영역들에 대하여 반복되는 것을 특징으로 하는 특징 벡터 공간의 인덱싱 방법.
6. 제2항 또는 제3항중 어느 한 항에 있어서, 상기 (c) 단계 이후에,

   (d) 모든 하이퍼 큐브들이 특이 노드로써 인덱스되었는지를 식별하는 단계;

   (e) 모든 하이퍼 큐브들이 특이 노드로써 인덱스되지 않은 것으로 식별되면 다음 하이퍼 큐브를 선택하여 상기 단계(b) 이후의 단계들을 반복적으로 수행하는 단계; 및

   (f) 모든 하이퍼 큐브들이 특이 노드로써 인덱스된 것으로 식별되면 인덱싱을 종료하는 단계;를 더 포함하는 것을 특징으로 하는 특징 벡터 공간의 인덱싱 방법.
7. 제2항에 있어서, 상기 복수 개의 근사 영역들은,

   임의의 인덱싱 방법에서 사용되는 서브 공간들인 것을 특징으로 하는 특징벡터 공간의 인덱싱 방법.
8. 제2항에 있어서, 상기 복수 개의 근사 영역들은,

   MDS(multi-dimensional scaling), 패스트맵(Fast-map), 또는 국부 감지 해싱(locality sensitive hashing)중에서 선택된 하나의 인덱싱 방법에서 사용되는 서브 공간들인 것을 특징으로 하는 특징 벡터 공간의 인덱싱 방법.
9. 제2항에 있어서, 상기 (c) 단계는,

   (c') 상기 (b) 단계에서 근사 영역이 희박한 근사 영역으로 식별되면 해당 근사 영역은 상기 해당 근사 영역과 인접한 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계;인 것을 특징으로 하는 특징 벡터 공간의 인덱싱 방법.
10. 트리 구조를 사용하여 특징 벡터 엘리먼트가 희박한 근사 영역을 그 영역과 소정의 거리보다 적은 거리 만큼 이격된 다른 희박한 근사 영역과 함께 트리 구조의 자식 노드에 속하는 하나의 특이 노드로써 인덱스하는 단계를 포함하는 인덱싱 방법에 의하여 인덱싱된 벡터 공간내에서 쿼리 벡터와 유사한 특징을 가지는 특징 벡터를 검색하는 방법에 있어서,

    (a) 쿼리 벡터가 속하는 특이 노드를 결정하는 단계;

    (b) 결정된 특이 노드에 해당하는 하이퍼 큐브내에서 쿼리 벡터의 엘리먼트와 가장 가까운 엘리먼트 사이의 거리를 제1 임계값으로 설정하는 단계; 및

    (c) 특징 벡터와 비특이 노드로 인덱스된 하이퍼 큐브 사이의 거리가 소정의 제1 임계값보다 크거나 같으면 해당 노드의 모든 자식 노드들을 제외하는 단계;를 포함하는 것을 특징으로 하는 특징 벡터 공간내에서의 검색 방법.
11. 제10항에 있어서, 상기 (c) 단계 이전에,

    (c') 루트 노드의 자식 노드들 중에서 임의의 노드를 선택하여 선택된 노드가 특이 노드인지 비특이 노드인지를 식별하는 단계;를 더 포함하는 단계를 더 포함하는 것을 특징으로 하는 특징 벡터 공간내에서의 검색 방법.
12. 제11항에 있어서, 상기 (c) 단계는,

    (c-1) 상기 (c') 단계에서 선택된 노드가 비특이 노드인 것으로 식별되면 특징 벡터 q와 비특이 노드로 인덱스된 하이퍼 큐브사이의 거리를,

    에 따라 계산하는 단계;

    (c-2) 특징 벡터 q와 비특이 노드로 인덱스된 하이퍼 큐브사이의 거리가 e보다 작은지를 식별하는 단계;

    (c-3) 특징 벡터 q와 비특이 노드로 인덱스된 하이퍼 큐브사이의 거리가 e보다 작은 것으로 식별되면 해당 노드의 자식 노드를 선택하는 단계; 및

    (c-4) 특징 벡터 q와 비특이 노드로 인덱스된 하이퍼 큐브사이의 거리가 e보다 크거나 같은 것으로 식별되면 해당 노드의 모든 자식 노드들을 제외하는 단계;를 포함하는 것을 특징으로 하는 특징 벡터 공간내에서의 검색 방법.
13. 제12항에 있어서, 상기 (c-2) 단계 이후에,

    이 e보다 작은 것으로 식별되면를로 업데이트하는 단계;를 더 포함하는 것을 특징으로 하는 특징 벡터 공간내에서의 검색 방법.
14. 제11항에 있어서, 상기 (c') 단계 이후에,

    상기 (c') 단계에서 선택된 노드가 특이 노드인 것으로 식별되면, 그 노드에 해당하는 하이퍼 큐브 공간을 저차원 공간으로 변환하는 단계;를 더 포함하는 것을 특징으로 하는 특징 벡터 공간에서의 검색 방법.
15. 제12항에 있어서, 상기 (c') 단계 이후에,

    (c-5) 상기 (c') 단계에서 선택된 노드가 특이 노드인 것으로 식별되면, 그 노드에 해당하는 하이퍼 큐브 공간을 저차원 공간으로 변환하는 단계;

    (c-6) 특징 벡터 q와 특이 노드로 인덱스된 하이퍼 큐브내의 모든 엘리먼트사이의 거리을에 따라 계산하는 단계;

    (c-7)의 조건을 만족하는 엘리먼트들을 후보 엘리먼트들로써 결정하는 단계;를 더 포함하는 것을 특징으로 하는 특징 벡터 공간에서의 검색 방법.
16. 제15항에 있어서, 상기 (c-7) 단계 이후에,

    (c-8)의 조건을 만족하는 엘리먼트가 존재하는 경우에는를로 업데이트하는 단계;를 더 포함하는 것을 특징으로 하는 특징 벡터 공간에서의 검색 방법.
17. 제12항 또는 제15항 중 어느 한 항에 있어서, 상기 (c-4) 단계 이후에,

    모든 특이 노드들에 대하여 검색되었는지를 식별하는 단계;

    검색되지 않은 특이 노드가 남아 있는 것으로 식별되면 다음 노드를 선택하여 상기 (c-1) 단계 이후의 과정들을 반복적으로 수행하는 단계;

    모든 특이 노드들에 대하여 검색된 것으로 식별되면 소정 개수의 엘리먼트를 최종 검색된 엘리먼트로써 결정하는 단계;를 더 포함하는 것을 특징으로 하는 특징 벡터 공간에서의 검색 방법.