KR101266358B1 - 다중 길이 시그니처 파일 기반 분산 색인 시스템 및 방법 - Google Patents

Abstract

본 발명은 다중 길이 시그니처 파일 기반 분산 색인 시스템 및 방법에 관한 것으로서, 멀티미디어 객체 및 식별자로부터 N-차원의 특징벡터를 추출하는 특징벡터 추출수단, 상기 멀티미디어 객체의 객체 식별자와 N-차원의 특징벡터에 따른 트리 기반의 분산 색인을 구성하고, 구성한 분산 색인 트리의 말단 노드 개수와 기준 클러스터의 크기를 비교하여 시그니처의 길이를 결정하는 분산색인 관리수단 및 상기 결정한 길이를 반영한 말단 노드별 시그니처를 생성하여 상기 N-차원의 특징벡터와 매칭하여 저장하는 고차원 색인관리수단을 포함하여 구성한 장치 및 그 방법을 제공함으로써, 데이터의 분포에 따라 분산 색인 트리 내 단말의 컴퓨팅 노드가 다른 길이의 시그니처 파일을 독자적으로 구성할 수 있어 클러스터의 크기가 작은 경우에 더 많은 비트로 구성되는 시그니처를 생성함으로써, 효율적인 검색을 통해 필터링 효과를 증대시키고, 분산 색인 트리의 탐색을 통해 결정되는 말단 노드가 하나 이상인 경우 각 노드에서 시그니처 기반의 필터링이 병렬로 수행되기 때문에 노드별 다른 길이의 시그니처에 따른 추가 비용이 발생하지 않고, 검색의 정확도가 증가한다는 효과도 얻어진다.

고차원 데이터, 특징벡터, 분산 색인, 시그니처, 트리 기반, 검색

Description

다중 길이 시그니처 파일 기반 분산 색인 시스템 및 방법{A distributed index system based on multi-length signature files and method thereof}

본 발명은 다중 길이 시그니처 파일 기반 분산 색인 시스템 및 방법에 관한 것으로서, 보다 자세하게는 클러스터 환경에서 대용량의 고차원 데이터에 대한 효과적인 검색을 지원하기 위한 시그니처 파일 기반의 분산 색인 시스템 및 방법에 관한 것이다.

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

최근 컴퓨팅 기술 및 미디어 기술의 발달, 그리고 웹 2.0의 등장으로 인터넷 서비스가 공급자 중심에서 사용자 중심으로 패러다임이 이동함에 따라 사용자 제작 컨텐츠(user created contents, UCC)와 함께 인터넷 서비스에서 멀티미디어 데이터의 양과 이에 대한 사용이 빠르게 증가하고 있다. 그리하여, 사용자가 보유한 이미지나 동영상에 근거하여 이미지 혹은 동영상을 찾는 내용 기반 검색 문제가 대두되고 있다. 이를 해결하기 위하여, 이미지, 오디오, 비디오와 같은 멀티미디어 데이 터를 분석하여 이를 고차원의 특징 데이터(feature vector)로 변환하고 이에 대한 색인을 구축한 후에, 고차원 데이터간의 유사성을 찾는 방법들이 제안되었다.

종래 고차원 데이터에 대한 내용 기반 검색을 지원하기 위한 색인 연구는 크게 트리 기반 과 필터링 기법으로 나눌 수 있다.

트리 기반 고차원 색인 기법은 K-D-B tree, Quad tree와 같이 데이터 공간을 분할하거나, R-tree, X-tree, M-tree와 같이 흩어져 있는 데이터를 클러스터링 한 후에 근접한 객체들의 집합을 나타내는 사각형이나 원을 검색 단위로 사용하였다. 이러한 트리 기반 색인 기법은 데이터의 차원이 증가할수록 근접한 객체들의 집합을 나타내는 사각형이나 원 사이에 겹침 영역이 확대됨으로 인해 검색 성능이 기하급수적으로 떨어져서 순차 검색보다도 성능이 나빠지는 차원의 저주(dimensional curse) 문제가 발생하여 이에 대한 개선이 요구된다.

반면, VA-file, CBF와 같은 필터링 기반 색인 기법은 차원 별로 데이터 공간을 분할하고 비트(bit)를 할당한 후, 이를 벡터의 요약값(시그니처, approximation)으로 사용한다. 필터링 기반 색인 기법은 이렇게 생성된 시그니처의 순차 탐색를 통해 불필요한 데이터의 가지치기(pruning)를 수행함으로써, 고차원 데이터에 대한 범위 질의(range query) 혹은 k-최근접 질의(k-nearest neighbor search)의 검색 성능을 개선하였다.

