맨위로가기

K-d 트리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

K-d 트리는 각 노드가 k차원 점인 이진 트리이다. 공간을 분할하는 초평면을 암묵적으로 생성하며, 트리 내 각 노드는 k차원 중 하나와 연관되어 초평면에 수직이다. K-d 트리는 구축, 요소 추가, 제거, 균형 유지, 최근접 이웃 탐색, 범위 탐색 등 다양한 연산을 지원한다. 차원의 저주로 인해 고차원 공간에서 성능이 저하될 수 있으며, 다양한 변형과 오픈 소스 구현이 존재한다.

2. 비공식적 설명

''k''-d 트리는 모든 노드가 ''k''차원 점인 이진 트리이다.[2]

2. 1. 분할 초평면

k-d 트리는 모든 노드가 k차원 점인 이진 트리이다.[2] k-d 트리의 모든 비-리프(non-leaf) 노드는 공간을 두 개의 반공간으로 나누는 분할 초평면을 암시적으로 생성한다고 볼 수 있다. 이 초평면을 기준으로 왼쪽에 있는 점들은 해당 노드의 왼쪽 서브트리에 속하고, 오른쪽에 있는 점들은 오른쪽 서브트리에 속하게 된다.

초평면의 방향은 트리 내 각 노드마다 k개의 차원 중 하나와 연관되어 결정되며, 해당 차원의 축에 수직이다. 예를 들어, 특정 분할 기준으로 "x"축이 선택되었다면, 해당 노드의 "x" 값보다 작거나 같은 값을 가지는 모든 점들은 왼쪽 서브트리로, 큰 값을 가지는 모든 점들은 오른쪽 서브트리로 분류된다. 이때 분할 초평면은 해당 노드 점의 x 값에 위치하게 되며, 초평면의 법선 벡터는 x축 방향의 단위 벡터가 된다.[3]

3차원 k-d 트리의 예

3. 연산

''k''-d 트리에서는 데이터를 효율적으로 관리하고 검색하기 위한 여러 가지 기본 연산이 정의되어 있다. 주요 연산들은 다음과 같다.


  • 구축: ''k''-d 트리를 만드는 과정이다. 일반적으로 점들을 특정 축의 중앙값을 기준으로 반복적으로 나누어 균형 트리 형태를 만드는 것을 목표로 한다. 구축 방법은 다양하며, 트리의 균형과 성능에 영향을 미친다.
  • 요소 추가: 새로운 점을 이진 탐색 트리와 유사한 방식으로 트리에 삽입하는 연산이다. 트리를 따라 내려가 적절한 위치에 새 노드를 추가하지만, 이 과정에서 트리가 불균형해질 수 있다.
  • 요소 제거: 트리에서 특정 점을 삭제하는 연산이다. 점을 제거한 후에도 ''k''-d 트리의 구조적 속성을 유지해야 하며, 이를 위해 하위 트리를 재구성하거나 대체 점을 찾는 방법 등이 사용된다.
  • 균형: 점의 추가나 삭제로 인해 트리가 한쪽으로 치우쳐 성능이 저하되는 것을 막기 위해 트리의 균형을 맞추는 과정이다. 일반적인 트리 회전 기법은 사용할 수 없으며, 다양한 변형된 ''k''-d 트리 구조나 재균형 알고리즘이 사용된다.
  • 최근접 이웃 탐색: 주어진 검색 점과 가장 가까운 거리에 있는 점을 트리 내에서 효율적으로 찾는 핵심 연산이다. 트리의 공간 분할 구조를 활용하여 불필요한 탐색 영역을 제외함으로써 검색 속도를 높인다.
  • 범위 탐색: 특정 범위(예: 특정 좌표 값 범위) 안에 속하는 모든 점들을 찾는 연산이다. ''k''-d 트리는 각 노드에서 데이터 공간을 나누는 특성 때문에 범위 검색을 효율적으로 수행할 수 있다.

3. 1. 구축

