컴퓨터 과학!/Algorithms2004. 11. 16. 00:05
이건 지난 학기 FS 시간에 배운 것인데,
이번에 알고리즘 시간에 나와서
한 번 복습!



⊙ 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 기반에서는... 안좋다.
Posted by 스니

댓글을 달아 주세요

  1. 쳇, 공부쟁이!

    2004.11.16 09:13 [ ADDR : EDIT/ DEL : REPLY ]
  2. 치앙수

    이거 뭐에요 -_-a;

    2004.11.16 18:42 [ ADDR : EDIT/ DEL : REPLY ]
  3. 스니스니

    지난 학기 FS 시간에 했다던 kd-tree야. 으흐흐흐 잘 읽어봉. 쉬움.

    2004.11.16 19:09 [ ADDR : EDIT/ DEL : REPLY ]
  4. Michelle

    요거 찾아 들어왔슴다. 꼭꼭씹어서 이해되었구요... ^^
    혹 제가 모르는거 있음 물어도 되나요?
    많이 도와주세요~~~

    2006.09.25 00:11 [ ADDR : EDIT/ DEL : REPLY ]
  5. 아.. 저도 많이 부족하지만...
    제가 아는 것이라면야.. ^^

    2006.09.25 18:39 [ ADDR : EDIT/ DEL : REPLY ]
  6. 비케이러브

    알고리즘에 대한 기초가 많이 부족한 탓인지 아무리 읽어봐도 잘 이해가 가질 않네요..이 알고리즘으로 image serach 프로그램을 만들어야 하는데 어떻게 공부를 해야 할까요?쫌 가르쳐 주세요

    2006.11.14 15:36 [ ADDR : EDIT/ DEL : REPLY ]
  7. ㅇㅇ

    퍼가염..

    2007.04.10 11:11 [ ADDR : EDIT/ DEL : REPLY ]
  8. Kurt

    허헛~! 구글에서 k-d tree 치니까 세 번째로 뜨는구랴~~

    2007.10.11 23:13 [ ADDR : EDIT/ DEL : REPLY ]
  9. 스니스니

    한때 잠깐 열심히 할려던 시절이 있었지 -ㅅ-;;

    2007.10.20 17:17 [ ADDR : EDIT/ DEL : REPLY ]
  10. 재밌게 잘 써 놓으셔서 퍼갑니다. 스크랩이나 트랙백으로 가져가고 싶었는데, 서비스업체가 달라서 안되네요.. 암튼 잘 보고 갑니다^^

    2007.11.09 19:14 [ ADDR : EDIT/ DEL : REPLY ]
  11. 스니스니

    네ㅡ 얼마든지요! : )

    2007.11.16 13:29 [ ADDR : EDIT/ DEL : REPLY ]
  12. 아아아악 누나~~~!! 잘 지내죠? 흐윽 ㅠ
    알고리즘 분석 셤이 낼이라 kd-tree 검색하다가 익숙한 스니스니 보고 ㅋㅋ

    역시 사발의 천재계보군요 흐음흐음...이런 정리를!
    잘 참고하고 가요~~^^

    2009.10.22 20:16 [ ADDR : EDIT/ DEL : REPLY ]
  13. 근데 deletion 할때 그림에서는 오른쪽 subtree이던 왼쪽 subtree이던 minimum 값만 찾아서 교체해주네요. 누나 글이랑 달라서 어느쪽이 맞는건가 해서요 ㅠ_ㅠ

    2009.10.22 20:35 [ ADDR : EDIT/ DEL : REPLY ]
    • 그래, 그러고 보니 설명과 그림에 약간 문제가 있구나.
      너무 오래전에 작성한 글이라 다시 읽어보고 다음과 같은 결론을 내렸다.
      1. 자료구조라는 것은 정해진 규칙을 '유지'하고 있도록 만드는 것이 주 목적이다. 이 규칙은 검색을 용이하게 하며, 따라서 이 규칙을 지키도록 삽입과 삭제 작업을 해 주어야 한다.
      2. kd-tree의 규칙은 각 레벨마다 기준 좌표(DISC)가 다른 BST이다. 따라서 left subtree의 x-DISC에 해당하는 노드의 x값은 parent의 x값보다 모두 작아야 하며, right subtree의 x-DISC에 해당하는 노드의 x값은 parent의 x값보다 모두 커야한다. y도 마찬가지이다.
      3. 따라서, right subtree의 min, left subtree의 max로 target을 교체하여 삭제하는 것이 기본적으로 생각할 수 있는 방법이다. (C노드를 E노드로 교체)
      4. 그러나, 그림에서는 left subtree의 min으로 교체하고 그 subtree를 target의 right subtree로 만들어주었다. 이것은, 구현의 특징이라고 할 수 있는데, 이 방법에서는 left subtree의 max냐 right subtree의 min이냐 고민하기 전에, 무조건 right subtree의 min을 구해서 삭제하고, right subtree가 empty일 때에만 left subtree에서 교체할 값을 찾는 방법을 사용하기 때문인 것 같다. (C노드를 D노드로 교체한 후, D의 left subtree를 right subtree로 바꾸어주었다.)
      이렇게 한 이유는 아마도, 트리가 균형을 이룰 필요는 없으므로, 교체할 값을 빠르게 찾고 검색 또한 빨라지게 하기 위한 방법이 아닐까 싶다.

      2009.10.23 01:37 신고 [ ADDR : EDIT/ DEL ]
  14. 12

    잘 보고 갑니다 ^^ 스크랩 해갈게요

    2010.02.02 18:41 [ ADDR : EDIT/ DEL : REPLY ]
  15. 회사에서 일하다가 12년 전의 누나 블로그를 보고 가네요^^ 12년 전의 누나와 지금의 누나에게 감사를 표합니다~!! 잘 지내시죠?

    2016.08.05 07:47 신고 [ ADDR : EDIT/ DEL : REPLY ]