필터링 기반 색인 기법은 트리 기반 색인 기법과 달리 차원의 증가가 성능에 크게 영향을 받지 않는 반면, 데이터가 증가할수록 순차 탐색의 부하가 증가된다는 문제가 있다.

따라서, 필터링 기반 색인 기법에서 시그니처를 위한 비트의 길이는 읽어야 하는 데이터의 크기 및 검색의 정확도를 결정하는 중요한 요소라 하겠다. 즉, 시그니처를 위한 비트 길이를 크게 할수록 필터링 대상이 커져 정확도가 증가하는 반면, 검색해야 하는 대상 시그니처의 크기가 커지게 된다. 그러나, 기존 대부분의 필터링 기반 색인 기법들은 시그니처 표현을 위한 비트 길이 결정 시에 대상 데이터의 분포 정보를 고려하지 않고 있다.

즉, 도 2에 도시된 바와 같이 고차원 데이터에 대한 범위 질의 혹은 k-최근접 질의와 같은 유사성 검색시에 클러스터(200, 210, 220, 250) 내 객체의 특징벡터는 차원당 2bit로 구성되는 시그니처로의 변환만으로 필터링 효과를 얻을 수 있다.

그러나 다른 클러스터에 비해 클러스터 크기가 작은 클러스터(230, 240)에 포함된 객체의 특징벡터들은 각각 한 셀에 모두 포함되어 2bit의 시그니처로는 필터링 효과를 얻을 수 없다. 즉, 클러스터의 크기가 작은 클러스터(230, 240)는 적어도 차원당 2bit보다는 큰 비트 길이의 시그니처로 표현되는 경우에 한하여 유사성 검색시에 필터링을 통한 성능 향상을 기대할 수 있으나, N-차원의 데이터 공간을 균일한 개수의 공간으로 분할함으로써 구성되는 셀의 시그니처가 그 셀에 포함되는 모든 객체의 특징벡터를 대체하는 경우, 고차원 공간 상의 특징벡터의 분포정보를 반영하지 못하는 시그니처로 인하여 검색기능이 저하됨을 알 수 있다. 이는 검색의 대상이 되는 고차원 데이터의 개수가 대용량화 될수록 검색 성능의 차이 또 한 커진다는 문제점이 있었다.

한편, 멀티미디어 서비스가 차세대 인터넷 서비스로 부각되면서, 멀티미디어 데이터가 기하급수적으로 늘어나 단일 컴퓨팅 노드에서 수십억 개의 멀티미디어 개체들에 대한 고차원 인덱스를 색인화하기 어려운 상황이다. 클러스터 환경에서 고확장성을 지원하기 위한 색인 구조로써, 트리 기반 색인 기법에서는 서브 트리별로 분할하여 여러 노드에 분산 저장할 수 있으나, 트리 기반 색인 기법이 데이터의 차원이 증가할수록 순차 검색 성능보다 좋지 않은 점을 감안하면 효과적인 방법이라 할 수 없다. 필터링 기반 색인 기법은 전체 시그너처 파일을 순차적으로 검색하기에 시그너처 파일을 분할 및 분산 저장하여도 각 노드에서 병렬적으로 전체 검색을 유발하는 문제점을 갖고 있다. 즉, 기존 고차원 데이터의 색인 기법은 클러스터 컴퓨터 환경 및 병렬 처리에 대한 깊은 고려가 없어, 대용량의 고차원 데이터의 검색에 있어 그 성능이 우수하지 못하다는 문제가 있었다.

본 발명의 목적은 상술한 바와 같은 종래의 문제점을 해결하기 위한 것으로서, 데이터 양의 증가에 대한 고확장성 지원 및 데이터의 분포 정보를 반영한 다중 길이의 시그니처를 기반으로, 고차원의 특징 벡터를 이용하여 대용량의 고차원 데이터에 대한 효과적인 검색을 지원하는 장치 및 방법을 제공하는 것이다.

본 발명의 다른 목적은 분산 색인 트리의 탐색을 통해 결정되는 말단 노드가 하나 이상인 경우 각 노드에서 시그니처 기반의 필터링을 병렬로 수행하여 노드별 다른 길이의 시그니처에 따른 추가 비용이 발생하지 않고, 검색의 정확도를 증가시킬 수 있는 장치 및 방법을 제공하는 것이다.