''k''-d 트리를 구축하는 방법은 다양하며, 이는 분할 평면을 선택하는 여러 방법이 존재하기 때문이다. 표준적인 ''k''-d 트리 구축 방법은 다음과 같은 제약 조건을 따른다.[17]

  • 트리를 따라 내려가면서 분할 평면 선택에 사용되는 축을 순환시킨다. 예를 들어, 3차원 트리에서는 루트 노드가 ''x''축 정렬 평면을 가지고, 그 자식 노드들은 ''y''축, 손자 노드들은 ''z''축, 증손자 노드들은 다시 ''x''축 정렬 평면을 가지는 방식으로 진행된다.
  • 각 단계에서 점들은 해당 축 좌표의 중앙값을 기준으로 분할되어 서브트리에 배치된다. 이 방법은 알고리즘 시작 시 전체 ''n''개의 점 집합이 주어진다고 가정한다.


이 표준적인 방법을 사용하면 각 리프 노드가 루트로부터 비슷한 거리에 위치하는 균형 트리 형태의 ''k''-d 트리가 생성된다. 그러나 균형 트리가 모든 응용 프로그램에서 반드시 최적의 성능을 보장하는 것은 아니다.

중앙값을 반드시 선택해야 하는 것은 아니다. 중앙값을 선택하지 않으면 트리가 균형을 이루지 못할 수 있지만, 복잡한 O(n) 중앙값 찾기 알고리즘[13][14]이나 모든 점을 정렬하는 O(n\log(n)) 정렬 (힙 정렬, 병합 정렬 등)을 피할 수 있다. 실용적인 대안으로, 고정된 수의 점을 무작위로 선택하여 정렬한 뒤 그 중앙값을 분할 평면으로 사용하는 방법이 있다. 이 기법은 실제로 종종 잘 균형 잡힌 트리를 생성한다.

''n''개의 점 목록이 주어지면, 중앙값 찾기를 이용해 균형 ''k''-d 트리를 구축하는 알고리즘은 다음과 같은 의사 코드로 표현될 수 있다.

'''function''' kdtree (''점 목록'' pointList, ''int'' depth)

{

''// 깊이에 따라 축을 선택하여 모든 유효한 값을 순환하게 합니다.''

'''var''' ''int'' axis := depth '''mod''' k;

''// 점 목록을 정렬하고 중앙값을 피벗 요소로 선택합니다.''

'''선택''' median '''by''' axis '''from''' pointList;

''// 노드를 생성하고 서브트리를 구성합니다.''

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;

}

일반적으로 중앙값 "이후(after)"의 점들은 현재 차원에서 중앙값보다 엄격하게 큰 점들만을 포함한다. 중앙값과 동일한 좌표를 가진 점의 처리 방식은 다양하며, 때로는 모든 차원을 비교하는 함수를 사용하거나, "미만"과 "이상 또는 같음"으로 나누는 방식처럼 한쪽에 포함시키기도 한다. 이 알고리즘은 모든 노드에 대해 왼쪽 서브트리의 모든 점은 분할 평면의 한쪽에, 오른쪽 서브트리의 모든 점은 다른 쪽에 위치한다는 불변량을 만족시킨다. 분할 평면 자체에 놓인 점은 양쪽 서브트리 중 어느 한쪽에 나타날 수 있다.

균형 ''k''-d 트리를 구축하는 다른 접근 방식은 데이터를 미리 정렬하는 것이다. 이 방법은 트리 구축 전에 데이터를 사전 정렬한 뒤, 구축 과정에서 이 정렬 순서를 유지함으로써 각 분할 단계에서 비용이 많이 드는 중앙값 찾기 과정을 생략한다. 예를 들어, 3차원 컴퓨터 그래픽스의 광선 추적 성능을 개선하기 위해 삼각형들을 정렬하는 균형 ''k''-d 트리를 구축하는 알고리즘들이 이 방식을 사용하며, 사전 정렬 후 최상의 경우 O(n\log n) 시간에 트리를 구축할 수 있다.[4][5] 점들을 정렬하여 균형 ''k''-d 트리를 구축하는 알고리즘의 경우, 먼저 ''k''개 차원 각각에 대해 ''n''개의 점을 O(n\log(n)) 정렬(힙 정렬 또는 병합 정렬 사용)하여 사전 정렬한다. 그런 다음 트리 구축 중에 이 ''k''개의 정렬된 순서를 유지하여 중앙값 찾기를 피하며, 이 알고리즘의 전체 복잡도는 최악의 경우 O(kn\log(n))이다.[6][7]

