KR101994871B1 - 다차원 데이터에 대한 색인 생성 장치 - Google Patents

Abstract

데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 장치는 상기 다차원 데이터 공간에 데이터 벡터를 삽입하는 삽입부 및 상기 다차원 데이터 공간을 복수의 셀로 분할하고, 상기 데이터 벡터가 삽입됨에 따라 변화된 각 셀의 셀 밀도 및 기설정된 밀도 임계치에 기초하여 상기 분할된 복수의 셀 중 일부를 복수의 하위 레벨 셀로 분할하는 분할부를 포함한다. 상기 셀 밀도는 상기 다차원 데이터 공간을 구성하는 각 셀이 수용 가능한 데이터 백터의 수에 대한 상기 각 셀에 수용된 데이터 벡터의 비율이다.

Description

다차원 데이터에 대한 색인 생성 장치{APPARATUS FOR GENERATING INDEX TO MULTI DIMENSIONAL DATA}

본 발명은 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 장치에 관한 것이다.

교통 정보나 멀티미디어 데이터의 사용이 증가함에 따라 고차원 데이터에 대한 효율적인 색인과 검색 기법이 크게 요구되고 있다. 그러나 현재의 계층 구조의 다차원 색인 기법들은 고차원 데이터 공간에서 큰 성능을 보여주고 있지 못하고 있다. 최근에는 차원의 저주(dimensionality curse)를 해결하기 위해 차원을 줄이거나 근사 해를 구하는 등의 접근법이 시도되고 있다. 이와 관련하여, 선행기술인 한국등록특허 제 10-0518781호는 하이퍼사각형 기반의 다차원 데이터 세그먼테이션 장치, 클러스터링 장치 및 그 방법을 개시하고 있다.

그러나 차원의 저주를 해결하기 위해 차원을 줄이거나, 근사 해를 구하는 방법은 정확도가 떨어진다는 문제점을 가지고 있다. 정확도의 문제를 개선시키기 위해 VA-file, LPC-file 등과 같이 벡터 근사에 기반한 기법들이 개발되고 있으나, 이러한 기법은 검색 성능이 색인 파일의 크기에 큰 영향을 받고, 한 번에 큰 검색 공간을 줄일 수 있는 기존의 트리 형태의 계층적 색인 구조의 장점을 상실한다는 문제점을 가지고 있다.

따라서, 검색 성능이 색인 파일의 크기에 영향을 받지 않으면서도 높은 정확도를 갖춘 트리 형태의 계층적 색인 구조가 요구되고 있다.

고차원 데이터 집합에 대해 k-NN 질의를 효율적으로 수행하기 위해 밀도 기반 공간 분할과 그 분할 계층 구조를 반영하는 새로운 계층 색인 기법인 그리드셀-트리 기법을 제시하는 색인 생성 장치를 제공하고자 한다. 그리드셀-트리 기법을 이용하여 데이터 집합을 주의 깊게 분석하고, 이미지와 같은 고차원 데이터에 대해 계층 구조를 갖는 색인 기법을 적용할 수 있도록 하는 색인 생성 장치를 제공하고자 한다. 그리드셀-트리 기법을 이용한 위치 기반 서비스 및 다양한 고차원 데이터 검색를 제공하도록 하는 색인 생성 장치를 제공하고자 한다. 다만, 본 실시예가 이루고자 하는 기술적 과제는 상기된 바와 같은 기술적 과제들로 한정되지 않으며, 또 다른 기술적 과제들이 존재할 수 있다.

상술한 기술적 과제를 달성하기 위한 수단으로서, 본원 발명의 일 실시예에 따른 색인 생성 장치는 다차원 데이터 공간에 데이터 벡터를 삽입하는 삽입부 및 상기 다차원 데이터 공간을 복수의 셀로 분할하고, 상기 데이터 벡터가 삽입됨에 따라 변화된 각 셀의 셀 밀도 및 기설정된 밀도 임계치에 기초하여 상기 분할된 복수의 셀 중 일부를 복수의 하위 레벨 셀로 분할하는 분할부를 포함할 수 있다. 상기 셀 밀도는 상기 다차원 데이터 공간을 구성하는 각 셀이 수용 가능한 데이터 백터의 수에 대한 상기 각 셀에 수용된 데이터 벡터의 비율일 수 있다.

일 실시예에 따르면, 상기 분할부는 상기 분할된 복수의 셀 중 상기 셀 밀도가 상기 밀도 임계치를 초과하는 셀을 클러스터 셀로 생성하는 것일 수 있다. 상기 분할부는 상기 분할된 복수의 셀 중 상기 클러스터 셀을 복수의 하위 레벨 셀로 분할하는 것일 수 있다. 상기 분할부는 상기 클러스터 셀 이외의 영역에 수용된 데이터 벡터를 국외자(outliers)로 취급하는 것일 수 있다. 상기 분할부는 상기 다차원 데이터 공간의 차원수에 기초하여 상기 다차원 데이터 공간 또는 상기 복수의 셀을 차원의 중간에서 이진 분할하는 것일 수 있다.

일 실시예에 따르면, 상기 분할부에 의해 수행되는 계층적인 분할 방법에 기초하여 색인 트리 구조를 생성하는 색인 생성부를 더 포함하고, 상기 색인 트리 구조는 색인에 사용되는 디렉토리 노드와 상기 데이터 벡터를 저장하는데 사용되는 데이터 노드를 포함하는 것일 수 있다.