상기와 같은 목적을 달성하기 위하여, 본 발명에 따른 다중 길이 시그니처 파일 기반 분산 색인 시스템은, 멀티미디어 객체 및 상기 멀티미디어 객체의 객체 식별자로부터 N-차원의 특징벡터를 추출하는 특징벡터 추출수단과, 상기 멀티미디어 객체의 객체 식별자와 N-차원의 특징벡터에 따른 트리 기반의 분산 색인을 구성하고, 구성한 분산 색인 트리의 말단 노드의 클러스터 크기와 상기 N-차원의 특징 벡터의 공간 크기를 상기 말단 노드의 전체 개수로 나눈 평균 크기로 정의되는 기준 클러스터의 크기와 비교하여, 상기 말단 노드의 크기가 상기 기준 클러스터의 크기 이상인 경우, 제1 비트 수로 표현되는 시그니터의 길이를 결정하고, 상기 말단 노드의 크기가 상기 기준 클러스터의 크기보다 작은 경우, 상기 제1 비트 수보다 큰 제2 비트 수로 표현되는 시그니처의 길이를 결정하는 고차원 색인수단 및 상기 결정한 시그니처의 길이를 반영한 말단 노드별 시그니처를 생성하고, 생성된 시그니처, 상기 N-차원의 특징 벡터 및 상기 객체 식별자를 해당 컴퓨팅 노드에 저장하는 고차원 색인관리수단으로 이루어질 수 있다.
또한, 본 발명에 따른 다중 길이 시그니처 파일 기반 분산 색인 방법은, 멀티미디어 객체들로부터 N-차원의 특징벡터를 추출하는 단계, 상기 추출된 N-차원의 특징벡터에서 임의 표본 추출을 통해 트리기반의 분산 색인을 구성하는 단계, 상기 구성한 분산 색인 트리의 말단 노드별 클러스터 크기를 계산하여 그에 따른 시그니처 길이를 결정하는 단계, 상기 분산 색인 트리의 말단 노드별 해당 컴퓨팅 노드를 결정하는 단계 및 상기 컴퓨팅 노드에 결정한 길이별 시그니처를 생성하여 N-차원의 특징벡터와 개별 매칭하여 저장하는 단계를 포함하여 이루어질 수 있다.

삭제

또한, 본 발명에 따른 다중 길이 시그니처 파일 기반 분산 색인 방법은, 저장된 멀티미디어 객체로부터 특징벡터를 추출하는 단계, 상기 추출한 특징벡터를 기반으로 분산 색인 트리를 탐색하여 유사한 값을 가지는 후보 말단 노드를 결정하여 유사검색을 요청하는 단계, 상기 유사검색 요청시 상기 결정한 후보 말단 노드에서 관리하는 시그니처를 생성하여 이를 기준으로 저장한 시그니처 파일을 순차 검색하여 후보 시그니처들을 결정하는 단계 및 상기 특징벡터를 가지는 후보 시그니처를 검색하여 최종 후보를 결정하는 단계를 포함하여 이루어질 수 있다.

상술한 바와 같이, 본 발명에 따른 다중 길이 시그니처 파일 기반 분산 색인 시스템 및 방법에 의하면, 데이터의 분포에 따라 분산 색인 트리 내 단말의 컴퓨팅 노드가 다른 길이의 시그니처 파일을 독자적으로 구성할 수 있어 클러스터의 크기가 작은 경우에 더 많은 비트로 구성되는 시그니처를 생성함으로써, 효율적인 검색을 통해 필터링 효과를 증대시킨다.

또한, 본 발명에 따른 다중 길이 시그니처 파일 기반 분산 색인 시스템 및 방법에 의하면, 분산 색인 트리의 탐색을 통해 결정되는 말단 노드가 하나 이상인 경우 각 노드에서 시그니처 기반의 필터링이 병렬로 수행되기 때문에 노드별 다른 길이의 시그니처에 따른 추가 비용이 발생하지 않고, 검색의 정확도가 증가한다는 효과도 얻어진다.

이하, 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 본 발명을 용이하게 실시할 수 있을 정도로 상세히 설명하기 위하여, 본 발명의 가장 바람직한 실시예를 첨부한 도면을 참조하여 상세하게 설명한다. 또한, 본 발명을 설명하는데 있어서 동일 부분은 동일 부호를 붙이고, 그 반복 설명은 생략한다.

