KR101153966B1

KR101153966B1 - 고차원 데이터의 색인/검색 시스템 및 그 방법

Info

Publication number: KR101153966B1
Application number: KR1020080131384A
Authority: KR
Inventors: 이훈순; 이미영; 엄정호; 장재우
Original assignee: 전북대학교산학협력단; 한국전자통신연구원
Priority date: 2008-12-22
Filing date: 2008-12-22
Publication date: 2012-06-08
Also published as: KR20100072855A

Abstract

본 발명은 고차원 데이터의 색인/검색하는 시스템 및 그 방법에 관한 것이다. 고차원 데이터의 검색 시스템 및 그 방법에서는 고차원 데이터를 구간으로 나누어 클러스터링한 후, 각 구간에 시그니처를 부여하고, 고차원 데이터의 삽입시 데이터를 인접 셀에도 중복 삽입함으로써, 사용자에게 높은 정확도를 보장하는 검색 성능이 제공된다.

Description

고차원 데이터의 색인/검색 시스템 및 그 방법{SYSTEM AND METHOD OF INDEXING/RETRIEVAL OF HIGH-DIMENSIONAL DATA}

본 발명은 고차원 데이터를 색인/검색하는 시스템 및 그 방법에 관한 것으로서, 특히 유사 동영상 검색을 위하여 동영상으로부터 추출된 고차원 데이터를 색인 및 검색하는 검색 시스템 및 그 방법에 관한 것이다.

본 발명은 지식경제부 및 정보통신연구진흥원 IT신성장동력핵심기술개발사업의 일환으로 수행한 연구로부터 도출된 것이다.[국가관리번호: 2007-S-016-02 국가연구과제명: 저비용 대규모 글로벌 인터넷 서비스 솔루션 개발]

현재 UCC 등의 동영상 사이트가 증가하고 있다. 동영상의 수가 증가함에 따라, 사용자가 보유한 이미지나 동영상에 근거하여 동영상을 검색하는 문제가 대두되고 있다. 이를 해결하기 위하여, 최근에는 동영상을 고차원 특징 데이터로 변환하고, 변환된 고차원 특징 데이터에 대하여 색인을 구축함으로써, 고차원 데이터 간의 유사성을 찾는 기법이 개발된바 있다.

고차원 데이터를 위한 색인은 크게 트리 기반의 색인 기법과 셀 기반의 색인 기법으로 분류된다.

트리 기반 고차원 색인 기법(예컨대, R-Tree, X-Tree, SR-Tree, M-Tree)은 데이터 공간에 흩어져 있는 객체들을 효율적으로 검색하기 위해, 서로 유사한 데이터를 클러스터링한 후 근접한 객체들의 집합을 나타내는 사각형이나 원을 검색 단위로 사용한다. 그러나, 데이터의 차원이 증가할수록 근접한 객체들의 집합을 나타내는 사각형이나 원 사이에 겹침 영역이 확대됨으로써, 검색 성능이 기하급수적으로 떨어진다. 또한 순차 검색보다도 검색 성능이 오히려 떨어지는 현상이 발생하여, 이에 대한 개선이 요구되는 실정이다.

셀 기반의 색인 기법(예컨대, VA-File, CBF 등)은 데이터를 순차적으로 탐색하면서, 불필요한 데이터에 대한 가지치기(pruning)를 수행한다. 데이터를 순차적으로 탐색하므로, 트리 기반 색인과 달리 데이터의 차원이 증가할지라도 검색 성능은 크게 떨어지지 않는다. 하지만 데이터가 증가할수록 순차 탐색에 대한 부하가 증가한다.

따라서, 차원과 데이터의 증가에 따른 문제를 해결하고자 LSH(Locality Sensitive Hashing) 기법이 제안된바 있다. 이 LSH기법은 해쉬 함수를 사용하여 자신과 가까운 객체 또는 벡터 데이터는 동일한 버킷(buket)에 삽입될 확률을 높이고, 자신과 먼 객체일수록 같은 버킷에 삽입될 확률을 낮춤으로써, 탐색 범위를 줄이는 개념이다.

도 1은 기존의 LSH 기법에 따라 고차원 데이터가 버킷에 삽입되는 과정을 보여주는 순서도이다.

도 1을 참조하면, 고차원 데이터가 버킷에 삽입되는 과정이 수행되기에 앞 서, 고차원 데이터가 분할되어, 저장되는 해싱 구조(또는 인덱스)의 개수가 결정되고, 해싱에 필요한 난수가 생성된다. 이후, 고차원 데이터의 값을 기준으로 각 차원 마다 상기 고차원 데이터가 비트열로 변환된다(S11). 비트열의 변환은 제일 큰 수를 기준으로 그 수만큼의 비트가 할당되어, 해당 값에 따라 그 값만큼의 비트가 1로 세팅된다. 이는 데이터 간의 거리를 보존하기 위함이다.