일 실시예에 따르면, 상기 디렉토리 노드는 하위 레벨의 내부 노드가 점유하는 영역에 대응하는 셀 벡터와 상기 하위 레벨의 내부 노드를 가리키는 포인터를 포함하는 내부 노드 및 내부 노드에 수용된 데이터 벡터에 대한 벡터 근사값과 상기 데이터 벡터가 저장되는 데이터 노드를 가리키는 포인터를 포함하는 리프 노드를 포함하는 것일 수 있다.

일 실시예에 따르면, 상기 색인 생성부는 상기 다차원 데이터 공간에 대응하여 기본 엔트리에 해당하는 내부 노드를 할당하고, 상기 내부 노드에 수용된 데이터 벡터에 대응하여 리프 노드를 할당하는 것일 수 있다.

일 실시예에 따르면, 상기 색인 생성부는 상기 클러스터 셀이 생성되는 경우, 상기 클러스터 셀에 대응하여 상기 내부 노드에 대한 하위 레벨로 신규 내부 노드를 할당하는 것일 수 있다.

일 실시예에 따르면, 상기 색인 생성부는 상기 클러스터 셀 이외의 셀에 데이터 벡터가 국외자로 삽입되어 상기 셀의 셀 밀도가 상기 밀도 임계치를 초과하는 경우, 상기 클러스터 셀 이외의 셀에 대응하여 상기 내부 노드에 같은 레벨의 신규 내부 노드를 연결하여 할당하는 것일 수 있다.

상술한 과제 해결 수단은 단지 예시적인 것으로서, 본 발명을 제한하려는 의도로 해석되지 않아야 한다. 상술한 예시적인 실시예 외에도, 도면 및 발명의 상세한 설명에 기재된 추가적인 실시예가 존재할 수 있다.

전술한 본 발명의 과제 해결 수단 중 어느 하나에 의하면, 고차원 데이터 집합에 대해 k-NN 질의를 효율적으로 수행하기 위해 밀도 기반 공간 분할과 그 분할 계층 구조를 반영하는 새로운 계층 색인 기법인 그리드셀-트리 기법을 제시하는 색인 생성 장치를 제공할 수 있다. 그리드셀-트리 기법을 이용하여 데이터 집합을 주의 깊게 분석하고, 이미지와 같은 고차원 데이터에 대해 계층 구조를 갖는 색인 기법을 적용할 수 있도록 하는 색인 생성 장치를 제공할 수 있다. 그리드셀-트리 기법을 이용한 위치 기반 서비스 및 다양한 고차원 데이터 검색를 제공하도록 하는 색인 생성 장치를 제공할 수 있다.

도 1은 본 발명의 일 실시예에 따른 색인 생성 장치의 구성도이다.
도 2a 및 도 2b는 본 발명의 일 실시예에 따른 다차원 데이터 공간을 복수의 셀로 분할하는 분할 기법을 도시한 예시적인 도면이다.
도 3a 내지 도 3c는 본 발명의 일 실시예에 따른 데이터 집합 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 형성하는 과정을 도시한 예시적인 도면이다.
도 4a 및 도 4b는 본 발명의 일 실시예에 따른 디렉터리 노드를 도시한 예시적인 도면이다.
도 5a 및 도 5b는 본 발명의 일 실시예에 따른 다차원 데이터 공간을 계층적으로 분할한 구조와 색인 트리 구조 간의 관계를 도시한 예시적인 도면이다.
도 6은 본 발명의 일 실시예에 따른 다차원 데이터 공간에서 리프 노드에 대한 하한치 및 상한치를 결정하는 과정을 도시한 예시적인 도면이다.
도 7은 본 발명의 일 실시예에 따른 색인 생성 장치에서 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 방법의 순서도이다.

아래에서는 첨부한 도면을 참조하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 본 발명의 실시예를 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다.

명세서 전체에서, 어떤 부분이 다른 부분과 "연결"되어 있다고 할 때, 이는 "직접적으로 연결"되어 있는 경우뿐 아니라, 그 중간에 다른 소자를 사이에 두고 "전기적으로 연결"되어 있는 경우도 포함한다. 또한 어떤 부분이 어떤 구성요소를 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있는 것을 의미하며, 하나 또는 그 이상의 다른 특징이나 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.

본 명세서에 있어서 '부(部)'란, 하드웨어에 의해 실현되는 유닛(unit), 소프트웨어에 의해 실현되는 유닛, 양방을 이용하여 실현되는 유닛을 포함한다. 또한, 1 개의 유닛이 2 개 이상의 하드웨어를 이용하여 실현되어도 되고, 2 개 이상의 유닛이 1 개의 하드웨어에 의해 실현되어도 된다.

본 명세서에 있어서 단말 또는 디바이스가 수행하는 것으로 기술된 동작이나 기능 중 일부는 해당 단말 또는 디바이스와 연결된 서버에서 대신 수행될 수도 있다. 이와 마찬가지로, 서버가 수행하는 것으로 기술된 동작이나 기능 중 일부도 해당 서버와 연결된 단말 또는 디바이스에서 수행될 수도 있다.

이하 첨부된 도면을 참고하여 본 발명의 일 실시예를 상세히 설명하기로 한다.

본 발명에서는 질의 처리 시에 검색 공간의 많은 부분을 잘라내는 다차원 색인 기법의 장점을 고차원 데이터 집합에 대해서도 적용할 수 있는 새로운 계층 색인 기법을 제안하고자 한다. 본 발명에서 제안하는 색인 기법은 실제 데이터의 적은 부분만 접근하는 벡터 근사 기법의 장점과 검색 공간의 많은 부분을 잘라내는 다차원 색인 기법의 장점을 결합한 것으로, 데이터 집합을 분석하고, 그에 따라 데이터 공간을 분할하고, 분할된 계층 구조에 기반하여 계층적으로 색인을 형성할 수 있다.