도 1은 본 발명의 실시예에 따른 다중 길이 시그니처 파일 기반 분산 색인 시스템의 구성을 간략하게 보인 블록도이고, 도 3은 본 발명의 실시예에 따른 데이터 분포를 고려한 트리 기반의 분산 색인의 구조를 보인 도면이며, 도 4는 본 발명의 실시예에 따른 대용량의 고차원 데이터의 색인을 위한 트리 구조를 보인 도면이다.

도 1에서 도시한 바와 같이, 본 발명에 따른 분산 색인 시스템은 객체관리기(110), 분산저장소(120), 특징벡터 추출기(130), 고차원 색인기(140) 및 고차원 색인관리기(150)를 포함한다.

객체관리기(110)는 입력되는 오디오, 동영상 또는 이미지의 멀티미디어 객체(100)로부터 객체 식별자를 추출하고, 멀티미디어 객체 정보를 저장하도록 관리한다.

분산저장소(120)는 상기 멀티미디어 객체(100)의 정보를 개별 저장한다.

특징벡터 추출기(130)는 상기 멀티미디어 객체(100) 및 상기 멀티미디어 객체의 객체 식별자로부터 N-차원의 특징벡터를 추출한다.

고차원 색인기(140)는 분산색인 생성부(141), 시그니처 길이 결정부(142) 및 분산색인 관리부(143)를 포함한다.

분산색인 생성부(141)는 도 3에 도시한 바와 같이 N-차원의 특징벡터들로부터 클러스터 컴퓨팅 환경 내의 하나의 노드에서 수용 가능한 개수 만큼의 특징벡터를 임의 표본 추출하여 2차원의 특징벡터의 공간을 트리구조로 인덱싱한다. 이때, 구성되는 트리는 M-tree, SP-tree, Hybrid-tree 등과 같이 특징벡터 공간을 분할하는 트리는 모두 가능한데, 도 4에 도시한 바와 같이 표본 추출된 특징벡터들은 트리의 비말단 노드(401)를 구성하여 트리 내의 탐색을 결정짓는 라우팅 노드(routing node)로 역할을 하도록 할 수 있다.

시그니처 길이 결정부(142)는 상기 구성된 트리의 말단 노드에 해당하는 클러스터 크기를 계산하는데, 이때, 말단 노드에 해당하는 특징 벡터 공간의 중심점에서 클러스터 경계까지의 거리를 계산하거나, 말단 노드에 해당하는 특징 벡터 공 간 내의 가장 먼 거리를 계산한다.

또한, 시그니처 길이 결정부(142)는 상기 계산한 말단 노드의 클러스터의 크기(여기서, 크기란 데이터 공간의 크기를 일컬음)와 사용자가 정의한 기준 클러스터 크기와 비교하여 시그니처의 길이를 결정하는데, 전체 데이터 공간 크기와 구성된 분산 색인 트리의 말단 노드 개수가 반영된 기준 클러스터 크기를 비교하여 시그니처의 길이를 결정한다. 즉, 상기 계산한 말단 노드의 클러스터의 크기와 전체 데이터 공간 크기를 상기 말단 노드의 개수로 분할한(나눈) 기준 클러스터 크기를 비교하여 시그니처의 길이를 결정한다. 이에 대한 구체적인 설명은 아래에서 상세히 설명하기로 한다.

이때, 결정되는 시그니처의 길이는 데이터의 분포에 따라 결정하며, 상기 기준 클러스터의 크기는 전체 특징 벡터의 크기, 말단 노드 개수, 각 말단 노드의 클러스터 크기 및 사용하고자 하는 비트 수의 목록 개수를 기반으로 결정한다.

분산색인 관리부(143)는 상기 객체 식별자와 N-차원의 특징벡터를 통해 상기 구축된 분산 색인 트리를 탐색하여 해당 노드에 객체 식별자 및 특징벡터의 저장을 요청하고, 상기 멀티미디어 객체(100)로부터 특징벡터를 추출하여 이를 기반으로 상기 분산 색인 트리를 탐색하여 유사한 값을 가지는 후보 말단 노드를 결정하여 유사검색을 요청한다.

고차원 색인관리기(150)는 상기 저장요청 입력시 도 4에 도시한 바와 같이 상기 구축된 분산 색인 트리 내 말단 노드별 특징벡터를 분할 및 분산 저장할 해당 컴퓨터 노드(410, 420)를 결정한 후 해당 노드에서 관리하는 특정 길이별 시그니처를 생성하여 상기 N-차원의 특징벡터와 매칭하여 결정한 컴퓨팅 노드(410, 420)에 저장한다.