이어, 생성된 해싱 구조(또는 인덱스)의 개수에 따라 비트열이 임의로 분할된다. 생성된 해싱 구조의 개수는 실험을 통하여 높은 정확도를 가지는 수가 선택된다(S12). 이어, 분할한 비트 수(C)만큼 버킷이 생성되고, 해당 비트에 따라 1차 해싱이 수행된다(S13). 이어, 비트별로 상기 생성된 난수(R)와 상기 1차 해싱의 버킷 값(C)을 곱하여 더한 후, 이 결과치와 2차 해싱의 버킷 수(M) 간의 모듈러(modular) 연산을 통해 2차 해싱이 수행된다(S14). 이어, 2차 해싱을 통해 결정된 버킷에 고차원 데이터가 저장되고(S15), 1차 및 2차 해싱의 수행 횟수가 상기 해싱 구조(또는 인덱스)의 개수보다 커질 때까지 상기 과정들(S13, S14, S15)이 반복된다(S16).

이러한 기존의 LSH 기법에 따라 고차원 데이터를 버킷에 삽입되는 과정은 다음과 같은 세 가지 문제점이 있다.

첫째, 기존의 기술에서는, 고차원 데이터의 값이 비트로 표현되고, 이를 비트별로 난수를 곱하여 2차 해싱이 수행된다. 즉, 기존의 기술에서는, 데이터의 분산을 향상시키기 위해 난수가 사용한다. 그러나 고차원 데이터의 차원 중에서 하나의 값만 변할지라도 비트 패턴 또한 변하기 때문에 데이터가 다른 버킷에 저장될 확률이 높아지게 된다. 즉, 서로 매우 유사한 고차원 데이터라 할지라도 같은 버킷에 삽입될 확률이 저하되어, 클러스터링 효과가 적어진다.

둘째, 해싱 기법의 특성상 한 버킷 안에 유사한 데이터가 사용자가 원하는 개수만큼 저장되지 않을 확률이 높다. 따라서 기존의 기술에서는 사용자의 질의에 따라 일정 이상(약 95%)의 정확도가 확보되지 못한다.

셋째, 고차원 데이터의 값을 기준으로 비트를 생성하므로, 그 비트의 수가 매우 크다.

상술한 바와 같은 종래 기술의 문제점을 해결하기 위하여, 고차원 데이터를 구간으로 나누어 클러스터링한 후 각 구간에 비트를 부여하고, 데이터 삽입 시 데이터를 인접 셀에도 중복 삽입함으로써, 사용자에게 높은 정확도의 검색 성능을 제공하는 고차원 데이터 색인/검색 방법 및 그 시스템을 제공하는 것이다.

상술한 바와 같은 목적을 달성하기 위한 본 발명의 일면에 따른 고차원 데이터의 색인/검색 시스템은 고차원 데이터로부터 추출된 하나의 특징 벡터가 속하는 셀을 구하고, 상기 셀을 표시하기 위한 시그니처를 생성하되, 상기 시그니처를 차원 단위로 여러 개로 나누어, 이를 다수의 인덱스에 저장하는 해싱 구조를 구축하는 해싱 연산모듈, 및 상기 구축된 해싱 구조를 기반으로, 상기 고차원 데이터의 삽입 및 검색을 수행하는 알고리즘이 저장된 저장부를 포함한다.

또한 본 발명의 일면에 따른 고차원 데이터의 검색 방법은 고차원 데이터로부터 추출된 하나의 특징 벡터가 속하는 셀을 구하고, 상기 셀을 표시하기 위한 시그니처를 생성하되, 상기 시그니처를 차원 단위로 여러 개로 나누어, 이를 다수의 인덱스에 저장하는 단계, 및 각 인덱스에 검색된 후보 셋(집합)을 합병 및 정렬하는 단계를 포함한다.

본 발명의 효과는 다음과 같다.

첫째, 본 발명에서는 고차원 데이터를 구간별로 나누어 시그니처로 표현하기 때문에, 이로 인한 클러스터링 효과를 얻을 수 있어 종래 기술에 비해 정확도를 향상시킬 수 있다.

둘째, 고차원 데이터가 버킷에 삽입되는 과정에서, 이웃 셀에도 중복 삽입을 통하여 정확도를 향상시킬 수 있다.

셋째, 종래 기술에서는 고차원 데이터의 값을 기준으로 비트열을 할당하기 때문에 비트의 수가 매우 크다. 하지만 본 발명에서는 구간을 나누어 저장하므로 구간에 해당하는 비트만을 필요로 하고, 이로 인하여 데이터 삽입 연산 수행 속도를 향상시킬 수 있다.

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

도 2는 본 발명의 실시예에 따른 고차원 데이터의 색인/검색(이하 검색) 시스템의 전체 구성을 나타내는 블록도이고, 도 3은 도 2에 도시된 시그니처 변환모듈에서 수행되는 시그티처 변환의 일예를 보여주기 위한 도면이다.

도 2를 참조하면, 본 발명의 실시예에 따른 고차원 데이터의 색인/검색 시스템(200)에서는 사용자에게 높은 정확도의 검색 성능을 제공하기 위해 기본적으로 시그니처 기반 해싱 기법이 사용된다.