예를 들어, 교통 데이터베이스는 지도 상의 객체를 종종 d 개의 수치적 특성으로 표현하고, 그 특성 벡터와 유사성 척도(similarity measure)를 이용하여 저장하고 검색한다. 여기서, 특성 벡터는 d-차원 벡터 공간 상의 한 점으로 표현될 수 있고, 유사성 척도는 그 공간 내에서 거리의 척도로 나타내어질 수 있다.

이러한 시스템에서 중요한 문제는 주어진 질의 객체와 가장 근접한 k 개의 객체를 찾는 것이다. 이 문제는 먼저 질의 객체를 대응하는 특성 벡터로 바꾸고, 그 벡터에 대한 k 개의 최근접 이웃(nearest neighbors: NNs)을 찾음으로써 해결할 수 있다. 여기서, 기본 문제는 k 개의 NNs(k -NN문제)을 어떻게 효율적으로 찾는가 하는 것이다.

저차원 또는 중차원(예를 들어, 10차원 이하)의 특성 벡터를 갖는 응용에서는, R*-tree, X-tree, HG-tree, SR-tree와 같은 기존의 다차원 색인 기법(multidimensional indexing methods: MIMs)을 이용하여 이 문제를 해결할 수 있었다. 그러나 예를 들어, 100 차원 이상의, 고차원 특성 벡터를 갖는 응용에서는 효과적인 해결책이 제시되지 않고 있다.

고차원에서는 데이터 공간의 분할에 기초하는 기존의 MIMs의 성능은 질의 객체와 전체 데이터베이스 객체를 하나씩 비교하는 순차 탐색보다 성능이 더 나빠지므로, 주된 문제인 차원의 저주 (dimensionality curse: 차원이 높아짐에 따라 검색 성능이 급격히 하락하는 현상)를 해결하는 것이다. 따라서, 데이터베이스 시스템에서 k-NN 문제를 해결하기 위한 다양한 접근법이 연구되어 왔다.

본 발명에서는, 차원의 저주를 해결하는 새로운 접근법으로서 고차원 데이터 집합에서 클러스터(clusters)와 국외자(outliers)를 구분해낸 후, 데이터 집합의 분할을 클러스터 부분에 집중하고, 이 클러스터들을 계층 구조로 구성함으로써 고차원 데이터 집합에 대해서도 트리 형태의 계층적 색인 구조를 형성할 수 있는 기법을 제시하고자 한다.

도 1은 본 발명의 일 실시예에 따른 색인 생성 장치의 구성도이다. 도 1을 참조하면, 색인 생성 장치(100)는 삽입부(110), 분할부(120) 및 색인 생성부(130)를 포함할 수 있다.

삽입부(110)는 다차원 데이터 공간에 데이터 벡터를 삽입할 수 있다.

분할부(120)는 다차원 데이터 공간을 복수의 셀로 분할할 수 있다. 예를 들어, 분할부(120)는 데이터 공간을 서로 겹치지 않는 사각형 셀(cell)로 분할할 수 있다. 이 때, 분할부(120)는 각 셀에 놓이는 벡터의 수를 계산하기 위해 각 차원을 같은 수의 동일한 길이의 간격으로 분할할 수 있다. 다차원 데이터 공간을 복수의 셀로 분할하는 기법을 도 2a 및 도 2b를 참조하여 상세히 설명하도록 한다.

도 2a 및 도 2b는 본 발명의 일 실시예에 따른 다차원 데이터 공간을 복수의 셀로 분할하는 분할 전략을 도시한 예시적인 도면이다. 2차원 공간과 같은 다차원 데이터 공간에 균형 분할 기법 또는 밀도 기반 분할 기법을 적용할 수 있다. 여기서, 질의 벡터 'q'는 'x'(200)로 표시되고, 한 클러스터는 그 셀에 최소 3개의 벡터를 포함할 수 있다.

도 2a는 종래의 균형 분할 기법을 도시한 예시적인 도면이다. 도 2a를 참조하면, 다차원 공간에서 균형 분할 기법을 이용하여 데이터 공간을 균형있게 분할하고자 할 때, 고차원에서는 경계 사각형의 크기가 커서 큰 검색 구인 'k-NN^sphere'(210)가 모든 분할과 교차할 수 있다. 그러나 균형 분할 기법은 고차원 공간에서 각 분할에 대해 큰 경계 사각형(bounding rectangles)를 생성하여 검색 시에 해당 부분을 잘라내기 어렵고, 차원이 높아질수록 각 차원에서 공간을 분할할 기회가 줄어들어 경계 사각형의 크기가 더 커지는 문제점을 가지고 있다.

도 2b는 본 발명의 일 실시예에 따른 밀도 기반 분할 기법을 도시한 예시적인 도면이다. 도 2b를 참조하면, 밀도 기반 분할 기법은 불균등 분할 기법으로, 다차원 공간에서 밀도 기반 분할 기법을 이용하여 데이터 공간을 분할하고자 할 때, 클러스터가 점유하는 작은 영역이 검색 구인 'k-NN^sphere'(220)가 교차하지 않을 수 있다. 또한, 밀도 기반 분할 기법의 경우, 차원의 수만큼 데이터 공간을 분할하므로 전체 데이터 공간에 대한 경계 사각형의 상대적인 크기가 줄어드는 특징을 가짐으로써, 균등 분할 기법 보다 개선된 분할 효과를 제공할 수 있다. 즉, 본원 발명에서는 색인 구조의 하나의 노드에 한 특정 부분 공간에서 생성된 모든 국외자를 모으고, 검색 공간과 클러스터들이 교차하는 확률을 줄이기 위해 공간 분할을 클러스터들에만 집중할 수 있다.