3. 2. 요소 추가

새로운 점을 k-d 트리에 추가하는 것은 다른 이진 탐색 트리에 요소를 추가하는 방식과 유사하다. 먼저, 루트 노드에서 시작하여 트리를 따라 내려간다. 각 노드에서는 현재 분할 기준이 되는 축과 비교하여, 추가하려는 점이 분할 평면을 기준으로 "왼쪽"에 속하는지 "오른쪽"에 속하는지에 따라 왼쪽 또는 오른쪽 자식 노드로 이동한다. 이 과정을 반복하여 더 이상 내려갈 자식 노드가 없는 리프 노드에 도달하면, 해당 리프 노드의 분할 기준에 따라 새 점을 왼쪽 또는 오른쪽 자식으로 추가하여 새로운 리프 노드를 만든다.

점을 추가하는 이러한 방식은 트리가 한쪽으로 치우치는 불균형 상태를 유발할 수 있다. 트리가 불균형해지면 최근접 이웃 탐색과 같은 연산의 효율성이 떨어져 트리 전체의 성능이 저하될 수 있다. 성능 저하의 정도는 추가되는 점들의 공간적 분포나 기존 트리의 크기 대비 추가되는 점의 수 등 여러 요인에 따라 달라진다. 만약 트리의 불균형이 심해지면, 트리 균형에 의존하는 검색 성능을 회복하기 위해 트리를 재균형화하는 과정이 필요할 수 있다.

3. 3. 요소 제거

기존 k-d 트리에서 점을 제거하면서 트리의 불변성을 유지하는 가장 간단한 방법은, 제거 대상 노드의 자식 노드들과 잎 노드들로 이루어진 집합을 이용하여 해당 하위 트리를 다시 구축하는 것이다.[8] 이때 노드의 축과 피벗 값은 유지해야 한다.

다른 방법은 제거될 점을 대체할 다른 점을 찾는 것이다.[9]

# 제거하려는 점을 포함하는 노드 R을 찾는다.

# 만약 R이 잎 노드라면, 다른 대체 작업 없이 그냥 제거한다.

# R이 잎 노드가 아니라면, R을 루트로 하는 하위 트리 내에서 대체 점 p를 찾는다.

# R 노드에 저장된 점을 p로 교체한다.

# 이제 원래 p가 있던 위치에서 재귀적으로 p를 제거하는 과정을 반복한다.

대체 점 p를 찾는 방법은 다음과 같다. 만약 노드 R이 x 축을 기준으로 점들을 나누고 오른쪽 자식 노드를 가지고 있다면, 오른쪽 자식 노드를 루트로 하는 하위 트리에서 x 좌표값이 가장 작은 점을 p로 선택한다. 그렇지 않으면, 왼쪽 자식 노드를 루트로 하는 하위 트리에서 x 좌표값이 가장 큰 점을 p로 선택한다.

3. 4. 균형

''k''-d 트리를 균형 있게 유지하는 것은 여러 차원에 걸쳐 정렬되기 때문에 주의가 필요하다. 이러한 다차원 정렬 특성 때문에, 일반적인 트리 회전 기법을 사용하여 균형을 맞추려고 하면 불변성이 깨질 수 있어 사용할 수 없다.

균형 잡힌 ''k''-d 트리에는 여러 변형이 존재한다. 여기에는 분할된 ''k''-d 트리, 유사 ''k''-d 트리, K-D-B-트리, hB-트리, Bkd-트리 등이 포함된다. 이러한 변형 중 상당수는 적응형 k-d 트리의 형태를 띤다.

3. 5. 최근접 이웃 탐색 (Nearest Neighbor Search)

2차원 트리에서 가장 가까운 이웃 검색의 예시. 각 노드는 사각형에 해당하며, 두 개의 동일한 하위 사각형으로 분할된다. 잎 노드는 단일 점을 포함하는 사각형이다.


가장 가까운 이웃 검색 (Nearest Neighbor Search, NN) 알고리즘은 주어진 입력점에 대해 트리 내에서 가장 가까운 점을 찾는 것을 목표로 한다. 이 검색은 ''k''-d 트리의 구조적 특징을 활용하여 검색 공간의 상당 부분을 효율적으로 제외함으로써 수행된다.

