KR20020004301A

KR20020004301A - 구형 피라미드 기법을 이용한 최근접 질의 처리 방법

Info

Publication number: KR20020004301A
Application number: KR1020000038050A
Authority: KR
Inventors: 이동호; 김형주
Original assignee: 이동호; 김형주
Priority date: 2000-07-04
Filing date: 2000-07-04
Publication date: 2002-01-16

Abstract

본 발명은 구형 피라미드 기법을 이용한 최근접 질의 처리 방법에 관한 것으로서, d-차원의 데이터 공간을 2d 개의 구형 피라미드로 분할하는 제1 단계; 분할된 상기 구형 피라미드를 다시 구형 조각으로 분할하는 제2 단계; 질의 점(query point)과 상기 구형 피라미드 사이의 최소 거리를 계산하여 오름차순으로 순위 큐에 삽입하는 제3 단계; 상기 순위 큐의 첫 번째 원소를 추출하여, 추출된 첫 번째 원소가 구형 피라미드이면 상기 구형 피라미드 안에 있는 구형 조각과 질의 점간 최소 거리를 계산하여 상기 구형 조각을 상기 큐에 다시 삽입하고, 상기 추출된 첫 번째 원소가 구형 조각이면 상기 구형 조각 안에 있는 객체와 질의 점간 거리를 계산하여 상기 객체를 상기 큐에 다시 삽입하고, 상기 추출된 첫 번째 원소가 객체이면 상기 객체를 최근접 질의의 결과로 반환하는 제4 단계;를 포함하는 것을 특징으로 하며, R*-tree와 X-tree상에서 구현된 점진적 k-최근접 질의 처리 방법보다 페이지 접근 횟수, CPU 사용시간, 전체 응답 시간 등의 측면에서 더욱 효율적인 효과가 있다.

Description

구형 피라미드 기법을 이용한 최근접 질의 처리 방법{Method of Nearest Query Processing using the Spherical Pyramid-Technique}

본 발명은 d-차원의 공간을 2d 개의 구형 피라미드들로 공간분할하여 고차원 데이터를 색인하는 구형 피라미드 기법을 이용하여 질의어에 대하여 최근접된 객체를 검색하는 구형피라미드기법을 이용한 최근접 질의 처리 방법에 대한 것이다.

최근접 질의 혹은 k-최근접 질의를 처리하기 위한 알고리즘은 GIS응용이나 패턴 인식, 서류 검색, 학습 이론 등의 분야에서 그 필요성에 의해 많은 연구가 이루어졌다. 이러한 알고리즘은 d-차원의 벡터 공간에서 점 객체나 임의의 공간 객체에 대하여 질의 객체와 가장 유사한 객체들을 찾기 위해 개발되었으며, 대부분 일정한 공간 자료구조를 기반으로 하고 있다. 예를 들어, k-d tree에 기반한 알고리즘과 quad-tree에 기반한 알고리즘, 그리고, R-tree에 기반한 알고리즘 등이 있으며 이러한 알고리즘들은 대부분 수정을 통하여 다른 공간 자료구조 상에서도 자연스럽게 적용될 수 있다.

Roussopoulos와 Kelley등은 mindist와 minmaxdist를 이용하여 R-tree상에서 branch & bound 알고리즘으로 질의 점(질의 객체)와 가장 유사한 k개의 객체를 검색하는 알고리즘을 제안하였다. 이 알고리즘의 기본적인 아이디어는 R-tree를 깊이 우선 방식으로 탐색하면서 후보가 될 수 있는 객체들을 활성 리스트(Active Branch List)에 유지하는 것이다. 이 알고리즘은 k가 이미 결정된 상태에서 알고리즘이 시작된다. 즉, 사전에 k가 이미 결정되기 때문에 만약 사용자가 (k+1)번째 객체를 얻고자 하다면 알고리즘을 처음부터 다시 시작해야 하는 단점이 존재한다(N. Roussopoulos, S. Kelley, F. Vincent. "Nearest Neighbor Queries" Proc. ACM SIGMOD, San Jose, CA, pages 71-79, 1995.).