다시 도 1로 돌아와서, 분할부(120)는 데이터 벡터가 삽입됨에 따라 변화된 각 셀의 셀 밀도 및 기설정된 밀도 임계치에 기초하여 분할된 복수의 셀 중 일부를 복수의 하위 레벨 셀로 분할할 수 있다. 예를 들어, 분할부(120)는 분할된 복수의 셀 중 셀 밀도가 밀도 임계치를 초과하는 셀을 클러스터 셀로 생성하고, 분할된 복수의 셀 중 클러스터 셀을 복수의 하위 레벨 셀로 분할할 수 있다. 이 때, 분할부(120)는 클러스터 셀 이외의 영역에 수용된 데이터 벡터를 국외자(outliers)로 취급할 수 있다. 여기서, 셀 밀도는 다차원 데이터 공간을 구성하는 각 셀이 수용 가능한 데이터 벡터의 수에 대한 각 셀에 수용된 데이터 벡터의 비율일 수 있다.

분할부(120)는 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할할 수 있다. 즉, 분할부(120)는 데이터 집합의 밀도를 근사하기 위해 데이터 공간을 서로 겹치지 않는 사각형 셀(cell)로 분할하고, 각 셀에 놓이는 벡터의 수를 계산할 수 있다. 이렇게 하기 위해 각 차원을 같은 수의 동일한 길이의 간격으로 분할할 수 있다. 여기서, 각 셀이 같은 데이터 크기를 가짐으로써, 각 셀 내부에 놓이는 벡터의 수가 그 셀의 밀도를 근사하는데 사용될 수 있다.

분할부(120)는 다차원 데이터 공간의 차원수에 기초하여 다차원 데이터 공간 또는 복수의 셀을 차원의 중간에서 이진 분할(예를 들어, 2^d)할 수 있다.

여기서, 데이터 공간에서의 한 영역은 물리적으로 디스크의 한 페이지로 사상되고, 한 디스크 페이지가 수용할 수 있는 객체의 최대수를 나타내는 수로 'P'가 규정될 수 있다. 여기서, 'P'는 페이지 용량을 나타내는 것일 수 있다. 예를 들어, 한 페이지에 삽입된 데이터의 수가 'P'를 초과하면, 그 페이지를 두 개로 분할할 수 있다. 특정 셀의 밀도가 특정 밀도 임계치 'τ'를 초과하는 경우, 특정 셀을 조밀하고, 그렇지 않은 경우를 희박하다는 의미로 나타낼 수 있다. 여기서, 조밀한 셀을 클러스터(cluster)라고 하고, 희박한 셀에 포함된 데이터 벡터들을 국외자로 칭할 수 있다. 예를 들어, 밀도 임계치를 페이지 용량의 절반보다 크게 결정하면, 객체가 삽입되어 한 영역을 분할할 때 최대로 하나의 클러스터만 생성될 수 있다.

이러한 과정을 통해, 본 발명에서는 데이터 공간의 분할 시, 클러스터를 규정하고, 국외자들에 의해 점유된 부분의 공간을 검색 시에 잘라낼 수 없으므로, 분할을 클러스터들의 부분 공간에 집중하고, 같은 분할 레벨에 존재하는 국외자를 처리하는 것을 목적으로 하고자 한다. 분할부에서 다차원 데이터 공간을 계층적으로 분할하는 과정과 관련하여 도 3a 내지 도 3c를 통해 상세히 설명하도록 한다.

도 3a 내지 도 3c는 본 발명의 일 실시예에 따른 데이터 집합 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 형성하는 과정을 도시한 예시적인 도면이다.

먼저, 색인 구조를 형성하기 위한 계층 분할과 관련하여, 본원 발명은 데이터 삽입에 따라 한 클러스터 또는 희박 셀(예를 들어, 밀도 임계치를 초과 하지 않는 셀)에 해당하는 디스크 페이지가 범람할 때마다 그 데이터 공간(예를 들어, 범람 노드라고 할 수 있다)을 한번에 모든 차원의 중앙에서 분할할 수 있다. 또한, 본원 발명은 분할한 공간에서 클러스터와 국외자를 규정하고 데이터 벡터를 위치에 따라 해당 노드에 분산시킬 수 있다. 만약 분할로 인해 새로운 클러스터가 생성되면 그것을 분할 계층 구조에서 범람 노드의 하위 레벨 노드로 만들 수 있다. 새로운 클러스터가 생성되지않으면, 단순히 범람 노드에서 같은 레벨의 새로운 노드를 연결하여 할당하고, 이에 범람 객체를 삽입할 수 있다.

도 3a는 본 발명의 일 실시예에 따른 전체 데이터 공간의 초기 상태를 도시한 예시적인 도면이다. 도 3a를 참조하면, 데이터베이스가 전체 데이터 공간(300)에서 4개의 벡터를 포함하는 초기 상태를 나타낸 것으로, 데이터 공간은 4개의 셀로 기분할 되어 있는 것일 수 있다. 여기서, 밀도 임계치 τ는 3/4일 수 있다. 즉, 페이지 용량은 4이고, 한 클러스터는 최소 3개의 데이터 벡터를 포함하고, 3개보다 적은 수의 벡터를 포함하는 셀에 위치한 벡터들은 국외자로 취급할 수 있다.

