kd-tree Introduction

from Or........../Work 2009.08.27 14:57
⊙ Introduction
여기에서 다루는 kd-tree는 공간 DB로, 기존의 문자 DB와는 다르다. key 값 매칭 문제이고, 굉장히 큰 양을 공간 기반으로 검색한다. 공간 기반 검색이란, range로 표현된 질의를 검색한다는 것이다. Spatial data는 points, lines, polygons 등을 포함하고 있따.
Spatial data를 효율적으로 지원하기 위해서는, 다음과 같은 특징적 어려움을 알아야 한다.
① First, spatial data are latge in quantity, complex in structures and relationships
② Second, the retrieval process employs complex spatial operators like intersection, adjacency, and containment
③ Third, it is difficult to define a spatial ordering, so conventional techniques cannot be employed for spatial operations
→ spatial indices 필요!

(1) kd-tree : Binary-tree based indexing
kd-tree는 multi-attribute data index를 binary search하는 tree로, k는 표현될 데이터 공간의 차원을 가리킨다. 각 depth에서, 어떤 branch로 갈 것인가를 결정하는 데에 다른 attribute이 사용된다. 예를 들어, 2-d (x,y) tree에서는 짝수 depth에서 x 좌표가 branch 기준이라면, 홀수 depth에서는 y 좌표가 branch 방향의 기준이 된다. 마지막으로, 이 tree는 꼭 균형을 이룰 필요는 없다.

A가 제일 먼저 들어간 것을 알 수 있다. 즉, 최초의 분리자는 root이다.



① Principle
Node는 각각의 실제 data point를 나타내고, 검색 방향의 지표가 된다. (left, right 두 개의 child가 있다.→ 현재 노드 값 보다 작은가? 큰가?)
한 Node는 5개의 field로 구성되어 있다. LOSON(작은 값을 가진 left 자식), HISON(큰 값을 가진 right 자식), 좌표(x,y,...), NAME(해당 노드에 대한 정보. 포인터가 들어갈 수도 있다.), DISC(좌표 이름을 가리킨다. 즉, 이 노드는 x를 기준으로 했느냐 y를 기준으로 했느냐. 등. ).

② Insertion
Binary search tree에서의 insertion 방법과 유사하다. 다른 점이 있다면, 앞에서 설명 했듯이, depth마다 비교하는 attribute가 다르다는 것이다. tree의 bottom에 도달하면, 거기에 새 node를 넣는다.

매우 쉽다;



③ Search
Search 역시 매우 straightforward하다. 흐흐 BST 처럼 찾아 내려가면 된다. 여기에서 역시, 다른점은 depth마다 비교 기준의 attribute이 다르다는 점 뿐. 참 그리고, 질의가, 조건 질의가 가능하다는 것이 또 하나 틀린데, 예를 들어, 'Y>20인 점들을 찾아라' 라든지, '(75,15)에 가까운 점들을 찾아라' 등이 가능하다는 것이다.
Region Search는 Euclidean distance를 이용하여 구할 수있다. node (a,b) 근처 거리 d안에 있는 점들을 다 구하라는 질의가 들어오면, 우선 (a-d) ≤ x ≤ (a+d), (b-d) ≤ y ≤ (b+d) 안의 점들을 다 구한다. 그런데 이렇게 구한 점은, 반지름 d인 원 안에 있는 점이 아니라, 한 변이 2d인 정사각형 안에 들어오는 점이므로, 점들을 구한 다음에 range안에 들어오는 게 맞는지 확인이 필요하다.

Search 결과 Miami를 찾았다!



④ Deletion
앞에 insert나 search는 BST와 비슷하여 쉬웠지만, deletion은 좀 더 복잡하다. 각 depth마다, DISC가 달라서, 원래 tree의 root는 DISC가 x 지만, subtree의 root는 y가 될 수도 있기 때문에, 모든 subtree가 kd-tree가 아니다. 그래서 그냥 마구 삭제해 버리면 문제가 생긴다.
kd-tree로 부터 (a,b) 노드를 삭제한다고 할 때, (a,b)의 두 subtree가 empty tree이면 그냥 삭제하면 되고, 아니면 (a,b)의 subtree들 중에서 가장 적절한 대체 노드 (c,d)를 찾아서, replace시킨다. 이 (c,d)는 recursive하게 다시 삭제되는 것이다. 그렇다면, 이 대체 노드는 어떻게 찾는 것일까? 오른쪽 subtree에서 가장 작은 값을 가진 노드나, 왼쪽 subtree에서 가장 큰 값을 고르면 된다. 그러면 다음의 예를 보자.

사실 이것도 찬찬히 보면 매우 쉽다. 그죠?



⑤ 장단점
kd-tree는 partial matching search에 유용하지만, empty space가 없고, point search와 region search가 다 가능하다. 하지만, 균형이 심~하게 안맞으면 performance가 안좋다. kd-tree는 메모리 기반 index이다. File 기반에서는... 안좋다.

 

출처 : http://www.snisni.net/98

'Or.......... > Work' 카테고리의 다른 글

Overview of the Major Structural Changes in Direct3D 10  (0) 2009.08.27
Scene Graph Rendering  (0) 2009.08.27
kd-tree Introduction  (0) 2009.08.27
Grass Rendering  (0) 2009.08.27
Water Rendering  (0) 2009.08.27
Flight Simulator : HUD - LCOSS  (0) 2009.08.27