구체적으로, 고차원 데이터의 색인/검색 시스템(200)은 고차원 데이터를 색인하기 위해, 시그니처 변환모듈(C1), 1차 해싱 함수모듈(C2), 이웃 셀 계산 모듈(C3) 및 2차 해싱 함수모듈(C4)을 포함하는 해싱 연산 모듈과(220), 아울러 고차원 데이터의 삽입 및 고차원 데이터의 검색을 각각 수행하는 삽입 알고리즘(242)과 검색 알고리즘(244)이 저장된 저장부(240)를 포함한다.

시그니처 변환모듈(C1)은 고차원 데이터를 차원별로 일정 구간으로 나누어, 각 구간을 비트열로 변환한다. 예를 들어 차원의 구간을 4개로 나누면, (0, 1, 2, 3)의 구간에 해당하는 비트는 (00, 01, 10, 11)와 같다. 따라서 고차원 데이터의 삽입 시에 차원별로 해당하는 구간을 탐색하여, 이를 비트로 변환한다. 예를 들어 도 3에 도시된 바와 같이, 데이터가 2차원이고 구간을 4개로 나눈 경우, (0.26, 0.3)이 비트열로 변환되면, (01, 01)이 된다.

1차 해싱 함수모듈(C2)은 1차 해싱 함수를 통한 1차 해싱 과정을 수행한다. 1차 해싱 과정은 크게 두 단계로 나눌 수 있다.

첫 번째 단계에서는, 시그니처 변환모듈(C1)에서 생성한 시그니처를 거리를 보존할 수 있도록 변환과정이 수행된다. 두 번째 단계는 변환한 시그니처에서 ‘1’의 비트 수를 기반으로 시그니처를 해싱 구조에 맵핑(Mapping)하는 과정이 수행된다.

먼저, 첫 번째 단계에서는 구간 거리를 비트 연산으로 계산할 수 있도록 시그니처 변환모듈(C1)에서 생성한 시그니처를 도 4와 같이 변환한다.

도 4는 도 2에 도시된 1차 해싱 모듈에서 수행되는 1차 해싱과정을 보여주는 도면이다.

도 4를 참조하면, 먼저 셀에 할당되는 전체 비트의 수는 나누어진 구간의 수 만큼 할당한다. 도 4에서는 상기 전체 비트의 수가 4개의 구간으로 나누어진 예가 나타난다. 따라서, 각 구간에는 4개의 비트가 할당된다. 도 4에 도시된 바와 같이, 셀이 전체 구간에서 몇 번째 구간인지를 계산하여, 그 값에 해당하는 수만큼 비트 ‘1’로 시그니처를 채운다. 예를 들어, 00은 첫 번째 구간이므로 0001을, 01은 두 번째 구간이므로 0011을, 10은 세 번째 구간이므로 0111로 변환한다. 따라서 1차 해싱 함수에서 변환하는 시그니처에서 비트 ‘1’로 채워지는 비트의 개수 N은 아래의 수학식 1과 같다.

여기서, N은 시그니처에 채워지는 비트 ‘1’의 수를 나타내고, b는 C1에서 변환한 시그니처의 비트의 수를, S는 C1에서 변환한 시그니처를, i는 계산하고자 하는 시그니처의 비트 위치를 나타낸다. 식에서 비트마다 합산한 값에 1을 더하는 이유는 변환되는 시그니처가 최소 하나의 ‘1’을 가지기 때문이다. 이와 같이 시그니처의 표현 방법을 변환하는 것은 셀의 값으로 시그니처를 표현할 때, 해싱 함수를 위해 임의의 수를 곱하면 셀 간의 상대적인 거리 및 위치 관계가 보존되기 어렵기 때문이다. 예를 들어 C1에서 생성한 시그니처 01과 10에 비트별로 임의의 수 (1, 2, 1, 3)을 곱한다면 01은 3이 되고, 10은 1이 된다. 01은 10 셀보다 더 작지만, 임의의 수를 곱하면 01이 더 커지게 된다. 따라서 예제에서와 같이 임의의 수 를 곱함에 따라 두 셀간의 위치가 뒤바뀌는 경우가 발생한다. 이는 k-최근접 질의와 같은 공간 질의 시에 잘못된 결과를 반환할 수 있음을 의미한다. 1차 해싱 함수에서 변환한 시그니처의 경우, 시그니터 변환모듈(C1)에서 생성한 시그니처를 변환한 0011과 0111에 위 예제의 임의의 수를 곱하면 0011은 4가 되고, 0111은 6이 된다. 이는 셀 간의 위치 상태를 보존하여 공간 질의 시에 부정확한 결과가 도출될 가능성을 제거할 수 있다.

