Ball Partitioning Methods

영역 분할을 하는데 사용하는 기존의 접근 방식에 대해 조사해보았다.

 

첫 번째로, Ball Partitioning에 대한 방법들을 알아보자.

 

---

Burkhard-Keller Tree (BKT)

BKT라고도 불린다.

 

특징으로는 다음 4가지가 있다.

- Applicable to discrete distance functions only : 이산적인 거리만 적용할 수 있다. 연속적인 거리는 안된다는 말.

- Recursively divides a given dataset X : 재귀적으로 주어진 데이터셋 X를 분할한다.

나머지 두 특징은 특수기호가 포함되어있어 이미지로 대체하였다.

 

위의 두 특징을 해석하자면, 임의의 점 pj로 부터 같은 거리에 위치한 점들을 Xi로 묶어 pj의 서브트리에 저장한다는 얘기이다.

 

BKT에 쿼리가 주어졌을 경우 처리 방법은 다음과 같다.

 

 

---

Fixed Queries Tree (FQT)

- BKT의 변형이다.

- 모든 level은 하나의 피봇을 갖는다. (모든 object들은 리프 노드에 저장된다)

- 검색을 하는동안 거리 계산이 저장된다.

 

왼쪽 그림과 같은 데이터셋을 트리 구조로 나타내면 오른쪽과 같아진다.

---

Fixed - Height FQT (FHFQT)

- Extension of FQT : FQT의 확장이다.

- All leaf nodes at the same level : 모든 리프 노드들이 같은 레밸에 위치한다.

- Extended tree depth does not typically introduce further computations : 트리의 깊이가 증가하는게 통상적으로 더 많은 계산을 요구하는 것은 아니다.

 

 

FQT를 FHFQT로 변환하면 위 그림처럼 나타낼 수 있다.

같은 레벨의 리프노드에 모든 오브젝트들을 몰아 넣고, 그 외의 노드들은 pivot이 되는 것이다.

 

위에 트리를 보니, array를 사용하면 더 간단하게 데이터를 표현할 수 있을 것 같다는 생각이 든다.

그래서 등장한게 

FQA이다.

---

Fixed Queries Arrya (FQA)

- Based on FHFQT : FHFQT에 기반한다.

- An h-level tree is transformed to an array of paths : h-레벨의 트리를 경로의 배열로 변형한것이다.

   >Every leaf node is represented with a path from the root node

   >Each path is encoded as h values of distance

- A search algorithm turns to a binary search in array intervals

 

 

왼쪽의 FHFQT를 오른쪽에 FQA로 변형한 뒤의 그림이다.

---

Vantage Point Tree (VPT)

 

VPT도 마찬가지로 Ball partitioning을 이용하는 트리이다.

임의의 피봇 p를 고르고, median m을 계산한다.

p로부터 반지름 m을 가진 원을 기준으로 밖의 영역은 S2, 안의 영역은 S1이 된다.

 

 

한 개 이상의 오브잭트들이 리프 노드에 들어갈 수 있으며,

VP tree는 균형을 유지하는 이진 트리가 된다.

주의해야 할 점은, pivot p1, p2, p3도 피벗이기 이전에 하나의 데이터로서 데이터베이스 상에 존재한다는 점이다.