K-d 트리는 K-dimensional tree로 K 차원 공간에서 데이터를 partitioning 하는 기법.

• 모든 노드가 K차원 데이터를 가짐.
• non-leaf 노드는 공간을 반으로 나누는 hyperplane을 생성.
• 트리 아래로 내려가면서 차원을 순환. (ex. 2차원 데이터가 있을 때, root node가 x축을 기준으로 나눈다면, 그 다음 노드들은 y축을 기준으로 나누고, 그 다음 노드들은 다시 x축을 기준으로 나눔)

Algorithm

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtree
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

from wiki

데이터가 $[(30, 40), (5, 25), (10, 12), (70, 70), (50, 30), (35, 45)]$ 이렇게 존재 한다면 아래와 같은 트리가 만들어진다.

Nearest Neighbor Search

K-d 트리로 부터 주어진 포인트와 가장 가까운 것을 찾아낼 수 있다.

1. root-node부터 recursive하게 아래로 내려간다.
2. leaf-node의 포인트와 주어진 포인트 사이의 거리를 계산하고 "current best"로 저장.
3. tree를 다시 거슬러 올라가며, 거리를 계산하고 current best를 업데이트한다.
    * 다른 plane에 더 가까운 포인트가 있을 수 있다. 그 점을 고려. 

자세한 내용