두 번째 단계에서는 변환된 시그니처를 1차 해싱 구조에 맵핑하기 위해 각 차원에서 비트 수를 계산하여 1을 차감한다. 1을 차감하는 이유는 주소가 0부터 시작하기 때문이다. 계산된 비트 수에 그리드 크기(시그니처의 비트 총 개수)의 "차원-1"승을 한다. 고차원 데이터를 차원에 따라 표기하는 방식은 n차원, n-1차원, ... , 2차원, 1차원과 같다. 각 차원에서 값이 계산되면 이를 합산하여 버킷의 수로 모듈러(modular) 연산을 통해 주소를 계산한다. 버킷의 수는 차원*그리드 크기다. 예를 들어 위의 도 4의 오른쪽에서 01(0011,0111)의 값은 1차원의 0111은 1의 비트 수가 3개이므로, 해당 값은 (3-1)*4^(1-1) = 2이고, 2차원의 0011은 비트 수가 2개이고 (2-1)*4^(2-1)= 1*4 = 4이므로 최종 주소값은 (2+4)%8=6%8=6 이 된다. 이를 식으로 표현하면, 1차 해싱 함수는 아래의 수학식 2와 같다.

여기서 V는 1차 해싱 함수의 결과값을, d는 차원을, x_i는 비트로 변환된 i번째 고차원 데이터를, b는 시그니처 비트의 수를 나타낸다. 즉, 1차 해싱 구조에서 버킷의 수는 d*b가 된다.

아래의 표 1은 도 3을 참조하여 설명하는 과정에서, 그리드에 해당하는 비트를, 1차 해싱 함수의 상기 첫 번째 단계와 상기 두 번째 단계를 통하여 획득된 버킷의 주소값의 일 예를 보여주는 표이다.

다시 도 2를 참조하면, 이웃 셀 계산모듈(C3)은 현재 고차원 값을 기반으로 먼저 삽입할 이웃 셀 중에 제일 작은 주소값을 계산한다. 이는 현재 고차원 데이터가 존재하는 그리드의 값에서 모두 최상위 비트를 차감하여 계산할 수 있다. 예를 들어 (0011, 0011)의 경우 이웃 셀 중에 최소값을 가지는(0001, 0001)의 셀부터 이웃 셀을 계산한다.

계산을 시작할 이웃 셀이 결정되면, 나머지 이웃 셀들이 1차 해싱 구조에서 계산된다. 이웃 셀은 순차적으로 차원의 비트가 변할 때마다 일정한 간격으로 계산된다.

도 5는 도 2에 도시된 이웃 셀 계산모듈에서 수행되는 데이터의 이웃 셀 계산과정의 일예를 보여주는 도면이고, 도 6은 4, 5, 6차원의 비트가 변하는 경우 이웃 셀 간격을 보여주는 도면이다.

도 5를 참조하면, 그리드의 크기가 4일 때, 2차원의 비트가 변하는 이웃 셀의 간격은 4이고, 3차원의 비트가 변하는 이웃 셀의 간격은 8(=[4-2]*4)이다. 즉, 2차원에서 이웃 셀의 간격은 그리드 크기이고, 3차원은 (2차원 간격-2)*그리드 크기이다.

도 6을 참조하면, 4, 5, 6차원의 비트가 변하는 경우 이웃 셀 간격을 계사하는 과정은 2, 3차원의 (이전 차원 간격-2)*그리드 크기의 규칙이 그대로 적용됨을 알 수 있다. 즉, 4차원의 비트가 변하는 이웃 셀의 간격은 24(=[8-2]*4)이고, 5차원의 경우, 이웃 셀의 간격은 88(=[24-2]*4)이고, 6차원의 경우, 이웃 셀의 간격은 344(=[88-2]*4)이다.

만일, 현재 셀이 (0001, 0001)과 같이 그리드의 처음 시작 셀이거나, (1111, 1111)과 같이 그리드의 마지막 셀인 경우에는 간격에서 (해당차원-1)*그리드 크기를 합산한다. 이는 그리드의 끝에 있어서 계산되지 않는 이웃 셀로 인하여 간격이 증가하기 때문이다. 예를 들어 (0011, 0001, 0011)의 경우 이전 이웃 셀(0001, 0011, 0011)과 다음 이웃 셀(0011, 0001, 0011)과의 간격은 12셀이다. 즉, (4-2)*4+(4*(2-1))=12를 의미한다. 따라서 이웃 셀간의 간격은 아래의 수학식 3과 같다.

여기서 I는 셀간의 간격을 나타내고, i는 셀간의 간격이 바뀌는 해당 차원을 나타내고, xi는 간격이 바뀌는 차원의 시그니쳐를 나타내고, d는 차원을 나타내고, s와 e는 각각 그리드의 처음 셀과 마지막 셀을 나타내고, G는 그리드의 크기(각 차원을 분할하는 구간의 개수)를 나타낸다.

도 7은 이웃 셀을 삽입하는 과정의 일예를 보여주는 순서도이다.

도 7을 참조하면, 이웃 셀 삽입을 위해 차원을 저장하는 i(예컨대, 2) 와 해당 차원에서 이웃 셀의 계산 횟수(cnt: cnt2~ cntd)를 저장 및 계산된 결과를 저장할 그룹 R을 초기화 한다(S701).

초기화 후 최소 이웃 셀의 위치 C를 계산하고, C의 인접 셀 C+I1과 C+2I1를 R에 저장한다(S702, S703). 이는 1차원 상에서 인접한 셀을 저장한 것이다.