따라서, 도 3에 도시한 바와 같이 분산 색인 트리의 말단 노드에 해당하는 클러스터의 크기가 전체 2차원의 데이터 공간을 말단 노드 개수 6으로 분할하였을 경우의 데이터 공간과 비교하여 같거나 큰 경우에 해당하는 트리의 말단 노드(330, 350, 360, 500)에는 차원당 2bit의 시그니처를 사용하고, 그렇지 않은 클러스터(230, 240)에 해당하는 트리의 말단 노드(380, 390)에서는 차원당 2bit보다 큰 k-bit로 표현되는 시그니처로 변환하여 고차원 데이터의 검색시 필터링 효과를 얻을 수 있다.

또한, 고차원 색인관리기(150)는 상기 결정한 후보 말단 노드에서 관리하는 시그니처를 생성하여 이를 기준으로 저장한 시그니처 파일을 순차 검색하여 후보 시그니처들을 결정한 후, 상기 후보 시그니처들의 특징벡터를 검색하여 최종 후보 특징벡터를 결정한다.

이때, 후보 말단 노드가 하나 이상인 경우에는 각 후보 말단 노드에서 결정한 최종 후보 특징벡터를 병합하여 최종적으로 특징벡터를 결정한다.

한편, 상기 고차원 색인관리기(150)는 고차원 색인기(140)의 상기 분산색인 생성부(141), 시그니처 길이 결정부(142) 및 분산색인 관리부(143)와 다른 컴퓨터 노드상에 위치한다.

또한, 상기 고차원 색인기(140)의 분산색인 생성부(141)와 분산색인 관리부(143)는 전체 데이터의 공간 크기 및 데이터 분포에 따라서 기능의 분리 및 병합이 가능하다.

이와 같이 구성한 본 발명의 실시예에 따른 동작과정을 첨부한 도면을 참조 하여 설명하면 다음과 같다.

도 5는 본 발명의 실시예에 따른 다중 길이 시그니처 파일 기반 분산 색인 검색을 위한 설정 과정을 보인 흐름도이고, 도 6은 본 발명의 실시예에 따른 다중 길이 시그니처 파일 기반 분산 색인의 검색 과정을 보인 흐름도이다.

먼저, 도 5를 참조하면, 멀티미디어 객체들로부터 N-차원의 특징벡터를 추출한다(S500).

이어서, 단계(S500)에서 추출된 N-차원의 특징벡터에서 임의 표본 추출을 통해 트리기반의 분산 색인을 구성한다(S510).

이후, 단계(S510)에서 구성한 분산 색인 트리의 말단 노드별 클러스터 크기를 계산하고(S520), 계산한 말단 노드별 클러스터 크기와 시그니처를 위한 비트수를 결정하는 기준 클러스터를 비교하여 말단 노드에 구축할 시그니처 길이를 결정한다(S530). 이때, 상기 기준 클러스터의 크기는 전체 특징 벡터의 크기, 말단 노드 개수, 각 말단 노드의 클러스터 크기 및 사용하고자 하는 비트 수의 목록 개수를 기반으로 결정한다.

즉, 예를 들어 각 기준 클러스터 크기의 목록과 각 기준 클러스터별 시그니처를 위한 차원당 비트수 목록(단, 비트수 목록 개수 = 클러스터 크기 목록 개수 + 1, 마지막 목록의 비트수는 가장 크게 설정)이 기 설정되고, 클러스터 크기와 이에 상응하는 차원당 비트 수는 서로 반비례한다고 가정하면, 말단 노드에 해당하는 특징벡터 공간의 중심점에서 클러스터 경계까지의 거리 또는 말단 노드에 해당하는 특징벡터의 공간 내 가장 먼 거리를 계산하고, 계산된 말단 노드의 클러스터 크기 와 내림차순(크기순)으로 정렬된 기준 클러스터 크기를 비교하여 말단 노드의 클러스터 크기보다 작은 첫 번째 기준 클러스터의 해당 비트수를 해당 말단 노드에서 사용할 시그니처의 차원당 비트수(길이)로 결정한다.

만약, 상기 시그니처를 위한 차원당 비트수 목록만이 설정된 경우에는 먼저, 상기 구축된 분산 색인 트리 내 말단 노드 개수(nodeN)와 전체 특징 벡터 공간의 크기(totalS)를 이용하여 데이터가 정규분포로 흩어져 있는 경우에 평균 클러스터의 평균크기(avgS)를 계산하고(avgS = totalS/nodeN(트리내 말단 노드 수)), 계산된 평균 클러스터의 크기와 오름차순으로 정렬된 시그니처를 위한 차원당 비트수 목록을 통해 각 비트수를 할당할 클러스터 크기를 계산하여 시그니처 길이로 결정한다.

