SDBMS ⑥ The KD Tree

 

SDBMS 공간데이터베이스

 

⑥ The KD Tree

 

---

 

 

1. KD Tree

: $k$-d tree, $k$-dimentional tree

 

$k$차원의 점을 관리하는 이진 트리 구조이다.

트리의 모든 leaf는 $k$차원의 점이고 non-leaf는 공간을 나누는 hyperplane*이다.

* 본래 공간보다 한 차원 하위의 공간이라고 생각하면 될 듯. 3차원이라면 평면, 2차원이라면 선분 등 

기본적으로는 중앙값을 기준으로 점을 두 영역에 나누고, 또 중앙값을 기준으로 나누는 걸 반복해

leaf에 한 개의 점이 할당될 때까지 재귀적으로 트리를 빌드한다.

 

위 그림에서는 $x$를 기준으로 먼저 축을 골라 ①의 좌우로 점들을 나누고

다음 단계에서는 $y$를 기준으로 축을 골라 점을 나눴다.

다시 $x$, $y$, $x$, $y$ 순으로 공간을 나눠 위와 같은 트리를 만들었다.

 

$k$=3이라면 $x$, $y$, $z$, $x$, $y$, $z$... 순으로 축을 선택해 나눌 수 있다.

 

경우에 따라 축을 $x$, $x$, $y$, $y$ 순으로 고르는 등 variation이 가능하다.

중앙값 대신 평균을 사용할 수도 있고,

새로운 점 정보를 삽입하면서 node split을 할 수도 있다.

 

 

---

 

 

2. Query

Search(v,R) node v를 기준으로 region R에 속하는 점을 구하는 쿼리

Search(v,R) {
	if(v.isleaf)
		if(v.point IN R) res += { v.point }
	else
		if(Region(v) IN R) res += { all points in v }
		else
			if(Region(v.left) INTERSECT R) Search(v.left,R)
			if(Region(v.right) INTERSECT R) Search(v.right,R)

}

range, window query 모두 이런 식으로 재귀적으로 찾으면 된다.

 

 

 

---

1.

사실 강의에서 깊게 파고들었던 내용은 아니었다. 그래서인지 내용이 이정도뿐,,,

이해하기도 어렵지 않고 최근에 Segment Tree를 정리해서 그런가 비슷해보인다. (이진트리니까)

구현도 비슷하게 할 수 있을 것 같아 시도했지만 아직 완성하지 못했다..ㅎ

 

2.

파이썬 라이브러리 scikit-learn에 구현이 되어있어 NN 등을 처리할 때 쓸 수 있다.

구현은 파이썬 코드로 위키에도 나와있다.