삽입될 인접 셀을 결정하기 위해 CS를 C+I1으로 설정한다(S704). 즉, CS는 1차원 상에서 인접한 셀들 중에서 중간 셀 위치에 해당한다. 이는 중간 셀을 통해 1 차원 상에서 이웃하는 이전 셀(CS-I1)과 이후 셀(CS+I1)을 저장하기 위함이다 (도 6의 (b)를 참조).

삽입될 이웃 셀의 간격 Ii를 계산하고, Ii와 CS에 따라 삽입될 이웃 셀을 R에 저장한다(S705~S707). 아울러 이웃 셀 계산횟수(cnt)를 증가시킨다(S708). 만일 이웃 셀 계산횟수(cnt)가 2회 미만이면 i의 차원을 살펴본다. 셀 계산횟수가 2회 이상인지를 확인하는 것은 이웃 셀이 전, 후로 1개씩 존재하여, 이웃 셀 간격계산을 2회 반복하기 때문이다. 만일 i의 차원이 2차원이 아닌 경우에는 i를 2로 설정한다. 이는 아직 모든 차원마다 이웃 셀이 계산되지 않았기 때문이다. 따라서 이웃 셀 계산을 위해 다시 2차원부터 시작하여, 상기 과정(S705)부터 계산을 반복한다. 만일 i의 차원이 2차원일 경우, 상기 과정(S705)부터 계산을 반복한다(S709 ~ S711). 만일 이웃 셀 계산횟수(cnt)가 2회 이상이고, 계산된 데이터의 차원이 최고 차원(d)이 아니면 차원을 증가시켜 다음 차원의 이웃 셀을 계산한다. 만일 현재 계산된 차원이 데이터의 최고 차원(d)이라면 알고리즘은 종료된다(S712 ~ S714).

다시 도 2를 참조하면, 2차 해싱 함수모듈(C4)은 1차 해싱 구조가 매우 큰 버킷 개수를 가지기 때문에, 이를 B개의 버킷에 압축하여 저장한다.

2차 해싱 함수를 설계하기 위하여, 1차 해싱의 버킷 값을 비트별로 임의의 난수를 곱하여 더하고, 이 결과값과 2차 해싱 함수의 버킷 개수(B) 간의 모듈러 연산이 수행된다. 비트별로 난수를 곱하는 이유는 데이터를 버킷에 균일하게 분배하기 위함이다.

2차 해싱 함수는 아래의 수학식 4와 같다.

여기서, H는 2차 해싱 함수의 결과값을 나타내고, k는 비트의 수를 나타내고, B는 버킷의 수를 나타내고, V는 k개의 비트로 변환된 고차원 데이터의 비트 집합을 나타내고, A는 1 ~ B 사이의 임의의 난수를 비트의 수만큼 발생시킨 집합을 나타낸다.

표 1의 1차 해싱 구조의 주소를 2차 해싱 구조로 맵핑하는 경우, B가 4이고, A가 {1,3,1,2,4,2,1,3}이면, 1차 해싱 구조 각각의 주소는 아래의 표 2와 같이 2차 해싱 구조의 주소로 변환된다. 아울러 2차 해싱 구조에서는 중복되는 데이터가 많으므로, 저장공간의 낭비를 방지하기 위해 데이터의 아이디만을 유지하고 나머지 실제 고차원 벡터 데이터는 다른 저장소에 저장된다.

이하, 도 2에 도시된 저장부(240)에 저장된 삽입 알고리즘(242)과 검색 알고리즘(244)에 대해 상세히 설명하기로 한다.

먼저, 도 8을 참조하여, 도 2에 도시된 고차원 데이터의 삽입 알고리즘(242)에 대해 설명하기로 한다.

도 8은 도 2에 도시된 삽입 알고리즘의 일예를 보여주는 순서도이다.

도 8을 참조하면, 먼저 데이터를 삽입하기 전에, 시스템은 2차 해싱의 버킷 수와 시그니처 변환을 위한 구간의 수가 결정되고, 2차 해싱을 위한 난수가 생성된다.

이후, 시그니처 변환모듈(C1: 도 2에 도시됨)에 의해 고차원 데이터가 비트열로 변환된다(S910). 이어, 변환된 비트열이 차원을 기반으로 인덱스의 개수만큼 분할된다(S920). 이는 고차원 데이터의 위상을 보존하기 위함이다. 이어, 이웃 셀 계산모듈(C3: 도 2에 도시됨)에 의해 중복 삽입할 셀이 결정된다(S930). 이어, 1차 해싱 함수모듈(C2: 도 2에 도시됨)에 의해 1차 해싱이 수행되고, 아울러 인덱스에 할당되는 비트 수를 기반으로 난수가 생성된다(S940).

이어, 2차 해싱 함수모듈(C4: 도 2에 도시됨)에 의해 2차 해싱이 수행되고, 버킷에 검출되고(S950), 검출된 버킷에 최종적으로 데이터가 저장된다(S960),