이때, 평균 클러스터 크기(avgS) 보다 큰 경우에는 평균 클러스터 크기의 1배, 2배.. 등으로 더 작은 길이의 비트수를 할당하고(수학식 1), 평균 클러스터 크기(avgS) 보다 작은 경우에는 남은 비트 목록의 개수로 평균 클러스터 크기를 나눈 결과값의 1배, 2배... 순으로 더 작은 길이의 비트수를 할당한다(수학식 2).

여기서,

은 avagS 보다 큰 클러스터에 할당할 비트 목록 수이고, 1 <= i <= upperN, bitN(전체 비트 목록수)이다.

여기서,

은 avagS 보다 작은 클러스터에 할당할 비트 목록 수이고, upperN < i < bitN(전체 비트 목록수)이다.

이어서, 단계(S530)의 수행 후 분산 색인 트리의 말단 노드별 특징벡터를 분할 및 분산 저장할 컴퓨팅 노드를 결정한다(S540).

이후, 상기 컴퓨팅 노드에 분할 및 분산 저장시에 상기 결정한 길이별 시그니처를 생성하여(S550), N-차원의 특징벡터와 개별 매칭하여 저장한다(S560). 즉 상기 결정된 비트수(b)에 따라 각 차원을

개의 구간으로 분할하여 특징벡터에 해당하는 시그니처를 생성한다.

이때, 상기 결정한 컴퓨팅 노드는 비슷한 수의 데이터를 가지나, 해당하는 특징벡터의 데이터 범주의 크기가 다를 수 있기 때문에 분산 및 분할 저장된 특징벡터에 대하여 다른 길이의 시그니처를 병렬적으로 생성 및 저장함으로써, 작은 데이터 범주 내에 데이터가 군집되는 분산 색인 트리 내 말단 노드에 한하여 전체 데이터 공간이 더욱 세부 분할되어 필터링 효과가 높아지고, 전체 검색 성능이 향상된다.

한편, 도 6에 도시한 바와 같이 상기 분산 색인 검색을 위한 설정 과정이 완료되면, 상기 멀티미디어 객체(100)로부터 특징벡터를 추출하고(S600), 추출한 특징벡터에 따라 상기 분산 색인 트리를 탐색하여 유사한 값을 가지는 후보 말단 노드를 결정한다(S610). 이때, 결정되는 후보 단말 노드는 분산 색인 트리의 말단 노드 범위 결정에 따라 한 개 이상의 말단 노드가 후보 노드가 될 수 있다.

이어서, 단계(S610)에서 결정한 해당 후보 말단 노드에서 검색하고자 하는 특징벡터로부터 해당 길이의 시그니처를 생성한다(S620).

이후, 단계(S620)에서 생성한 시그니처를 기준으로 해당 후보 말단 노드에서 관리하는 상기 저장한 시그니처 파일을 순차 검색하여 후보 시그니처들을 결정한다(S630).

이어서, 상기 후보 말단 노드에서 상기 결정된 후보 시그니처에 대응되는 특징벡터를 검색하여 최종 후보 특징벡터를 결정한다(S640).

만약, 상기 한 개 이상의 후보 말단 노드가 결정되면 각 후보 말단 노드에서 결정된 최종 후보 특징벡터를 병합하여 최종 특징벡터를 결정한다(S650).

이상, 본 발명자에 의해서 이루어진 발명을 상기 실시예에 따라 구체적으로 설명하였지만, 본 발명은 상기 실시예에 한정되는 것은 아니고, 그 요지를 이탈하지 않는 범위에서 여러 가지로 변경 가능한 것은 물론이다.

도 1은 일반적인 2차원의 특징벡터 공간을 분할한 후 차원당 2bit의 시그니처로 표현한 도면.

도 2는 본 발명의 실시예에 따른 다중 길이 시그니처 파일 기반 분산 색인 시스템의 구성을 간략하게 보인 블록도.

도 3은 본 발명의 실시예에 따른 데이터 분포를 고려한 트리 기반의 분산 색인의 구조를 보인 도면.

도 4는 본 발명의 실시예에 따른 대용량의 고차원 데이터의 색인을 위한 트리 구조를 보인 도면.

도 5는 본 발명의 실시예에 따른 다중 길이 시그니처 파일 기반 분산 색인 검색을 위한 설정 과정을 보인 흐름도.