예를 들어, 색인 구조는 초기 상태의 전체 데이터 공간과 대응하여 하나의 내부 노드(320)와 하나의 리프 노드A(310)가 존재하도록 형성될 수 있다. 리프 노드 A(310)는 희박 셀에 존재하는 4개의 벡터(국외자)에 해당하는 벡터 근사값을 포함할 수 있다. 내부 노드(320)의 셀 벡터는 전체 데이터 공간을 나타내는 것일 수 있으며, 기호 '-'는 주어진 하나의 셀에서 한 차원에 대한 전체 도메인을 나타내는 것일 수 있다.

도 3b는 본 발명의 일 실시예에 따른 클러스터 셀을 생성하는 과정을 설명하기 위한 예시적인 도면이다. 도 3b를 참조하면, 새로운 벡터(335)가 첨가됨으로써, 최초의 클러스터 셀(330)이 생성될 수 있고, 생성된 최초의 클러스터 셀(330)과 대응하여 .기존의 내부 노드(320)에 같은 레벨의 내부 노드(350)를 연결하여 할당할 수 있다. 예를 들어, 셀 밀도가 밀도 임계치를 초과하는 셀을 클러스터 셀(330)로 생성한 후, 클러스터 셀(330)을 2²개의 셀로 분할하여 복수의 하위 레벨 셀로 분할할 수 있다. 이 때, 새로운 리프 노드 B(340)는 내부 노드(350)에 대응하여 셀 벡터가 (0,0)인 클러스터를 나타내고, 클러스터 셀(330) 이외의 영역에 수용된 국외자들은 셀 벡터가 (-,-)인 리프 노드 A(310)에 재분산될 수 있다.

도 3c는 본 발명의 일 실시예에 따른 분할이 완료된 데이터 공간을 도시한 예시적인 도면이다. 도 3c를 참조하면, 기존의 클러스터 셀(330)이 분할된 하위 레벨 셀에 새로운 벡터가 첨가됨으로써, 새로운 클러스터 셀(360)이 생성될 수 있 고, 생성된 클러스터 셀(360)과 대응하여 기존의 클러스터 셀(330)과 대응하는 내부 노드(350)에 대한 하부 레벨의 신규 내부 노드(390)를 할당할 수 있다. 예를 들어, 셀 밀도가 밀도 임계치를 초과하는 셀을 클러스터 셀(360)로 생성한 후, 클러스터 셀(360)을 2²개의 셀로 분할하여 복수의 하위 레벨 셀로 분할할 수 있다. 이 때, 새로운 리프 노드 C(370)는 내부 노드(390)에 대응하여 셀 벡터가 (0,0)인 클러스터를 나타내고, 클러스터 셀(330) 중 클러스터 셀(360) 이외의 영역에 수용된 국외자들은 내부 노드(390)와 같은 레벨인 신규 내부 노드(380)와 대응하여 셀 벡터가 (-,-)인 리프 노드 B(340)에 재분산될 수 있다.

다시 도 1로 돌아와서, 색인 생성부(130)는 분할부(120)에 의해 수행되는 계층적인 분할 방법에 기초하여 색인 트리 구조를 생성할 수 있다. 색인 트리 구조는 색인에 사용되는 디렉토리 노드와 데이터 벡터를 저장하는데 사용되는 데이터 노드를 포함할 수 있다. 디렉토리 노드는 하위 레벨의 내부 노드가 점유하는 영역에 대응하는 셀 벡터와 하위 레벨의 내부 노드를 가리키는 포인터를 포함하는 내부 노드 및 내부 노드에 수용된 데이터 벡터에 대한 벡터 근사값과 데이터 벡터가 저장되는 데이터 노드를 가리키는 포인터를 포함하는 리프 노드를 포함할 수 있다. 각 노드는 데이터 공간의 한 영역에 해당되며, 한 디스크의 페이지로 사상되는 것일 수 있다.

이하에서는 디렉토리 노드를 도 4a 및 도 4b를 참조하여 상세히 설명하도록 한다. 도 4a 및 도 4b는 본 발명의 일 실시예에 따른 디렉터리 노드를 도시한 예시적인 도면이다. 디렉토리 노드는 내부 노드 및 리프 노드를 포함할 수 있다.

도 4a는 본 발명의 일 실시예에 따른 내부 노드 구조를 도시한 예시적인 도면이다. 도 4a를 참조하면, 내부 노드의 요소는 하위 레벨 노드가 점유하는 영역에 대응하는 셀 벡터, 하위 레벨 노드(예를 들어, 자식1 ~ 자식i)를 가리키는 포인터를 포함할 수 있다.

도 4b는 본 발명의 일 실시예에 따른 리프 노드 구조를 도시한 예시적인 도면이다. 도 4b를 참조하면, 리프 노드의 요소는 실제 벡터에 대한 LPC-file 근사 <r, θ>와 실제 벡터 'p'가 저장되는 데이터 노드(예를 들어, 객체 1 ~ 객체 i)를 가리키는 포인터를 포함할 수 있다. 여기서, r은 벡터 p가 위치한 셀의 원점 O와 벡터 p간의 거리로 계산되고, θ는 벡터 p와 셀의 원점에서 반대편 모서리까지의 대각선 간의 각도로 계산되는 것일 수 있다.

다시 도 1로 돌아와서, 색인 생성부(130)는 다차원 데이터 공간에 대응하여 기본 엔트리에 해당하는 내부 노드를 할당하고, 내부 노드에 수용된 데이터 벡터에 대응하여 리프 노드를 할당할 수 있다.

색인 생성부(130)는 클러스터 셀이 생성되는 경우, 클러스터 셀에 대응하여 내부 노드에 대한 하위 레벨로 신규 내부 노드를 할당할 수 있다. 클러스터 셀은 예를 들어, 같은 길이의 변을 갖는 초사각형(hyper-rectangle)인 것일 수 있으며, 클러스터 셀에 해당하는 노드는 클러스터 노드로 표현될 수 있다.