이어, 비트열을 차원을 기반으로 인덱스의 개수만큼 분할한 모든 비트열의 부분에 대해 상기 과정들(S930 ~ S960)을 수행하면(S970), 모든 과정이 종료된다.

도 9는 도 8에 도시된 삽입 알고리즘을 이용한 실제 적용 예를 보여주기 위한 도면이다.

도 9를 참조하면, 삽입할 데이터가 Ｏ1(0.1, 0.3, 0.7, 0.12)인 경우, (0001, 0011, 0111, 0001)와 같은 비트로 변환된다(도 9의 "(1)비트열로 변환": 도 8의 S910).

이어, 차원을 기반으로 1 및 3 차원과 2 및 4차원으로 분할된 이후, 방위에 따라 삽입할 이수 셀을 계산하는 과정이 수행된다(도 9의 "(2) 차원 분할 및 이웃 셀 계산": 도 8의 S920, S930).

이어, 이웃 셀 계산에 의해 2차 해싱에 사용할 1차 해싱 값인 시그니처가 생성되고, 이를 임의의 난수 A집합({1, 3, 1, 2, 4, 2, 1, 3}, {1, 2, 1, 3, 4, 2, 3, 1})에 따라 2차 해싱값으로 변환하는 과정이 수행된다(도 9의 "(3)1차 해싱값을 2차 해싱값으로 변환": 도 8의 S940, S950).

이어, 최종적으로 저장되는 데이터는 도 9의 맨 우측에 도시된 바와 같다. 즉, 1 및 3차원으로 분할된 데이터는 2차 해싱 버킷의 0, 1, 4, 5, 6, 7에 저장되고, 2 및 4차원으로 분할된 데이터는 0, 2, 4, 5, 7에 저장된다.

이하, 도 10을 참조하여, 도 2에 도시된 고차원 데이터의 검색 알고리즘(244)에 대해 설명하기로 한다.

도 10은 도 2에 도시된 검색 알고리즘의 일예를 보여주는 순서도이다.

도 10을 참조하면, 사용자에 의해 k개의 유사 고차원 데이터를 검색 위하여 검색 알고리즘이 호출된다.

먼저, 시그니처 변환모듈(C1: 도 2에 도시됨)에 의해 고차원 데이터가 비트열로 변환된다(S1110). 이어, 상기 비트열로 변환된 고차원 데이터는 인덱스 개수만큼 차원이 분할되고(S1120), 1차 해싱 함수모듈(C2: 도 2에 도시됨)을 통해 1차 해싱 주소값이 계산된다(S1130). 이어, 2차 해싱 함수모듈(C4: 도 2에 도시됨)을 통해 2차 해싱 주소값이 계산된다(S1140). 이어, 계산된 주소값을 통하여 해당 버킷에 저장되어 있는 데이터가 검색되고(S1150), 후보 셋이 저장된다(S1160). 이어, 비트열을 차원을 기반으로 분할한 모든 비트열의 부분에 대해 상기 과정들(S1130 ~ S1160)이 반복 수행된다(S1170). 분할한 모든 비트열의 부분에 대해 수행되었으면, 획득된 후보셋이 병합 및 정렬되고(S1180), k개의 고차원 데이터가 반환됨으로써, 최종적인 결과가 사용자에게 전송된다(S1190).

도 11은 도 12에 도시된 검색 알고리즘의 실제 적용 예를 보여주는 도면이다.

도 11을 참조하면, 현재 저장되어 있는 데이터는 Ｏ1(0.1, 0.3, 0.7, 0.12)과 Ｏ2(0.4, 0.7, 0.2, 0.8)로 가정한다. Ｏ1에 대한 삽입 과정은 도 10을 참조하여, 설명한 바와 같으며, Ｏ1에 대한 삽입 과정과 Ｏ2에 대한 삽입 과정은 동일한 과정이므로, Ｏ2에 대한 삽입 과정에 대한 구체적인 설명은 전술한 도 10을 참조하여 설명한 Ｏ1에 대한 삽입 과정으로 대신한다. 또한 질의 데이터는 Q(0.26, 0.3, 0.26, 0.3)과 같으며 사용자가 검색하고자 하는 유사한 고차원 데이터의 수는 1개라 가정한다.

먼저, 상기 질의 데이터(Q(0.26, 0.3, 0.26, 0.3))가 비트열로 변환된다(Q(0011, 0011, 0011, 0011)). 변환된 비트열이 1 및 3차원과, 2 및 4차원으로 분할된다. 1차 해싱값이 2차 해싱값으로 변환된다. 도 13의 적용 예에서는 변환된 해싱값이 모두 7이다. 2차 해싱값이 계산되면, 해당 버킷이 탐색 및 저장된다. 도 13의 적용 예에서는 첫 번째 인덱스에서는 Ｏ1과 Ｏ2가 후보로 선출되고, 두 번째 인덱스에서는 O1이 선출된다. 각 인덱스별로 후보셋이 결정되면, 결정된 후보셋이 병합되고, 실제 거리 순으로 정렬된다. 본 적용 예에서는 Ｏ1과 Q와의 거리가 0.5로서, Ｏ2와 Q와의 거리인 0.658보다 적으므로, Ｏ1이 결과로 도출된다.