도 6은 본 발명의 실시예에 따른 다중 길이 시그니처 파일 기반 분산 색인의 검색 과정을 보인 흐름도.

* 도면의 주요 부분에 대한 부호의 설명 *

100 : 멀티미디어 객체 110 : 객체관리기

120 : 분산저장소 130 : 특징벡터 추출기

140 : 고차원 색인기 141 : 분산색인 생성부

142 : 시그니처 결정부 143 : 분산색인 관리부

144 : 고차원 색인관리부

Claims (20)

1. 멀티미디어 객체 및 상기 멀티미디어 객체의 객체 식별자로부터 N-차원의 특징벡터를 추출하는 특징벡터 추출수단,

   상기 멀티미디어 객체의 객체 식별자와 N-차원의 특징벡터에 따른 트리 기반의 분산 색인을 구성하고, 구성한 분산 색인 트리의 말단 노드의 클러스터 크기와 상기 N-차원의 특징 벡터의 공간 크기를 상기 말단 노드의 전체 개수로 나눈 평균 크기로 정의되는 기준 클러스터의 크기와 비교하여, 상기 말단 노드의 크기가 상기 기준 클러스터의 크기 이상인 경우, 제1 비트 수로 표현되는 시그니처의 길이를 결정하고, 상기 말단 노드의 크기가 상기 기준 클러스터의 크기보다 작은 경우, 상기 제1 비트 수보다 큰 제2 비트 수로 표현되는 시그니처의 길이를 결정하는 고차원 색인수단 및

   상기 결정한 시그니처의 길이를 반영한 말단 노드별 시그니처를 생성하고, 생성된 시그니처, 상기 N-차원의 특징 벡터 및 상기 객체 식별자를 해당 컴퓨팅 노드에 저장하는 고차원 색인관리수단을 포함하는 다중 길이 시그니처 파일 기반 분산 색인 시스템.
2. 제1항에 있어서,

   입력되는 상기 멀티미디어 객체로부터 객체 식별자를 추출하고, 멀티미디어 객체 정보를 저장하도록 관리하는 객체관리수단 및

   상기 멀티미디어 객체의 정보를 개별 저장하는 분산저장수단을 더 포함하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
3. 제1항에 있어서, 상기 기준 클러스터의 크기는

   전체 특징 벡터의 크기, 말단 노드 개수, 각 말단 노드의 클러스터 크기 및 사용하고자 하는 비트 수의 목록 개수를 기반으로 결정하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
4. 제1항에 있어서, 상기 고차원 색인수단은

   상기 고차원 색인관리수단에 의해 상기 해당 컴퓨팅 노드에 저장된 시그니처, 상기 N-차원의 특징 벡터 및 상기 객체 식별자를 포함하는 데이터의 검색시 멀티미디어 객체로부터 특징벡터를 추출하여 이를 기반으로 상기 분산 색인 트리를 탐색하여 유사한 값을 가지는 후보 말단 노드를 결정하여 유사검색을 상기 고차원 색인관리수단에게 요청하는 과정을 수행하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
5. 제1항에 있어서, 상기 고차원 색인수단은

   상기 N-차원의 특징벡터들 중에서 하나의 컴퓨터가 수용할 수 있는 개수의 N-차원 특징벡터들의 임의 표본을 추출하여 트리 기반의 분산 색인을 구성하는 분산색인 생성수단,

   상기 구성된 트리의 말단 노드에 해당하는 클러스터 크기를 계산한 후 사용자가 정의한 기준 클러스터 크기와 비교하여 시그니처의 길이를 결정하는 시그니처 길이 결정수단 및

   상기 객체 식별자와 N-차원의 특징벡터를 통해 상기 구성된 분산 색인 트리를 탐색하여 해당 컴퓨팅 노드에 객체 식별자 및 특징벡터의 저장을 상기 고차원 색인관리수단에게 요청하는 분산색인 관리수단을 포함하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
6. 삭제
7. 제5항에 있어서, 상기 시그니처 길이 결정수단은

   상기 구성된 분산 색인 트리 내 특정 말단 노드의 클러스터 크기를 계산시, 말단 모드에 해당하는 특징 벡터 공간의 중심점에서 크러스터 경계까지의 거리를 계산하거나, 말단 노드에 해당하는 특징 벡터 공간 내의 가장 먼 거리를 계산하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
8. 제5항에 있어서, 상기 시그니처 길이 결정수단은

   상기 시그니처의 길이 결정시 데이터의 분포에 따라 시그니처의 길이를 결정하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