''k''-d 트리에서 가장 가까운 이웃을 찾는 과정은 다음과 같다.

1. 탐색은 트리의 루트 노드에서 시작한다. 알고리즘은 새로운 점을 트리에 삽입할 때와 동일한 방식으로 트리를 따라 재귀적으로 내려간다. 즉, 각 노드에서 분할 기준이 되는 차원의 값을 비교하여, 검색 지점이 현재 노드의 값보다 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 이동한다.

2. 알고리즘이 리프 노드에 도달하면, 해당 리프 노드에 저장된 점을 확인한다. 이 점과 검색 지점 사이의 거리가 현재까지 찾은 가장 가까운 거리("현재 최고" 거리)보다 짧으면, 이 점을 "현재 최고" 점으로 기록하고 거리를 갱신한다.

3. 알고리즘은 재귀 호출에서 복귀하며 상위 노드로 올라가는 과정에서 각 노드마다 다음 작업을 수행한다.

  • 현재 노드의 점이 "현재 최고" 점보다 검색 지점에 더 가깝다면, 현재 노드의 점을 새로운 "현재 최고" 점으로 갱신한다.
  • 현재 노드의 분할 평면을 기준으로, 검색 지점이 위치하지 않은 다른 쪽 부분 공간에 "현재 최고" 점보다 더 가까운 점이 존재할 가능성이 있는지 확인한다. 이는 개념적으로 검색 지점을 중심으로 하고 "현재 최고" 거리 값을 반지름으로 하는 초구(hyper-sphere)가 현재 노드의 분할 초평면(hyper-plane)과 교차하는지 검사하는 것과 같다. ''k''-d 트리의 분할 평면은 축에 정렬되어 있으므로, 이 검사는 검색 지점의 해당 분할 차원 좌표와 현재 노드의 분할 경계값 사이의 거리가 '현재 최고' 거리보다 작은지를 비교하는 간단한 연산으로 수행된다.
  • 만약 초구가 분할 평면과 교차한다면, 평면 건너편에 더 가까운 점이 존재할 수 있다. 따라서 알고리즘은 해당 노드의 다른 자식 노드를 루트로 하여 다시 재귀적인 탐색 과정을 수행한다.
  • 만약 초구가 분할 평면과 교차하지 않는다면, 평면 건너편의 모든 점들은 '현재 최고' 점보다 멀리 있음이 보장된다. 따라서 해당 하위 트리 전체를 탐색 대상에서 제외하고, 계속해서 상위 노드로 이동한다.

4. 알고리즘이 루트 노드까지 거슬러 올라와 위의 과정을 마치면 탐색이 완료되고, 최종적으로 기록된 "현재 최고" 점이 가장 가까운 이웃이 된다.

이 탐색 과정은 깊이 우선 탐색 방식으로도 설명할 수 있다. 루트에서 시작하여 검색 점이 포함된 영역(초직육면체)을 따라 리프 노드까지 내려간 후, 다시 부모 노드로 거슬러 올라오면서 탐색하지 않은 다른 쪽 영역을 검사한다. 이때, 검색 점을 중심으로 현재까지의 최단 거리를 반지름으로 하는 초구와 해당 영역(초직육면체)이 겹치는지 확인하여, 겹치지 않으면 해당 영역 전체를 탐색 대상에서 제외한다. 이 과정을 모든 영역이 탐색되거나 제외될 때까지 반복하며, 평균적인 시간 복잡도는 O(log N)이다.

일반적으로 알고리즘 구현 시, 거리 계산에 제곱근 연산을 피하기 위해 실제 거리 대신 제곱 거리를 사용하여 비교한다. 이를 위해 "현재 최고" 거리의 제곱 값을 변수에 저장해두면 계산 효율을 높일 수 있다.

이 기본 알고리즘은 몇 가지 방식으로 확장될 수 있다. 예를 들어, 가장 가까운 점 하나 대신 ''k''개의 가장 가까운 이웃(k-NN)을 찾으려면, 하나의 "현재 최고" 대신 ''k''개의 최고 점 목록을 유지하면 된다. 탐색 중 특정 분기(하위 트리)를 제외하는 조건은, 해당 분기 내에 현재까지 찾은 ''k''개의 점들 중 가장 먼 점보다 더 가까운 점이 존재할 가능성이 없을 때로 변경된다.