색인 생성부(130)는 클러스터 셀 이외의 셀에 데이터 벡터가 국외자로 삽입되어 셀의 셀 밀도가 밀도 임계치를 초과하는 경우, 클러스터 셀 이외의 셀에 대응하여 내부 노드에 같은 레벨의 신규 내부 노드를 연결하여 할당할 수 있다. 여기서, 신규 내부 노드는 하위 레벨 노드가 될 수 있다. 국외자 영역은 원래 영역에서 클러스터에 해당하는 영역들을 제외하고 남은 영역으로, 국외자 영역에 대한 셀 벡터는 원래 영역의 셀 벡터로 표현되는 것일 수 있으며, 국외자에 해당하는 노드는 국외자 노드로 표현될 수 있다. 또한, 국외자의 삽입으로 해당 노드가 범람하는 경우, 새로운 노드를 할당하고, 해당 노드를 단순히 범람 노드에 연결하여 할당할 수 있다. 반면에, 클러스터 벡터의 삽입으로 클러스터 노드가 범람하면 색인 트리의 히위 레벨 노드로 새로운 노드를 할당할 수 있다. 즉, 본원 발명에 따르면, 공간 분할 계층 구조와 그것을 나타내는 색인 트리 계층 구조 간의 일대 일 대응관계가 존재할 수 있다.

도 5a 및 도 5b는 본 발명의 일 실시예에 따른 다차원 데이터 공간을 계층적으로 분할한 구조와 색인 트리 구조 간의 관계를 도시한 예시적인 도면이다.

도 5a는 본 발명의 일 실시예에 따른 데이터 공간의 비균등 분할을 도시한 예시적인 도면이다. 도 5a를 참조하면, 차원당 2비트를 사용한 2차원 데이터 공간(500)을 4x4개의 셀로 기분할한 것일 수 있다. 여기서, 밀도 임계치는 τ는 3/P일 수 있으며, P는 리프 노드의 팬아웃을 나타내는 것일 수 있다.

예를 들어, 셀 C2(510)은 클러스터 C4(511)와 국외자 영역을 포함할 수 있다. 또한, 셀 C4(511)는 클러스터 C5(512)와 국외자 영역을 포함할 수 있다.

다른 예를 들어, 셀 C1(520)은 클러스터 C3(521)와 국외자 영역을 포함할 수 있다.

데이터 공간 상의 데이터 점들은 <c_i, r, θ>로 근사되고, LPC(Local Polar Coordinate) 정보에 따라 <r, θ>는 리프 노드로 표현되고, 셀 벡터 c_i는 리프 노드의 내부 부모 노드의 색인 엔트리로 표현될 수 있다. 여기서, 상위 노드의 색인 엔트리에 위치한 셀 벡터는 하위 노드의 셀 벡터들의 공통 접두사로 이용될 수 있다.

도 5b는 본 발명의 일 실시예에 따른 색인 트리 구조를 도시한 예시적인 도면이다. 도 5b를 참조하면, 루트 디렉토리 노드(550)는 3개의 엔트리를 가지고 있을 수 있다. 엔트리는 예를 들어, (01, 01), (00, 11), (-, -)를 포함할 수 있다.

예를 들어, 도 5a의 셀 C3(521)의 셀 벡터인 (010, 011)은 상위 노드의 인덱스 엔트리의 셀 벡터(551)인 (01, 01)을 자신의 셀 벡터(552)인 (0, 1)의 앞에 붙여 얻을 수 있다. 즉, 하위 노드의 셀 벡터는 공통 접두사를 사용하여 나타낼 수 있으며, 본 발명에서 제시하고자 하는 색인 트리 구조는 내부 노드의 팬아웃을 높일 수 있고 디스크 접근 횟수를 줄일 수 있다는 장점을 제공한다.

한편, 도 5b에서는 셀 C5(512)의 셀 벡터(553)를 (00,01)로 표현하였다, 상술된 색인 구조의 기본 구성에 따르면, 셀 C5(512)의 셀 벡터는 셀 C4(511)의 셀 벡터(553)에 대한 하위 레벨 셀 벡터로서 (0,1)로 표현할 수 있다. 하지만, 이 경우는 해당 노드가 하위레벨로 할당됨에 따라 발생하는 성능 저하를 예방하기 위하여 C5(510)의 셀 벡터(553)를 셀 C4(511)의 셀 벡터(554)와 같은 레벨에 위치하는 셀벡터 (00,01)로 표현하였다.

색인 생성 장치(100)는 색인 생성을 위해 삽입(insert) 알고리즘을 이용할 수 있다. 색인 생성 장치(100)는 삽입 알고리즘을 이용하여 색인 구조를 하향식으로 따라 가면서, 새로운 객체를 수용할 적합한 리프 노드를 탐색할 수 있다. 이 때, 해당 리프 노드가 임계치를 초과한 경우, 분할이 일어날 수 있다. 본 발명에서 제시하고자 하는 색인 구조는 상향식으로 성장하지 않는 특징을 가지고 있다.

예를 들어, 한 노드 N의 임계치 초과는 N과 같거나 하위 레벨에서 새로운 노드 N'를 할당하고, 엔트리들을 클러스터와 국외자로 구별하여 두 노드에 분산시키고, 필요에 따라 디렉토리 엔트리를 부모 노드에 첨가하여 처리할 수 있다.

색인 생성 장치(100)가 색인 생성을 위해 이용하는 삽입 알고리즘은 다음과 같다.

Algorithm k_ NN _Query(Query q , Integer k )

// MAX: 데이터베이스에 있는 임의의 두 점 간의 최대 거리 //

