Ball Tree

knn(k-nearest neighbor) search에서 가까운 data point를 search하는 알고리즘이다.

1. 랜덤하게 하나의 point를 뽑는다.

2. Point 2개를 선정하고 ball을 그린다

랜덤한 포인트 p1(5,6)에서 가장 거리가 먼 p2(1,2) 선택 후 다시 한번 p2에서 가장 거리가 먼 포인트 p3(7,8)을 선택한다.
p2와 p3d를 이어 선을 만들고 해당 선에 중간 점을 기준으로 divide한다.
각 나누어진 선에 point들이 projection되고 점들의 축 성분에 합의 평균으로 새로운 centroid 점을 생성한다. centroid점의에서 가장 먼 point를 선택하여 해당 point간의 거리를 반지름으로 하는 ball을 그린다.

3. 재귀적인 방식으로 ball을 생성

생성된 ball안에서 재귀적으로 1번과 2번 작동흐름이 반복된다.

4. ball을 다 생성한 후 Tree를 그린다.

5. Input Data (8,5)가 속해져 있는 ball를 찾아 트리 노드search 후 가장 가까운 ball선택

6. 헤딩 ball에 있는 point중 가장 가까운 point 선택