또한, 실행 속도를 높이기 위해 근사 최근접 이웃 탐색 (Approximate Nearest Neighbor Search) 알고리즘으로 변형할 수 있다. 예를 들어, 탐색 과정에서 방문하는 노드의 최대 개수를 제한하거나, 실시간 시스템 환경을 고려하여 정해진 시간 내에 탐색을 중단하는 방식이다(후자는 하드웨어 구현에 더 적합할 수 있다). 근사 탐색은 정확한 최근접 이웃을 보장하지는 않지만, 계산 시간을 크게 단축할 수 있어 특히 로봇 공학과 같이 실시간 응답이 중요한 응용 분야에서 유용하게 사용된다. 최적-빈-우선 검색 (Best-Bin-First Search)은 이러한 근사 탐색의 한 구현 예시이다.

만약 트리 내에 이미 존재하는 점과 동일한 위치의 점을 검색하는 경우, 거리가 0인 노드를 찾으면 더 이상 탐색을 진행하지 않도록 수정할 수 있다. 하지만 이 방식은 검색 지점과 정확히 동일한 위치에 여러 점이 존재하는 경우, 그중 하나만 찾고 나머지는 버리게 되는 단점이 있을 수 있다.

3. 6. 범위 탐색 (Range Search)

범위 검색은 특정 매개변수의 값 범위를 기준으로 데이터를 찾는 방법이다. 예를 들어, 어떤 데이터 구조(트리)가 사람들의 소득과 나이 정보를 저장하고 있을 때, '나이가 20세에서 50세 사이이고 소득이 50,000에서 80,000 사이인 모든 사람 찾기'와 같은 검색이 범위 검색에 해당한다. k-d 트리는 데이터를 구성할 때 각 단계(레벨)에서 특정 기준(차원)을 따라 데이터 공간(도메인)의 범위를 절반으로 나누어 나가기 때문에, 이러한 범위 검색을 효율적으로 수행하는 데 유용하다.

이진 검색 트리 분석을 통해, ''n''개의 노드를 가진 ''k''차원 k-d 트리에서 범위 검색을 수행할 때 가장 오래 걸리는 경우(최악의 시간 복잡도)는 다음 방정식으로 나타낼 수 있다는 것이 알려져 있다.[10]

:t_\text{최악} = O\left(k \cdot n^{1-\frac{1}{k}}\right)

4. 성능 저하

고차원 공간에서는 차원의 저주로 인해 k-d 트리의 탐색 성능이 크게 저하될 수 있다. 데이터의 차원 수 ''k''에 비해 점의 개수 ''n''이 충분히 많지 않다면, 즉 `n >> 2k` 조건을 만족하지 못하면, 트리를 탐색할 때 대부분의 점을 확인하게 되어 모든 점을 순차적으로 비교하는 전수 검색과 효율성 면에서 큰 차이가 없게 된다.[12][21] 이러한 이유로 고차원 데이터에서는 k-d 트리를 이용한 정확한 최근접 이웃 탐색보다는 근사 최근접 이웃 (Approximate Nearest Neighbor, ANN) 방법을 사용하는 것이 더 효율적일 수 있다. 고차원 데이터에서 정확한 최근접 이웃을 찾는 문제는 NP 난해 문제와 유사한 복잡도를 가지는 것으로 여겨진다.[21]

저차원 공간에서도 성능 저하가 발생할 수 있다. 질의점(query point)이 데이터 점들의 분포에서 멀리 떨어져 있어, 가장 가까운 몇몇 이웃들과의 거리가 거의 비슷해지는 경우가 그렇다. 이 경우, 가장 가까운 이웃을 찾기 위해 많은 점들을 확인해야 하므로 성능이 전수 검색 수준으로 나빠질 수 있다. 예를 들어, 모든 점이 원점을 중심으로 하는 구 표면에 분포되어 있다면, 원점에서 가장 가까운 점을 찾기 위해서는 사실상 모든 점을 확인해야 한다.