Hjaltason과 Samet은 이러한 단점을 제거하고자 사전에 k 값을 결정하는 것이 아니라 사용자의 요구에 따라 한 개씩 점진적으로 질의 결과를 얻어내는 점진적 최근접(incremental nearest neighbor) 질의 처리 알고리즘을 제안하였다. 공간 데이터베이스에서 사용자는 질의 객체와 가장 가까운 객체들을 하나씩 차례로 얻고자 하는 `거리 브라우징(distance browsing)' 요구를 많이 하게 된다. 점진적 최근접 알고리즘은 이러한 응용을 위하여 고안되었다. 이 알고리즘은 순위 큐(priority queue)를 사용하여 항상 질의 객체와 가장 가까운 객체가 큐의 맨 앞에 오게 함으로써, 사용자가 원할 때마다 큐의 맨 앞에 있는 원소를 반환하여 차례로 가장 가까운 객체들을 질의 결과로 보여준다. 따라서, 사용자는 항상 원하는 만큼의 객체를 알고리즘을 처음부터 재시작 할 필요 없이 얻을 수 있게 된다. 즉, k개의 객체를 검색한 후, (k+1)번째 객체를 얻기 위해 알고리즘을 처음부터 재시작할 필요 없이 순위 큐에 남아 있는 다음 객체를 반환하면 된다.

Hjaltason와 Samet는 점진적 최근접 알고리즘을 이용하여 k-최근접 질의를 처리할 경우에도 기존의 R*-tree상의 k-최근접 질의 처리 알고리즘보다 효율적임을 보였다(Gisli R. Hjaltason, Hanan Samet. "Distance Browsing in Spatial Databases." ACM Transaction on Database Systems, 24(2), pages 265-318,1999.).

그러나, 이 알고리즘도 고차원 데이터에 대해서는 효율적이지 못하다. 이것은 알고리즘 자체의 문제라기 보다는 R-tree라는 공간 자료구조가 고차원 공간상에서 효율적이지 못하기 때문이다.

유사 검색은 데이터베이스 시스템의 중요한 검색 기법 중에 하나로 대두되고 있다. 이는 특정 데이터를 고차원 공간상의 하나의 점으로 변환하여, 다차원 색인 구조를 이용하여 색인하고 검색하는 기법이다. 이러한 검색 기법이 가장 많이 사용되는 응용으로는 내용 기반 멀티미디어 정보 검색을 들 수 있다. 내용 기반 멀티미디어 정보 검색은 멀티미디어 데이터로부터 내용으로 추정되는 특징 데이터를 추출하여 이를 기반으로 검색하는 기법인데, 일반적으로 멀티미디어 데이터에서 추출한 특징 데이터들은 고차원 벡터 형태로 표현된다(S. Berchtold, D. A. Keim, and H.-P. Kriegel. "The X-tree: An Indexing Structure for High-Dimensional Data". Proc. 22nd Int. Conf. on Very Large Database, pages 28-39, September 1996.: S. Berchtold, D. Keim, H.-P. Kriegel, and T. Seidl. "Fast Nearest Neighbor Search in High-Dimensional Spaces". Proc. 14th Int. Conf on Data Engineering, Orlando, 1998.).

또한, 이러한 응용에서는 데이터베이스에 저장된 객체들 중에서 질의 객체와 가장 유사한 객체들을 검색하는 질의로 k-최근접 질의와 구형태의 영역 질의를 사용한다(D. A. White, and R. Jain. "Similarity Indexing with the SS-tree". Proc. 12th Int. Conf on Data Engineering, pages 516-523, 1996.).

k-최근접 질의는 질의 객체와 가장 유사한 k-개의 객체를 검색하는 것이고, 구형태의 영역 질의는 질의 객체와 일정한 유사성 허용 오차를 만족하는 모든 객체들을 검색하는 방법이다. 효율적인 유사 검색을 지원하기 위해서는 고차원 데이터를 효율적으로 색인할 수 있는 색인 구조와 이러한 색인 구조상에서 위와 같은 유사 질의를 효율적으로 처리할 수 있는 알고리즘이 필수적이다.

그러나, 상기한 종래 기술에 의하면, 저차원이나 중차원 데이터에 대하여 효율적인 색인을 제공하는 어떤 색인 구조도 고차원 데이터에 대해서는 효율적인 색인을 제공하지 못하는 한계가 있다.

본 발명은 상기와 같은 종래기술의 한계와 문제점을 해결하기 위한 것으로, 고차원 데이터를 효율적으로 색인하고 유사 검색에 많이 사용되는 구형태의 질의를 효율적으로 처리할 수 있는 알고리즘으로 구형 피라미드 기법을 제시한다.

더 나아가, 본 발명에서는 구형 피라미드 기법을 이용하여 질의 객체와 가장 유사한 k-개의 객체를 검색하는 k-최근접 질의 처리를 위한 알고리즘을 제시한다.

이로써, R*-tree와 X-tree상에서 구현된 점진적 k-최근접 질의 처리 방법보다, 페이지 접근 횟수, CPU 사용시간, 전체 응답 시간 등의 측면에서 더욱 효율적인 효과가 있음을 밝힌다.

도1은 구형 피라미드 기법의 공간 분할방법의 예시도.

도2는 구형 피라미드의 번호 결정 과정과 존재하는 점의 거리 예시도.

도3은 2차원 공간상에서 10개의 객체가 존재하는 구형 피라미드의 예시도.

도4는 질의 점과 인접 구형피라미드간 최소 거리 예시도.

도5a, 도5b, 도5c는, 질의 점과 구형 조각간 최소 거리(MINDIST) 예시도.

도6은 점진적 최근접 질의를 처리하기 위한 알고리즘 1.

도7a, 도7b, 도7c는, 데이터베이스 차원에 따른, 페이지 접근 횟수 그래프, CPU 사용시간 그래프, 전체 응답 시간 그래프.

도8a, 도8b, 도8c는, 데이터베이스크기에 따른, 페이지 접근 횟수 그래프, CPU 사용시간 그래프, 전체 응답 시간 그래프.

도9a, 도9b, 도9c는, 실제 데이터를 이용한 실시예로서, 페이지 접근 횟수 그래프, CPU 사용시간 그래프, 전체 응답 시간 그래프.

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

10. 데이터 공간 중앙점 11. 구형 피라미드

12. (d-1)차원의 구형평면 13. 구형 조각

31. 최근접점 41. 질의 점

본 발명에 의한 구형 피라미드 기법을 이용한 최근접 질의 처리 방법은, d-차원의 데이터 공간을 2d 개의 구형 피라미드로 분할하는 제1 단계; 분할된 상기구형 피라미드를 다시 구형 조각으로 분할하는 제2 단계; 질의 점(query point)과 상기 구형 피라미드 사이의 최소 거리를 계산하여 오름차순으로 순위 큐에 삽입하는 제3 단계; 상기 순위 큐의 첫 번째 원소를 추출하여, 추출된 첫 번째 원소가 구형 피라미드이면 상기 구형 피라미드 안에 있는 구형 조각과 질의 점간 최소 거리를 계산하여 상기 구형 조각을 상기 큐에 다시 삽입하고, 상기 추출된 첫 번째 원소가 구형 조각이면 상기 구형 조각 안에 있는 객체와 질의 점간 거리를 계산하여 상기 객체를 상기 큐에 다시 삽입하고, 상기 추출된 첫 번째 원소가 객체이면 상기 객체를 최근접 질의의 결과로 반환하는 제4 단계;를 포함하는 것을 특징으로 한다.

상기 제3 단계와 제4 단계에서 질의 점과 각 구형 피라미드 또는 구형 조각 사이의 거리를 계산하는 데에는 특별히 정의된 식을 적용하기도 한다.

이하, 수학식과 도면을 참조하여 본 발명을 상세히 설명한다. 그러나, 이들 수학식과 도면은 예시적인 목적일 뿐 본 발명이 이에 한정되는 것은 아니다.

1. 구형 피라미드 기법

구형 피라미드 기법은 d-차원의 점을 1-차원 값으로 변환하여 B+-트리와 같은 효율적인 1-차원 색인 구조를 사용하여 1-차원 값들을 저장하고 접근한다. 이러한 변환은 2단계로 이루어진다.

첫 번째 단계에서는, d-차원의 데이터 공간을 2d 개의 구형 피라미드들로 분할한다. 즉, 데이터 공간의 중앙점(0.5, 0.5, ..., 0.5)을 상단점으로 하고 (d-1)-차원의 구형 평면을 기저로 가지는 2d개의 구형 피라미드들로 공간을 분할한다. 두 번째 단계는, 각 단일 구형 피라미드의 상단점을 중심으로 갖는 여러 개의 구형 조각(bounding slice)들로 나눈다. 이러한 구형태의 조각은 B+-트리의 한 페이지에 상응하게 된다.

도 1과 도 2는 2차원 공간상에서 구형 피라미드 기법의 공간 분할방법을 예시하여 주고 있다. 도 1에서는, 하나의 구형 피라미드(11)가 4개의 구형 조각(13)들로 분할되는 것을 예시하였다. 먼저, 2차원 공간상에서 4개의 구형 피라미드(11)들로 분할되며, 각 구형 피라미드는 동일하게 공간의 중앙점(10)을 상단점으로 가지고 하나의 곡선(12)을 기저로 가진다. 이것은 d-차원으로 동일하게 확장될 수 있으며, d-차원의 구는 2d 개의 (d-1)-차원의 구형 평면을 가지기 때문에 2d개의 구형 피라미드를 얻을 수 있다. 그리고, d-차원에서는 기저가 곡선이 아니라 (d-1)-차원의 구형 평면이 된다. 두 번째 단계에서 각 구형 피라미드는 상단점을 중심으로 갖는 여러 개의 구형 조각(13)들로 분할된다.

다음의 수학식 1과 2는 구형 피라미드 기법의 공간 분할 전략의 첫 번째와 두 번째 단계에 상응한다.

즉, 수학식 1에서는, d-차원의 점 v는 구형 피라미드 sp_i에 존재한다고 정의된다.

그리고, d-차원의 점 v가 주어졌을 때, 점 v의 거리는 다음의 수학식 2와 같이 정의된다.

즉, 도 2에 도시된 바와 같이, 먼저 수학식 1을 이용하여 어떤 점 v가 속해 있는 구형 피라미드의 번호를 결정한다. 그리고, 수학식 2에 의해 점 v의 위치를 결정한다.

마지막으로, 아래 수학식 3은 수학식 1과 2를 이용하여 d-차원의 점 v를 1차원 값으로 변환한다.

즉, d-차원의 점 v가 주어졌을 때, sp_i가 수학식 1에 의해 얻어진 점 v가 속해 있는 구형 피라미드이고, d_v가 수학식 2에 의해 얻어진 점 v의 거리라고 할 때, 점 v의 구형 피라미드 값은 수학식 3과 같이 정의된다.

예를 들어, 2차원 점 v=(0.4, 0.8)가 주어질 경우, j_max는 1이고 v₁(=0.8)이 0.5보다 크기 때문에 정의 1에 의하여 점 v는 sp₍₁₊₂₎에 속하게 된다. 또한, 수학식2에 의해 중앙으로부터 점 v까지의 거리는이 된다. 따라서, 점 v의 구형 피라미드 값은 수학식 3에 의해 ()이 된다.

그리고, 구형 피라미드 기법에 의해 색인을 생성하는 과정은 간단하다. 먼저, d-차원의 점 v가 주어지며 이것의 구형 피라미드 값(spv_v)을 결정한 후에, 이 값을 B+-트리의 키값으로 하여 점 v를 B+-트리에 삽입한다.

그리고, 점 v와 구형 피라미드 값 spv_v를 B+-트리의 해당 데이터 페이지에 저장한다. 갱신이나 삭제도 B+-트리를 이용하여 할 수 있다.

도 3은 2차원 공간상에서 구형 피라미드의 예를 보여 주고 있다. 각 구형 조각에는 1개의 객체만 들어간다고 가정하자. 도 3에서 질의 점(q)은 구형 피라미드상의 구형 조각(bounding slice) BS₄에 존재함을 알 수 있다. 대부분의 최근접 질의 처리 알고리즘이 그렇듯이 구형 피라미드(SPY-TEC)상에서의 최근접 질의 처리 알고리즘도 질의 점이 속해 있는 데이터 페이지에 있는 객체들을 먼저 검색한다. 그러나, 효율적인 검색을 위해서는 질의 점과 구형 피라미드 사이의 최소 거리와 질의 점과 구형 조각 사이의 최소 거리를 측정할 필요가 있다. 이러한 거리들을 순서화함으로써 검색시 불필요하게 방문하는 페이지들의 수를 줄일 수 있다.

2. 질의 점과 구형 피라미드의 최소거리

다음의 수학식 4는 질의 점과 구형 피라미드 사이의 최소 거리를 위한 정리이다. 이러한 거리 측정 과정을 좀 더 단순화시켜 설명하기 위하여 질의 점이 속해 있는 구형 피라미드 번호가 차원 d보다 작은 경우만을 설명한다. 차원 d보다 큰 경우도 유사한 방법으로 확장이 가능함은 물론이다.

즉, 질의 점(q=[q₀, q₁,...,q_d-1])이 주어졌을 때, 질의 점이 속해 있는 구형 피라미드를 sp_j(j< d)라 하면, 질의 점과 구형 피라미드 sp_i와의 최소 거리 MINDIST(q, sp_i)는 수학식 4와 같이 정의된다(Lemma 1).

위상 수학에서 한 점([q₀, q₁,...,q_d-1])과 한 평면(k₀x₀+ k₁x₁+,...,k_d-1x_d-1+ C = 0)이 주어졌을 때, 이 점과 평면 사이의 최소 거리는 점에서 평면에 이르는 수직선으로 다음과 같이 정의된다.

상기 거리공식을 이용하여 (i> d)인 경우와 (i< d)인 경우 각각 수학식 4를 증명할 수 있다.

먼저, i=j이면, sp_i는 질의 점이 속해 있는 구형 피라미드이다. 따라서,MINDIST(q, sp_i)= 0 이다.인 경우, sp_i는 질의 점이 속해 있는 구형 피라미드 sp_j의 맞은 편에 있는 구형 피라미드이다. 따라서, 질의 점과 구형 피라미드 sp_i에 이르는 최소거리는 sp_i의 상단점, 즉, 공간의 중앙점과 질의 점 사이의 거리가 된다. 따라서, MINDIST(q, sp_i)= d_q가 된다. 단위 공간을 기반으로 하기 때문에 상기 거리공식의 색인 k_n와 상수 C는 [-1, 0, 1]의 값 중에서 하나를 갖는다.

i< d 이면, 도4의 2차원 공간의 예처럼 질의 점과 인접하는 구형 피라미드 sp_i의 한 측면의 방정식은 "k_jx_j+ k_ix_i= 0" (42)이 된다. 이것은 d차원 이상의 공간에 대해서도 일관되게 확장이 가능하다. 2차원 공간인 경우에는 직선이지만, d차원 공간인 경우에는 (d-1)차원 평면이 된다. 이 (d-1)차원 평면의 방정식은 k_i와 k_j를 제외한 모든 색인이 0이 되는 일반적인 특성을 가진다. 이때, k_j=1 이고, k_i는 i< d 이므로 -1 이다. 따라서, 질의 점과 인접한 구형 피라미드 sp_i사이의 최소 거리는 |q_j- q_i|/가 된다.

마지막으로, i> d 인 경우는 질의 점과 인접하는 구형 피라미드 sp_i의 한 측면의 방정식은 "k_jx_j+ k_ix_i-1 = 0" (43)이 된다.

이 때, k_j= 1 이고, k_i는 i> d 이므로 1이다. 따라서, 질의 점과 인접한 구형 피라미드 sp_i사이의 거리는 |q_j- q_i|/가 된다.

3. 질의 점과 구형 조각의 최소거리

질의 점과 구형 조각 사이의 최소 거리를 측정하는 것은 질의 점과 구형 피라미드 사이의 최소 거리를 측정하는 것보다 복잡하다. 질의 점이 속해 있는 구형 피라미드 안에 존재하는 구형 조각들과 맞은 편에 있는 구형 조각들, 그리고 인접한 구형 피라미드 안에 존재하는 구형 조각들로 나누어 정리할 수 있다.

질의 점이 주어졌을 때 질의 점이 속해 있는 구형 피라미드를 sp_j라 하면, 질의 점과 구형 피라미드 sp_i안에 존재하는 구형 조각(BS_l)들과의 최소 거리 MINDIST(q, BS_l) 는 다음 수학식 5a 내지 5c와 같다(Lemma 2).

첫째로, 구형 조각이 질의 점이 속해 있는 구형피라미드 안에 존재하는 경우(i=j), 질의 점과 구형 조각간 최소 거리는 수학식 5a와 같다.

둘째로, 구형 조각이 질의 점의 맞은편에 있는 구형피라미드 안에 존재하는 경우(|i-j|= d), 최소거리는 수학식 5b와 같다.

여기서,는 질의 점에서 가장 가까운 구형 피라미드의 한 면에 이르는 거리이고,는 d_q와에 의해 만들어지는 직각 삼각형의 한 각()이다.

셋째로, 구형 조각이 질의 점과 인접한 구형 피라미드 안에 존재하는 경우, 최소거리는 수학식 5c와 같다.

여기서,는와 d_q에 의해 만들어지는 직각 삼격형의 밑변의 길이이다. min(BS_l)는 구형 조각(BS_l)에 속해 있는 점들 중에서d_v값이 가장 적은 것이며, max(BS_l)는d_v값이 가장 큰 것을 의미한다. min(BS_l)와 max(BS_l)를 이용하여 상기 수학식 5a 내지 5c는 다음과 같이 증명할 수 있다.

첫째(수학식 5a)로, (1) 질의 점이 BS_l안에 속해 있는 경우,MINDIST(q,BS_l)는 질의 점과 BS_l의 안에 존재하는 어떤 점과의 거리보다 작거나 같아야 함으로 0이 된다. (2) d_q>max(BS_l)이면,MINDIST(q, BS_l)는 BS_l에 존재하는 점들 중에서 중앙으로부터 가장 멀리 떨어진 점 v의 d_v, 즉, max(BS_l)와 d_q의 차이가 된다. (3) 마지막으로, d_q<min(BS_l)인 경우, MINDIST(q, BS_l)는 BS_l에 존재하는 점들 중에서 중앙으로부터 가장 가까운 거리에 있는 점 v의 d_v, 즉, min(BS_l)와 d_q의 차이가 된다. 도 5a는 2차원 공간에서, 위와 같이 i=j인 경우를 보여주는 예이다.

둘째(수학식 5b)로, |i-j|= d 이면, sp_i는 질의 점이 속해 있는 구형 피라미드의 맞은편에 있는 구형 피라미드가 된다. 이 경우 질의 점과 해당 구형 조각 사이의 최소 거리 d_q와 min(BS_l), 그리고, 이것들로 이루어지는 삼각형의 밑변의 길이가 된다. 이는 코사인 제 2법칙으로 구할 수 있다. 먼저, 질의 점과 가장 가까운 인접 구형 피라미드의 한 면에 이르는 거리를라 하면, d_q와에 의해 이루어지는 각는이 된다. 또한, 구형 피라미드의 상단 점의 각은 항상이므로, MINDIST(q, BS_l)는 코사인 제2법칙에 의해이 된다. 도5b는 위와 같이 |i-j|= d인 경우를 보여주는 예이다.

셋째(수학식 5c)로, 이 경우는 sp_i가 질의 점에 인접해 있는 구형 피라미드이다.와 d_q에 의해 만들어지는 직각 삼각형의 밑변의 길이를라 하면,인 경우, BS_l과 q 사이의 최소 거리는 첫째 경우와 같은 이유로 질의 점 q로부터 sp_i의 수직거리인가 된다. 한편,> max(BS_l)인 경우, MINDIST(q, BS_l)는와 |-max(BS_l)|에 의해 만들어지는 직각 삼각형의 빗변의 길이가 된다. 그리고,< min(BS_l)인 경우는 경우1과 동일한 이유로와 |-min(BS_l)|에 의해 만들어지는 직각 삼각형의 빗변의 길이가 된다.

4. 질의 점과 객체의 거리

질의 점(q=[q₀, q₁, ..., q_d-1])과 하나의 객체(p=[p₀, p₁, ...p_d-1]) 사이의 거리(DIST)는 두 점 사이의 거리를 구하는 아래의 수학식 6과 같다.

표 1은 도 3의 질의 점(q)과 각 구형 피라미드(SP), 구형 조각(BS)의 최소거리 및 해당 객체(OBJ)와의 거리를 수학식 4 내지 수학식 6을 이용하여 계산한 값들을 정리한 것이다.

5. 최근접 질의 처리

그리고, 상기한 수학식 4 내지 수학식 5c를 이용하여, 점진적 최근접 질의를 처리하기 위한 알고리즘은 도6과 같다.

도6(알고리즘1)의 줄 1 내지 4에서는 수학식4 (Lemma 1)를 이용하여 질의 점과 각 구형 피라미드 사이의 최소 거리를 계산하여 순위 큐에 삽입한다. 그리고, 줄 6 내지 21은 큐가 empty될 때까지, 큐의 첫 번째 원소를 추출하여 원소의 타입에 맞는 처리를 해준다. 추출된 원소가 구형 피라미드이면 해당 구형 피라미드 안에 있는 구형 조각들과 질의 점과의 최소 거리를 계산하여 이를 다시 큐에 삽입한다. 만약, 추출한 원소의 타입이 구형 조각이면 해당 구형 조각 안에 있는 객체와 질의 점과의 거리를 계산하여 다시 큐에 삽입한다. 그리고, 마지막으로 추출한 원소가 객체이면 해당 객체를 최근접 질의의 결과로 반환한다. 순위 큐는 항상 최소 거리를 가지고 있는 원소가 맨 앞에 있기 때문에 반환된 객체는 질의 점과 가장 가까이에 있는 객체가 된다.

다음은 도 3의 예에 대하여 상기 도6의 알고리즘 1이 수행되는 동안 순위 큐의 내용을 보여주고 있다.

1. Enqueue SP0∼SP3; [SP1,0], [SP2,4], [SP0,21], [SP3,33]

2. Dequeue SP1, enqueue BS3, BS4, BS5; [BS4,0], [BS5,2], [SP2,4], [BS3,14],

[SP0,21], [SP3,33]

3. Dequeue BS4, enqueuee; [BS5,2], [SP2,4], [BS3,14], [e,19], [SP0,21],

[SP3,33]

4. Dequeue BS5, enqueuef; [SP2,4], [f,12], [BS3,14], [e,19], [SP0,21],

[SP3,33]

5. Dequeue SP2, enqueue BS6, BS7; [BS7,4], [BS6,8], [f,12], [BS3,14], [e,19],

[SP0,21], [SP3,33]

6. Dequeue BS7, enqueueh; [h,6], [BS6,8], [f,12], [BS3,14], [e,19],

[SP0,21], [SP3,33]

7. Dequeueh, reporthas 1st nearest neighbor

상기 도6의 알고리즘 1은 먼저 질의 점과 각 구형 피라미드 sp₀내지 sp₃사이의 거리를 측정하여 이를 큐에 삽입하면서 시작된다. 상기 알고리즘 1의 순위 큐는 항상 거리를 키값으로 오름차순으로 정렬됨으로 질의 점이 속해 있는 구형 피라미드 sp₁가 큐의 맨 앞에 있게 된다. 다음, 알고리즘 1의 줄 7에서 큐의 첫 번째원소를 추출하고 이것이 구형 피라미드 sp₁이므로 sp₁에 속해있는 구형 조각 BS₃, BS₄, BS₅에 대하여 질의 점과의 거리를 측정하여 큐에 삽입하게 된다. 다시, BS₄를 추출하고 이것이 구형 조각이므로 BS₄에 있는 모든 객체들을 큐에 삽입하게 된다. 이 경우는 하나의 객체만을 가정했으므로 객체e가 큐에 삽입된다. 이런 식으로 알고리즘 1이 진행되며 결국 질의 점과 가장 가까운 객체가 큐의 맨 앞에 있게 된다(상기 예에서는h). 점진적 최근접 질의 처리 알고리즘은 순위 큐를 이용하여 사용자가 원하는 최근접 객체들을 차례대로 추출할 수 있다.

상기 알고리즘 1의while-루프에서 최근접 객체로 반환하는 객체의 수를 제어하면 간단히 기존의 k-최근접 질의를 처리할 수 있다.

비교 실시예

구형 피라미드 기법을 이용한 최근접 질의 처리의 효율성을 보이기 위하여 R*-tree와 X-tree와의 비교 실험을 비교 실시예로 제시한다.

공정한 실험을 위하여 R*-tree와 X-tree상에서 점진적 최근접 질의 처리 알고리즘을 구현하였으며 k-최근접 질의를 처리할 수 있도록 알고리즘을 수정하였다. 모든 실험은 128M의 주메모리와 10GB의 보조 기억장치를 가진 Sun Sparc 20 웍스테이션 상에서 수행되었으며, 블럭의 크기는 모든 색인 구조에서 4096 Byte이고, 블럭 사용률은 65%로 고정시켜 실시하였다.

실시예 1 (인위적 데이터를 이용한 비교 실시예)

인위적으로 생성된 데이터들은 20,000∼100,000개의 균등하게 분포된 데이터들이며 각 데이터의 차원은 4, 8, 12, 16, 20, 24이다.

첫 번째 실시예는 데이터의 차원을 변화시키면서 10개의 최근접 객체(10-NN)를 찾는데 소요되는 페이지 접근 횟수, CPU 사용 시간, 전체 질의 응답 시간을 측정하였다. 100개의 무작위로 선출된 질의 점을 사용하였으며 모든 결과는 100번의 질의 처리 결과에 대한 평균이다.

도7a 내지 도7c는 첫 번째 실시예의 결과 그래프이다. 전반적으로 데이터의 차원이 증가할수록 구형 피라미드 기법을 이용한 최근접 질의 처리가 기존의 R*-tree나 X-tree에 비해 효율적임을 알 수 있다. 도 7a는 페이지 접근 횟수를 보여주고 있는데, R*-tree는 12차원 이상에서는 거의 모든 내부 노드와 단말 노드를 접근해야 함을 볼 수 있다. X-tree는 비록 R*-tree보다는 적은 수의 페이지를 접근하나, R*-tree와 마찬가지로 고차원으로 올라갈수록 대부분의 페이지를 접근함을 알 수 있다. 구형 피라미드 기법도 비록 차원이 증가할수록 데이터 페이지 접근 횟수가 선형적으로 증가하나 항상 R*-tree나 X-tree보다 적음을 발견할 수 있었으며, 특히 24차원에서 R*-tree보다 34%, X-tree보다는 31% 정도의 성능향상이 있다. 최근접 질의 처리 알고리즘은 특정 거리 측정 함수(이를테면, R*-tree의 min-max distance)를 이용하여 노드들을 비교하고 정렬하여 처리하기 때문에 조인과 같은 다른 종류의 질의 처리에 비하여 CPU 사용 시간이 많이 소요된다[3].

도 7b는 CPU 사용 시간을 보여주고 있다. 비록 구형 피라미드 기법을 이용한 최근접 질의 처리 알고리즘은 각 구형 조각들과 질의 점 사이의 최소 거리를 측정하는 과정이 복잡해 보이지만 간단한 비교 연산을 통하여 각 경우를 쉽게 검사하여 최소 거리를 측정할 수 있다. 이에 반하여, R*-tree의 경우에는 고차원 공간으로 올라갈수록 영역들 간의 많은 겹침(overlap)이 발생하며 이에 따라 거리를 비교하고 계산하는데 많은 CPU 시간이 사용되는 단점이 있다. 그러나 구형 피라미드 기법은 그 구조상 겹침이 없는 공간 분할 방법을 이용하기 때문에 영역 겹침에서 오는 부담이 없다. 24차원의 경우, CPU 사용 시간에 있어서 R*-tree보다는 38%, X-tree보다는 35%정도의 성능향상이 있다.

마지막으로, 도 7c는 전체 질의 응답 시간을 보여주고 있는데, 페이지 접근 횟수나 CPU 사용 시간과 거의 유사한 결과를 보여주고 있으며, 24차원일 때, R*-tree보다는 45%, X-tree보다는 37%정도의 성능 향상이 있다.

실시예 2 (실제 데이터를 이용한 비교 실시예)

본 실시예는 데이터베이스의 크기를 변화시키면서 성능의 변화를 측정한 것이다. 차원은 16차원으로 고정시켜 수행하였다. 도8a 내지 도8c는 본 실시예의 결과를 보여주고 있으며, 첫 번째 실시예와 거의 유사한 결과를 확인할 수 있었다. 16차원 100,000개의 데이터에 대해서 구형 피라미드 기법을 이용한 최근접 질의 처리가 R*-tree에 비하여 47%, X-tree보다는 35%정도 빨리 질의를 처리함을 알 수 있었다.

이 실시예에서는 실제 CAD객체의 영역을 표시하는 16차원 푸리에(Fourier)점 100,000개를 사용하였다. 질의 객체는 실제 데이터에서 무작위로 선출한 100개의 16차원 푸리에 점들을 사용하였으며 모든 결과는 100번의 질의에 대한 평균값이다.

최근접 객체의 개수(k)를 1에서 10까지 증가시키면서 질의 처리에 필요한 페이지 접근 횟수, CPU 사용 시간, 전체 응답 시간을 측정하였다.

도9a 내지 도9c는 본 실시예의 결과를 보여준다.

도9a는 k가 변할 때, X-tree, R*-tree, 구형 피라미드 기법을 이용한 최근접 질의 처리, 각각의 페이지 접근 횟수를 나타낸다.

k=1일 때, 구형 피라미드 기법을 이용한 최근접 질의 처리 알고리즘은 단지 1개의 데이터 페이지만을 접근함으로써 질의 객체와 가장 가까운 객체(즉, 질의 객체 자체)를 검색함을 알 수 있었다. 그러나, X-tree는 13.45개의 페이지를 접근하고, R*-tree는 16.43개의 페이지를 접근해야 질의를 처리할 수 있었다.

또한, k=3 이상인 경우에 X-tree나 R*-tree는 거의 모든 데이터 페이지를 접근해야 함을 알 수 있었다. 구형 피라미드의 경우에도 k=3 이상이 되면 k값이 1이나 2인 경우보다는 많은 수의 데이터 페이지를 접근해야 하지만 항상 X-tree나 R*-tree보다는 적은 수의 데이터 페이지를 접근함을 알 수 있었다.

CPU 사용 시간이나 전체 질의 응답 시간도 역시 페이지 접근 횟수와 유사한 경향을 보여주고 있다. k=10일 때, 구형 피라미드 기법을 이용한 최근접 질의 처리 알고리즘은 전체 질의 응답 시간에 있어서 R*-tree보다는 67%, X-tree보다는 60% 정도 더 효율적이다.

즉, 인위적 데이터를 이용한 실시예와 비교해 보면, 구형 피라미드 기법을 이용한 최근접 질의 처리 알고리즘은 균등하게 분포된 데이터 집합보다 실제 데이터 집합에서 더 좋은 성능을 보인다.

이상과 같이, 본 발명에서는 기존의 구형 피라미드 기법을 이용하여 점진적 최근접 질의 처리 방법을 제시하였다. 또한, 다양한 실시예를 통하여 이 방법(알고리즘)이 기존의 X-tree나 R*-tree의 점진적 최근접 질의 처리 알고리즘보다 효율적임을 알 수 있다. 구형 피라미드 기법은 그 구조가 기존의 R*-tree 기반의 다른 색인 구조에 비하여 단순하며 B+-tree를 그대로 이용할 수 있기 때문에 B+-tree가 가지는 빠른 삽입과 검색, 삭제의 장점을 그대로 이용할 수 있다.

또한, 구형 피라미드 기법은 현재 사용되는 어떤 종류의 데이터베이스 시스템 상에서도 B+-tree를 이용하여 쉽게 구현될 수 있으며, 따라서 동시성 제어나 회복 기법도 그대로 이용할 수 있는 효과가 있다.

본 발명에 의한 구형 피라미드 기법을 이용한 최근접 질의 처리 방법을 통하여, 고차원 데이터를 효율적으로 색인하고 유사 검색에 많이 사용되는 구형태의 질의를 더욱 효율적으로 처리할 수 있게 된다. 더 나아가, 본 발명에 의한 구형 피라미드 기법을 이용하여, 질의 점(질의 객체)와 가장 유사한 k-개의 객체를 검색하는 k-최근접 질의 처리를 위한 알고리즘을 더욱 효율적으로 수행하게 된다.

이상에서 비교 실시예를 통하여, 본 발명에 의한 구형 피라미드 기법을 이용한 최근접 질의 처리 방법이, R*-tree와 X-tree상에서 구현된 점진적 k-최근접 질의 처리 방법보다, 페이지 접근 횟수, CPU 사용시간, 전체 응답 시간 등의 측면에서 더욱 효율적인 효과가 있음을 밝혔다.

Claims

d-차원의 데이터 공간을 2d 개의 구형 피라미드로 분할하는 제1 단계;

분할된 상기 구형 피라미드를 다시 구형 조각으로 분할하는 제2 단계;

질의 점(query point)과 상기 구형 피라미드 사이의 최소 거리를 계산하여 오름차순으로 순위 큐에 삽입하는 제3 단계;

상기 순위 큐의 첫 번째 원소를 추출하여, 추출된 첫 번째 원소가 구형 피라미드이면 상기 구형 피라미드 안에 있는 구형 조각과 질의 점간 최소 거리를 계산하여 상기 구형 조각을 상기 순위 큐에 다시 삽입하고, 상기 추출된 첫 번째 원소가 구형 조각이면 상기 구형 조각 안에 있는 객체와 질의 점간 거리를 계산하여 상기 객체를 상기 순위 큐에 다시 삽입하고, 상기 추출된 첫 번째 원소가 객체이면 상기 객체를 최근접 질의의 결과로 반환하는 제4 단계;를 포함하는, 구형 피라미드 기법을 이용한 최근접 질의 처리 방법.
제1항에 있어서,

상기 제3 단계에서, 상기 질의 점(q)과 구형 피라미드(sp_i)간 최소 거리MINDIST(q,sp_i)는, 질의 점이 속해 있는 구형 피라미드를 sp_j(j< d) 라 하면,

와 같이 정의되는, 구형 피라미드 기법을 이용한 최근접 질의 처리 방법.
제1항 또는 제2항에 있어서,

상기 제4 단계에서, 질의 점(q)과 구형 피라미드(sp_i) 안에 존재하는 구형 조각(BS_l)과의 최소 거리 MINDIST(q, BS_l) 는, 질의 점이 속해 있는 구형 피라미드를 sp_j라 할 때,

상기 구형 조각이, 질의 점이 속해 있는 구형 피라미드 안에 존재하는 경우(i=j)에는,

와 같고,

상기 구형 조각이, 질의 점의 맞은편에 있는 구형피라미드 안에 존재하는 경우(|i - j|= d) 에는,를 질의 점에서 가장 가까운 구형 피라미드의 한 면에 이르는 거리라 하고,를 d_q와에 의해 만들어지는 직각 삼각형의 한 각() 이라고 할 때,

와 같고,

상기 구형 조각이, 질의 점과 인접한 구형 피라미드 안에 존재하는 경우에는,와 d_q에 의해 만들어지는 직각 삼격형의 밑변의 길이를라고 할 때,

와 같이 정의되는, 구형 피라미드 기법을 이용한 최근접 질의 처리 방법.