9. 제5항에 있어서, 상기 시그니처 길이 결정수단은

   상기 계산된 말단 노드의 클러스터 크기와 비트 수의 크기가 내림차순으로 정렬된 기준 클러스터 크기를 비교하여 말단 노드의 클러스터 크기보다 작은 첫 번째 기준 클러스터의 해당 비트수를 해당 말단 노드에서 사용할 시그니처의 길이로 결정하거나,

   상기 클러스터의 평균크기를 계산하고, 계산된 평균 클러스터의 크기와 오름차순으로 정렬된 시그니처를 위한 차원당 비트수 목록을 통해 각 비트수를 할당할 클러스터 크기를 계산하여 시그니처 길이로 결정하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
10. 제5항에 있어서, 상기 분산색인 관리수단은

    검색요청시 상기 멀티미디어 객체로부터 특징벡터를 추출하여 이를 기반으로 상기 분산 색인 트리를 탐색하여 유사한 값을 가지는 후보 말단 노드를 결정하는 것을 더 수행하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
11. 제4항에 있어서, 상기 고차원 색인관리수단은

    검색 요청시 상기 결정한 후보 말단 노드에서 관리하는 시그니처를 생성하여 이를 기준으로 저장한 시그니처 파일을 순차 검색하여 후보 시그니처들을 결정한 후, 상기 후보 시그니처의 특징벡터를 검색하여 최종 후보 특징벡터를 결정하는 것을 수행하는 것인 다중 길이 시그니처 파일 기반 분산 색인 시스템.
12. 삭제
13. 삭제
14. 컴퓨팅 연산 처리가 각각 가능한 특징 벡터 추출수단, 고차원 색인수단 및 고차원 색인관리수단을 포함하는 다중 길이 시그니처 파일 기반 분산 색인 시스템을 이용한 다중 길이 시그니처 파일 기반 분산 색인 방법에 있어서,

    상기 특징 벡터 추출수단의 컴퓨팅 연산 처리에 의해 멀티미디어 객체들로부터 N-차원의 특징벡터를 추출하는 단계,

    상기 고차원 색인수단의 컴퓨팅 연산 처리에 의해 상기 추출된 N-차원의 특징벡터에서 임의 표본 추출을 통해 트리기반의 분산 색인을 구성하는 단계,

    상기 고차원 색인수단의 컴퓨팅 연산 처리에 의해 상기 구성한 분산 색인 트리의 말단 노드별 클러스터 크기를 계산하여 그에 따른 시그니처 길이를 결정하는 단계,

    상기 고차원 색인수단의 컴퓨팅 연산 처리에 의해 상기 분산 색인 트리의 말단 노드별 해당 컴퓨팅 노드를 결정하는 단계 및

    상기 고차원 색인 관리수단의 컴퓨팅 연산 처리에 의해 상기 컴퓨팅 노드에 결정한 길이를 갖는 시그니처를 생성하여 N-차원의 특징벡터와 개별 매칭하여 저장하는 단계를 포함하는 다중 길이 시그니처 파일 기반 분산 색인 방법.
15. 제14항에 있어서, 상기 시그니처 길이를 결정하는 단계는

    상기 클러스터 크기를 계산시, 말단 노드에 해당하는 특징 벡터 공간의 중심점에서 클러스터 경계까지의 거리를 계산하거나, 말단 노드에 해당하는 특징 벡터 공간 내의 가장 먼 거리를 계산하는 것인 다중 길이 시그니처 파일 기반 분산 색인 방법.
16. 제14항에 있어서, 상기 시그니처 길이를 결정하는 단계는

    전체 데이터 공간 크기와 구성된 분산 색인 트리의 말단 노드 개수가 반영된 기준 클러스터 크기를 비교하여 시그니처의 길이를 결정하는 것인 다중 길이 시그니처 파일 기반 분산 색인 방법.
17. 제16항에 있어서, 상기 기준 클러스터의 크기는

    전체 특징 벡터의 크기, 단말 노드 개수, 각 단말 노드의 클러스터 크기 및 사용하고자 하는 비트 수의 목록 개수를 기반으로 결정하는 것인 다중 길이 시그니처 파일 기반 분산 색인 방법.
18. 제16항에 있어서, 상기 시그니처 길이를 결정하는 단계는

    상기 시그니처의 길이 결정시 데이터의 분포에 따라 시그니처의 길이를 결정하는 것인 다중 길이 시그니처 파일 기반 분산 색인 방법.
19. 삭제
20. 삭제

Images