이러한 최악의 경우 성능 저하를 완화하기 위한 방법 중 하나로, 트리 검색 알고리즘 시 최대 거리(maximum distance) 매개변수를 사용하는 것이 있다. 탐색 과정에서 특정 영역(트리의 분기) 내에 있는 어떤 점도 이 최대 거리보다 가까울 수 없다고 판단되면, 해당 영역에 대한 추가 탐색을 중단(가지치기, pruning)한다. 하지만 이 방법을 사용하면 설정된 최대 거리 안에 이웃 점이 없는 경우, 최근접 이웃을 찾지 못하고 탐색이 종료될 수 있다.

5. 복잡도

''k''-d 트리의 여러 연산에 대한 시간 복잡도는 다음과 같다.


  • 정적 ''k''-d 트리 구축: ''n''개의 점으로부터 트리를 구축하는 시간 복잡도는 중앙값을 찾는 방법에 따라 달라진다.
  • 힙 정렬이나 합병 정렬과 같이 O(n log n)의 정렬 알고리즘을 사용하여 각 단계에서 중앙값을 찾는 경우: O(n log2 n)[22]
  • 선형 시간(O(n)) 중앙값 탐색 알고리즘(예: 중앙값의 중앙값)을 사용하는 경우: O(n log n)[13][14][22]
  • 트리 구축 전에 ''k''개 차원 각각에 대해 ''n''개의 점을 미리 O(n log n) 정렬하는 경우: O(kn log n)[7]
  • 점 삽입: 균형 잡힌 ''k''-d 트리에 새로운 점을 삽입하는 데 걸리는 시간은 O(log n)이다.
  • 점 제거: 균형 잡힌 ''k''-d 트리에서 점을 제거하는 데 걸리는 시간은 O(log n)이다.
  • 범위 탐색: 균형 잡힌 ''k''-d 트리에서 축에 평행한 범위 내의 점들을 찾는 데 걸리는 시간은 O(n1−1/k + m)이다. 여기서 ''m''은 보고된 점의 수이고, ''k''는 ''k''-d 트리의 차원이다.
  • 최근접 이웃 탐색: 임의로 분포된 점들로 구성된 균형 잡힌 ''k''-d 트리에서 가장 가까운 이웃 1개를 찾는 데 걸리는 시간은 평균적으로 O(log n)이다.

6. 변형

'''k'''-d 트리는 기본적인 구조 외에도 다양한 필요에 따라 변형된 형태로 활용된다. 예를 들어, 점 데이터뿐만 아니라 직사각형이나 초직사각형과 같은 체적 객체를 효율적으로 저장하고 검색하기 위한 변형이 존재한다. 또한, 트리의 구성 방식 자체를 변경하여 점을 잎 노드에만 저장하고 다른 분할 전략을 사용하는 변형도 연구되었다. 이러한 변형들은 특정 유형의 데이터나 연산에 더 최적화된 성능을 제공할 수 있다.

6. 1. 체적 객체 (Volumetric Objects)

''k''-d 트리는 점뿐만 아니라 직사각형이나 초직사각형과 같은 체적 객체를 저장하는 데에도 활용될 수 있다.[15][16] 이 경우, 범위 검색은 주어진 검색 범위(예: 검색 직사각형)와 겹치는 모든 직사각형 객체를 찾는 문제가 된다.

트리는 일반적으로 각 잎 노드가 하나의 직사각형에 해당하도록 구성된다. 직교 범위 검색 시에는 분할 기준이 되는 좌표축과 반대되는 검색 직사각형의 좌표값을 비교하여 탐색 효율을 높인다. 예를 들어, 현재 노드가 x축의 상한값(xhigh)을 기준으로 분할되었다면, 검색 직사각형의 x축 하한값(xlow)과 노드의 중앙값을 비교한다. 만약 중앙값이 검색 직사각형의 xlow 값보다 작다면, 해당 노드의 왼쪽 하위 트리에는 검색 직사각형과 겹치는 객체가 존재할 수 없으므로 더 이상 탐색하지 않고 가지치기(pruning)를 수행한다. 그렇지 않은 경우에는 양쪽 하위 트리를 모두 탐색해야 한다.

이러한 방식의 1차원 특수 사례로는 구간 트리가 있다.

6. 2. 잎에만 점 저장 (Points only in leaves)