// NN: 최근접 이웃 //

// k-NN: k-번째 최근접 이웃 //

// oid(x): x의 객체 식별자 //

// dist(x): x와 q 간의 거리 //

// dmin(x): x와 q 간의 dmin //

// bl _list: 분기 리스트를 저장하는 최소 히프(heap) //

// cand _list: 후보 집합을 저장하는 최소 히프 //

// bl: bl _list에 있는 요소를 나타내는 변수로써 객체 번호와 dmin, dmax로 구성된다. //

// knn: 요소 [oid(x), dist(x)]를 갖는 크기 k의 배열 //

// knn 에 대한 삽입은 크기 순으로 이루어진다. 즉, 새 요소 x는 dist(x) 순으로 knn 의 올바른 위치에 삽입된다. //

1. for i := 0 to k do {

knn[i].dist := MAX.

}

2. k-NNdist := MAX.

3. bl .node_no := Root; // Root는 GC-트리의 루트이다.

// stage 1

4. do {

next_node := ReadNodeFromGCtree(bl .node_no);

k_ NN _Search(next_node, q, k);

} while (GetFromBranchList(&bl) NULL);

// stage 2

5. for i := 0 to k do {

knn[i].dist := MAX;

}

6. while (cand _list 에서 후보 O를 읽고 dmin(O) ≤ k-NNdist 이면) do {

6.1. O에 해당하는 벡터 p 를 읽는다.

6.2. If (dist ( p ) < k-NNdist) { 11

6.2.1. NN [oid(O), dist ( p )]을 into knn.에 삽입한다.

6.2.2. k-NNdist := dist(k-NN in knn).

}

}

}

Algorithm k_ NN _Search(Node N , Query q , Integer k )

{

1. 만약 N 이 리프 노드이면 {

N 에 있는 모든 엔트리 Ni 에 대해 {

1.1. Ni 와 질의 객체 q 간의 dmin과dmax 를 계산한다.

1.2. If (dmin ≤ k-NNdist) {

1.2.1. [oid(Ni), dmin, dmax]를 cand _list 에 삽입한다.

1.2.2. If (dmax < k-NNdist) {

NN [oid(Ni), dmax]를 knn에 삽입한다.

k-NNdist := dist(k-NN in knn).

}

}

}

}

2. 그렇지 않으면 {

N 에 있는 모든 엔트리 Ni 에 대해 {

2.1. Ni 와 질의 객체 q 간의 dmin과dmax 를 계산한다.

2.2. [Ni, dmin]를 최소-heap bl _list.에 삽입한다.

2.3. If (dmax < k-NNdist) {

NN [ptr(Ni), dmax]를 knn에 삽입한다.

k-NNdist := dist(k-NN in knn).

}

}

}

}

색인 삽입 장치(100)는 첫번째 단계에서, 알고리즘 k_NN_Search를 통해 GC-트리의 최상위 레벨의 분기(branch)들을 검사하고, 각 분기에 대한 d_min과 d_max를 계산한 후, d_min의 오름차순으로 각 분기를 순회할 수 있다. K_NN 탐색의 잘라내는(pruning) 원칙은 동적이므로, 탐색반경은 q와 그것의 k번째 NN 간의 거리 k_NN^dist를 방문하는 노드의 순서가 탐색 성능에 영향을 미친다. 자신의 d_min이 k-NN^dist를 초과하는 객체는 더 나은 k개의 후보를 이미 선정한 상태이므로 안전하게 삭제를 할 수 있다. 여기서, 첫번째 단계의 끝에서 cand_list는 탐색 후보들의 집합을 포함할 수 있다.

색인 삽입 장치(100)는 두 번째 단계에서, 벡터 근사 접근법처럼 d_min의 오름차순대로 실제 벡터를 방문하여 후보 집합들을 정제하고, 최후로 k개의 최근접 벡터를 찾을 수 있다. 여기서, 함수 ReadNodeFromGCtree는 입력 변수로 제공되는 노드 번호에 대응하는 디스크 페이지를 읽고, 함수 GetFromBranchList는 bl_list로부터 가장 작은 d_min를 갖는 분기 리스트 요소를 변수 bl로 가져올 수 있다.

도 7은 본 발명의 일 실시예에 따른 색인 생성 장치에서 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 방법의 순서도이다. 도 7에 도시된 실시예에 따른 색인 생성 장치(100)에 의해 수행되는 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 방법은 도 1 내지 도 6에 도시된 실시예에 따라 시계열적으로 처리되는 단계들을 포함한다.

단계 S710에서 색인 생성 장치(100)는 다차원 데이터 공간에 데이터 벡터를 삽입할 수 있다.

단계 S720에서 색인 생성 장치(100)는 다차원 데이터 공간을 복수의 셀로 분할할 수 있다.

단계 S730에서 색인 생성 장치(100)는 데이터 벡터가 삽입됨에 따라 변화된 각 셀의 셀 밀도 및 기설정된 밀도 임계치에 기초하여 분할된 복수의 셀 중 일부를 복수의 하위 레벨 셀로 분할할 수 있다.

단계 S740에서 색인 생성 장치(100)는 계층적인 분할 방법에 기초하여 색인 트리 구조를 생성할 수 있다.

상술한 설명에서, 단계 S710 내지 S740은 본 발명의 구현예에 따라서, 추가적인 단계들로 더 분할되거나, 더 적은 단계들로 조합될 수 있다. 또한, 일부 단계는 필요에 따라 생략될 수도 있고, 단계 간의 순서가 전환될 수도 있다.