도 2는 본 발명의 실시예에 따른 고차원 데이터의 색인/검색 시스템의 전체 구성을 나타내는 블록도이다.

3은 도 2에 도시된 시그니처 변환모듈에서 수행되는 시그니처 변환의 일예를 보여주기 위한 도면이다.

도 5는 도 2에 도시된 이웃 셀 계산모듈에서 수행되는 데이터의 이웃 셀 계산과정의 일예를 보여주는 도면이다.

도 6은 4, 5, 6차원의 비트가 변하는 경우 이웃 셀 간격을 보여주는 도면이다.

Claims

멀티미디어 객체로부터 추출된 고차원의 특징 데이터를 색인하고, 저장하여, 상기 저장된 고차원 데이터의 검색을 수행하는 검색시스템에 있어서,

상기 특징 데이터로부터 추출된 하나의 특징 벡터가 속하는 셀을 구하고, 상기 셀을 표시하기 위한 시그니처를 생성하되, 상기 시그니처를 차원 단위로 여러 개로 나누어, 이를 다수의 인덱스에 저장하는 해싱 구조를 구축하고, 이 해싱 구조를 구축하는 과정에서 상기 특징 데이터를 삽입하고자 하는 셀 뿐만 아니라 인접한 이웃 셀에 중복 삽입하는 해싱 연산모듈; 및

상기 구축된 해싱 구조를 기반으로, 상기 특징 데이터의 삽입 및 검색을 수행하는 알고리즘이 저장된 저장부를 포함하는 고차원 데이터의 색인/검색 시스템.
제 1 항에 있어서, 상기 해싱 연산모듈은,

상기 특징 데이터의 클러스터링을 위해 공간을 상기 차원 단위로 일정 구간으로 나누고, 각 일정 구간에 상기 시그니처를 부여하는 시그니처 변환모듈;

상기 시그니처 변환모듈에서 부여된 시그니처 간의 거리를 보존할 수 있도록 재변환하고, 재변환된 시그니처에서 '1'의 비트 수를 기반으로 상기 재변환된 시그니처를 상기 해싱 구조에 맵핑(Mapping)하여, 1차 해싱 구조를 구축하는 1차 해싱함수 모듈;

검색의 정확도의 향상을 위해 상기 특징 데이터를 삽입하고자 하는 셀 뿐만 아니라 인접한 이웃 셀에 중복 저장하는 이웃 셀 계산 모듈; 및

상기 구축된 1차 해싱 구조의 버킷 개수를 B개의 버킷에 압축저장하여, 상기 1차 해싱 구조를 2차 해싱 구조에 맵핑하는 2차 해싱 함수모듈을 포함하는 것인 고차원 데이터의 색인/검색 시스템.
제2항에 있어서, 상기 시그니처 변환모듈은 상기 특징 데이터를 상기 일정 구간별로 나누고, 이를 기반으로 비트열을 생성하는 것인 고차원 데이터의 색인/검색 시스템.
제2항에 있어서,

상기 시그니처 변환모듈은 아래의 수학식 1에 따라 상기 시그니처를 구성하는 비트 '1'의 길이를 계산하여, 상기 시그니처를 재변환하고,

상기 수학식 1은,

이고,

여기서, 상기 N은 시그니처에 채워지는 비트 ‘1’의 수를 나타내고, 상기 b는 상기 시그니처의 비트의 수를 나타내고, 상기 S는 상기 시그니처를 나타내고, 상기 i는 계산하고자 하는 시그니처의 비트 위치를 나타내는 것인 고차원 데이터의 색인/검색 시스템.
제4항에 있어서,

상기 1차 해싱 함수모듈은 상기 재변환된 시그니처를 아래의 수학식 2에 따라 상기 해싱 구조에 맵핑되는 주소를 계산하고,

상기 수학식 2는,

이고,

여기서 상기 V는 상기 1차 해싱 구조의 결과값을 나타내고, d는 차원을 나타내고, x_i는 비트로 변환된 i번째 특징 데이터를 나타내고, b는 상기 시그니처 비트의 수를 나타내고, 1차 해싱 구조에서 버킷의 수는 d*b는 상기 1차 해싱구조에서의 버킷의 수를 나타내는 것인 고차원 데이터의 색인/검색 시스템.
제2항에 있어서, 상기 이웃 셀 계산모듈은 상기 1차 해싱 구조에서 이웃 셀 간의 간격을 차원에 따라 아래의 수학식 3에 근거하여 계산하고,

상기 수학식 3은,

이고, 여기서 I는 셀간의 간격을 나타내고, i는 셀간의 간격이 바뀌는 해당 차원을 나타내고, x_i는 간격이 바뀌는 차원의 시그니쳐를 나타내고, d는 차원을 나타내고, s와 e는 각각 그리드의 처음 셀과 마지막 셀을 나타내고, G는 그리드의 크기(각 차원을 분할하는 구간의 개수)를 나타내는 것인 고차원 데이터의 색인/검색 시스템.
멀티미디어 객체로부터 추출된 고차원의 특징 데이터를 색인 및 검색을 실행하기 위해, 해싱 연산모듈과 저장부가 탑재된 컴퓨팅 장치를 이용하여, 상기 고차원의 특징 데이터를 색인 및 검색하는 방법에 있어서,