점을 잎(leaf) 노드에만 저장하는 방식의 ''k''-d 트리도 정의할 수 있다.[17] 이 형태의 ''k''-d 트리는 표준적인 중간 분할 방식 외에도 다양한 분할 전략을 사용할 수 있다는 특징이 있다.

  • 중간점 분할 규칙[18]: 점의 실제 분포와 관계없이, 분할 대상 공간에서 가장 긴 축의 중간 지점을 기준으로 공간을 나눈다. 이 방식은 분할된 공간의 가로세로 비율(종횡비)이 최대 2:1을 넘지 않도록 보장하지만, 트리의 깊이는 점들의 분포에 따라 달라질 수 있다.
  • 슬라이딩 중간점 분할: 중간점 분할 규칙의 변형으로, 분할선의 양쪽에 점이 있는 경우에만 중간점을 기준으로 분할한다. 만약 한쪽에만 점이 있다면, 중간점에서 가장 가까운 점을 기준으로 분할 기준을 옮긴다(슬라이딩). Maneewongvatana와 Mount는 이 방식이 일반적인 데이터 집합에서 "충분히 좋은" 성능을 제공한다고 밝혔다.[17]


슬라이딩 중간점 분할 방식을 사용하면, 근사 최근접 이웃 탐색 쿼리는 O \left ( \tfrac{ 1 }{ { \epsilon\ }^d } \log n \right ) 시간 복잡도로 처리할 수 있다. 또한, 근사 범위 계산은 O \left ( \log n + { \left ( \tfrac{1}{ \epsilon\ } \right ) }^d \right ) 시간 복잡도로 수행 가능하다.

7. 오픈 소스 구현


  • ALGLIB는 ''k''-d 트리를 기반으로 하는 최근접 이웃 및 근사 최근접 이웃 알고리즘의 C# 및 C++ 구현을 제공한다.
  • CGAL(계산 기하학 알고리즘 라이브러리)는 ''k''-d 트리를 기반으로 하는 최근접 이웃, 근사 최근접 이웃 및 범위 검색 알고리즘을 구현한다.
  • SciPy는 과학 계산을 위한 파이썬 라이브러리이며, ''k''-d 트리를 기반으로 하는 최근접 이웃 검색 알고리즘을 구현한다.
  • scikit-learn은 머신 러닝을 위한 파이썬 라이브러리이며, 최근접 이웃 및 반경 이웃 검색을 지원하기 위해 ''k''-d 트리를 구현한다.

참조

[1] 웹사이트 k-dimensional https://xlinux.nist.[...] 2023-09-17
[2] 웹사이트 Introduction to K-D Trees https://www.baeldung[...] 2023-03-29
[3] 간행물 Multidimensional binary search trees used for associative searching
[4] 서적 2006 IEEE Symposium on Interactive Ray Tracing 2006-09
[5] 간행물 On improving k-d trees for ray shooting http://dcgi.felk.cvu[...] 2002
[6] 서적 Lecture Notes in Computer Science Springer-Verlag 2003
[7] 간행물 Building a balanced ''k''-d tree in {{math|O(''kn'' log ''n'')}} time http://jcgt.org/publ[...] 2015
[8] 웹사이트 Introduction to K-D Trees https://www.baeldung[...] 2023-03-29
[9] 문서 Introduction to kd-trees http://www.cs.umd.ed[...] University of Maryland Department of Computer Science
[10] 간행물 Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
[11] 간행물 An Algorithm for Finding Best Matches in Logarithmic Expected Time
[12] 서적 Handbook of Discrete and Computational Geometry CRC Press
[13] 간행물 Time bounds for selection http://people.csail.[...] 1973-08
[14] 문서 Introduction to Algorithms Chapter 10
[15] 간행물 Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries
[16] 간행물 Box Sort, a multidimensional binary sorting method for rectangular boxes, used for quick range searching
[17] 서적 Computational Geometry
[18] 문서 It's okay to be skinny, if your friends are fat https://graphics.sta[...] 4th Annual CGC Workshop on Computational Geometry 1999
[19] 서적 Computational Geometry: An Introduction Springer-Verlag 1985
[20] 서적 Computational Geometry: Algorithms and Applications Springer-Verlag 1997
[21] 문서 Nearest neighbors in high-dimensional spaces CRC Press 2004
[22] 서적 Introduction to Algorithms McGraw-Hill 1996


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com