도 1 내지 도 7을 통해 설명된 색인 생성 장치에서 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 방법은 컴퓨터에 의해 실행되는 매체에 저장된 컴퓨터 프로그램 또는 컴퓨터에 의해 실행 가능한 명령어를 포함하는 기록 매체의 형태로도 구현될 수 있다. 또한, 1 내지 도 7을 통해 설명된 색인 생성 장치에서 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 방법은 컴퓨터에 의해 실행되는 매체에 저장된 컴퓨터 프로그램의 형태로도 구현될 수 있다.

컴퓨터 판독 가능 매체는 컴퓨터에 의해 액세스될 수 있는 임의의 가용 매체일 수 있고, 휘발성 및 비휘발성 매체, 분리형 및 비분리형 매체를 모두 포함한다. 또한, 컴퓨터 판독가능 매체는 컴퓨터 저장 매체를 포함할 수 있다. 컴퓨터 저장 매체는 컴퓨터 판독가능 명령어, 데이터 구조, 프로그램 모듈 또는 기타 데이터와 같은 정보의 저장을 위한 임의의 방법 또는 기술로 구현된 휘발성 및 비휘발성, 분리형 및 비분리형 매체를 모두 포함한다.

전술한 본 발명의 설명은 예시를 위한 것이며, 본 발명이 속하는 기술분야의 통상의 지식을 가진 자는 본 발명의 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 쉽게 변형이 가능하다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다. 예를 들어, 단일형으로 설명되어 있는 각 구성 요소는 분산되어 실시될 수도 있으며, 마찬가지로 분산된 것으로 설명되어 있는 구성 요소들도 결합된 형태로 실시될 수 있다.

본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미 및 범위 그리고 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어야 한다.

100: 색인 생성 장치
110: 삽입부
120: 분할부
130: 색인 생성부

Claims (10)

1. 데이터 집합의 밀도에 기초하여 다차원 데이터 공간을 계층적으로 분할하여 색인 구조를 생성하는 장치에 있어서,
   상기 다차원 데이터 공간에 데이터 벡터를 삽입하는 삽입부; 및
   상기 다차원 데이터 공간을 복수의 셀로 분할하고, 상기 데이터 벡터가 삽입됨에 따라 변화된 각 셀의 셀 밀도 및 기설정된 밀도 임계치에 기초하여 상기 분할된 복수의 셀 중 일부를 복수의 하위 레벨 셀로 분할하는 분할부
   를 포함하고,
   상기 셀 밀도는 상기 다차원 데이터 공간을 구성하는 각 셀이 수용 가능한 데이터 백터의 수에 대한 상기 각 셀에 수용된 데이터 벡터의 비율인 것이되,
   상기 분할부에 의해 수행되는 계층적인 분할 방법에 기초하여 색인 트리 구조를 생성하는 색인 생성부를 더 포함하고,
   상기 색인 트리 구조는 색인에 사용되는 디렉토리 노드와 상기 데이터 벡터를 저장하는데 사용되는 데이터 노드를 포함하고,
   상기 디렉토리 노드는 하위 레벨의 내부 노드가 점유하는 영역에 대응하는 셀 벡터와 상기 하위 레벨의 내부 노드를 가리키는 포인터를 포함하는 내부 노드 및 내부 노드에 수용된 데이터 벡터에 대한 벡터 근사값과 상기 데이터 벡터가 저장되는 데이터 노드를 가리키는 포인터를 포함하는 리프 노드를 포함하는 것이되,
   상기 디렉토리 노드의 셀 벡터는 상기 하위 레벨의 내부 노드의 셀 벡터들의 공통 접두사로 이용되는 것인, 색인 생성 장치.
   
2. 제 1 항에 있어서,
   상기 분할부는 상기 분할된 복수의 셀 중 상기 셀 밀도가 상기 밀도 임계치를 초과하는 셀을 클러스터 셀로 생성하는 것인, 색인 생성 장치.
   
3. 제 2 항에 있어서,
   상기 분할부는 상기 분할된 복수의 셀 중 상기 클러스터 셀을 복수의 하위 레벨 셀로 분할하는 것인, 색인 생성 장치.
   
4. 제 3 항에 있어서,
   상기 분할부는 상기 클러스터 셀 이외의 영역에 수용된 데이터 벡터를 국외자(outliers)로 취급하는 것인, 색인 생성 장치.
   
5. 제 1 항에 있어서,
   상기 분할부는 상기 다차원 데이터 공간의 차원수에 기초하여 상기 다차원 데이터 공간 또는 상기 복수의 셀을 차원의 중간에서 이진 분할하는 것인, 색인 생성 장치.
   
6. 삭제
7. 삭제
8. 제 2 항에 있어서,
   상기 색인 생성부는 상기 다차원 데이터 공간에 대응하여 기본 엔트리에 해당하는 내부 노드를 할당하고, 상기 내부 노드에 수용된 데이터 벡터에 대응하여 리프 노드를 할당하는 것인, 색인 생성 장치.
   
9. 제 8 항에 있어서,
   상기 색인 생성부는 상기 클러스터 셀이 생성되는 경우, 상기 클러스터 셀에 대응하여 상기 내부 노드에 대한 하위 레벨로 신규 내부 노드를 할당하는 것인, 색인 생성 장치.
   
10. 제 8 항에 있어서,
    상기 색인 생성부는 상기 클러스터 셀 이외의 셀에 데이터 벡터가 국외자로 삽입되어 상기 셀의 셀 밀도가 상기 밀도 임계치를 초과하는 경우, 상기 클러스터 셀 이외의 셀에 대응하여 상기 내부 노드에 같은 레벨의 신규 내부 노드를 연결하여 할당하는 것인, 색인 생성 장치.
    

Images