상기 해싱 연산모듈이 상기 특징 데이터로부터 추출된 하나의 특징 벡터가 속하는 셀을 구하고, 상기 셀을 표시하기 위한 시그니처를 생성하되, 상기 시그니처를 차원 단위로 여러 개로 나누어, 이를 다수의 인덱스에 저장하고, 상기 특징 데이터를 삽입하고자 하는 셀 뿐만 아니라 인접한 이웃 셀에 중복 삽입하는 단계;

상기 해싱 연산모듈이 각 인덱스에 검색된 후보 셋(집합)을 합병 및 정렬하여 해싱 구조를 구축하는 단계; 및

상기 저장부가 상기 특징 데이터의 삽입 및 검색을 수행하기 위해 상기 구축된 해싱 구조를 저장하는 단계를 포함하는 고차원 데이터의 색인/검색 방법.
제7항에 있어서, 시그니처 변환모듈, 1차 해싱함수 모듈, 이웃 셀 계산 모듈 및 2차 해싱 함수모듈로 구성된 상기 해싱 연산모듈에 의해 상기 다수의 인덱스를 저장하는 단계는,

상기 시그니처 변환모듈이 상기 특징 데이터의 클러스터링을 위해 공간을 일정 구간으로 나누고, 각 구간에 시그니처를 부여하는 단계;

상기 1차 해싱함수 모듈이 상기 부여된 시그니처를 거리 간의 거리를 보존할 수 있도록 재변환하고, 재변환된 시그니처에서 '1'의 비트 수를 기반으로 상기 재변환된 시그니처를 1차 해싱구조에 사상하는 단계;

상기 이웃 셀 계산 모듈이 검색의 정확도의 향상을 위해 상기 특징 데이터를 삽입하고자 하는 셀 뿐만 아니라 인접한 이웃 셀에 중복 저장하는 단계; 및

상기 2차 해싱 함수 모듈이 상기 1차 해싱 구조의 버킷 개수를 B개의 버킷에 압축저장하여, 상기 1차 해싱 구조를 2차 해싱 구조에 맵핑하는 단계를 포함하는 고차원 데이터의 색인/검색 방법.
제7항에 있어서, 시그니처 변환모듈, 1차 해싱함수 모듈, 이웃 셀 계산 모듈 및 2차 해싱 함수모듈로 구성된 상기 해싱 연산모듈에 의한 상기 특징 데이터의 삽입 단계를 더 포함하고,

상기 특징 데이터의 삽입 단계는,

상기 시그니처 변환모듈에 의해 상기 특징 데이터가 비트열로 변환되고, 상기 변환된 비트열이 차원을 기반으로 인덱스의 개수만큼 분할되는 단계;

상기 이웃 셀 계산 모듈에 의해 중복 삽입할 셀이 결정되는 단계;

상기 1차 해싱함수 모듈에 의해 1차 해싱이 수행되고, 아울러 인덱스에 할당되는 비트 수를 기반으로 난수가 생성되는 단계;

상기 2차 해싱함수 모듈에 의해 2차 해싱이 수행되고, 버킷을 탐색하고, 탐색된 버킷에 최종적으로 데이터가 저장되는 단계;

비트열을 차원을 기반으로 인덱스의 개수만큼 분할한 모든 비트열의 부분에 대해 상기 단계들이 수행되면, 모든 단계가 종료되는 단계

를 포함하는 것인 고차원 데이터의 색인/검색 방법.
제7항에 있어서, 시그니처 변환모듈, 1차 해싱함수 모듈, 이웃 셀 계산 모듈 및 2차 해싱 함수모듈로 구성된 상기 해싱 연산모듈에 의한 상기 특징 데이터의 검색 단계를 더 포함하고,

상기 특징 데이터의 검색 단계는,

상기 시그니처 변환모듈에 의해 상기 특징 데이터가 비트열로 변환되고, 변환된 비트열이 인덱스 개수만큼 차원이 분할되는 단계;

상기 1차 해싱함수 모듈에 의해 1차 해싱 주소값이 계산되는 단계;

상기 2차 해싱함수 모듈에 의해 2차 해싱 주소값이 계산되는 단계;

상기 저장부가 계산된 주소값을 통하여 해당 버킷에 저장되어 있는 데이터가 검색되고, 후보 셋이 저장되는 단계; 및

비트열을 차원을 기반으로 분할한 모든 비트열의 부분에 대해 상기 단계들을 수행한 후에, 획득된 후보셋이 병합 및 정렬되고, k개의 특징 데이터가 반환됨으로써, 최종적인 결과가 상기 컴퓨팅 장치를 통해 사용자에게 전송되는 단계를 포함하는 것인 고차원 데이터의 색인/검색 방법.