Booil Jung

동적 균형 k-d 트리

k-d 트리(k-dimensional tree)는 점, 선, 다각형 등 다차원 공간 데이터를 효율적으로 저장하고 검색하기 위해 설계된 핵심적인 공간 분할 자료구조다. 특히 3차원 포인트 클라우드 데이터의 최근접 이웃 탐색(Nearest Neighbor Search)이나 범위 탐색(Range Search)과 같은 기하학적 질의를 처리하는 데 널리 사용된다. 그러나 전통적인 k-d 트리는 데이터셋이 변경되지 않는 정적(static) 환경에 최적화되어 있다. 자율주행, 로보틱스, 실시간 3D 스캐닝 등 현대적 응용 분야에서는 데이터가 지속적으로 추가되거나 삭제되는 동적(dynamic) 환경이 일반적이며, 이러한 환경에서 정적 k-d 트리는 심각한 성능 저하 문제를 드러낸다. 본 보고서는 동적 환경에서 k-d 트리의 균형을 유지하기 위한 근본적인 문제점을 분석하고, 이를 해결하기 위한 핵심 알고리즘들과 최신 연구 동향을 심층적으로 고찰한다.

k-d 트리는 k-차원 공간의 점들을 효율적으로 정리하기 위한 이진 트리 기반의 공간 분할 자료구조다.1 각 비-리프 노드(non-leaf node)는 하나의 k-차원 점과 함께 분할 축(splitting axis)을 가지며, 이 축에 수직인 초평면(hyperplane)을 통해 현재 공간을 두 개의 하위 공간(half-space)으로 나눈다.1 이 과정을 재귀적으로 반복하여 공간을 세밀하게 분할하는 계층적 구조를 형성한다.2

정적 k-d 트리의 표준적인 구축 과정은 다음과 같은 단계로 이루어진다.

1. 분할 축 결정: 트리의 각 레벨에서 공간을 분할할 축을 선택한다. 가장 일반적인 방법은 데이터의 분산(variance)이 가장 큰 축을 선택하여 데이터가 넓게 퍼져 있는 방향으로 분할하는 것이다.3 이는 분할의 효율을 극대화하여 탐색 시 더 많은 영역을 가지치기(pruning)할 수 있도록 돕는다. 또 다른 간단한 방법은 x, y, z축을 순환(cycling)하며 차례대로 선택하는 것이다.1
2. 분할 점(Pivot) 결정: 선택된 축을 기준으로 현재 노드에 속한 점들을 정렬하고, 그중 중간값(median)에 해당하는 점을 분할 점으로 선택한다. 이 분할 점은 현재 노드에 저장된다. 중간값을 분할 점으로 사용하는 것은 생성될 두 서브트리가 거의 같은 수의 점을 갖도록 보장하며, 이는 최종적으로 생성되는 트리가 균형 잡힌(balanced) 형태를 갖게 하는 핵심적인 단계다.4
3. 재귀적 분할: 분할 점을 기준으로, 선택된 축의 좌표값이 분할 점보다 작은 점들은 왼쪽 서브트리로, 크거나 같은 점들은 오른쪽 서브트리로 보내어 두 개의 새로운 하위 집합을 만든다.3 이 두 하위 집합에 대해 다시 1단계부터의 과정을 재귀적으로 적용하여 트리를 완성한다.

중간값을 찾는 과정은 전체 점들을 정렬하는 $O(n \log n)$ 알고리즘을 사용하거나, 더 효율적인 $O(n)$ 시간 복잡도를 갖는 median-of-medians 알고리즘을 사용할 수 있다.1 따라서 $n$개의 점으로 균형 잡힌 정적 k-d 트리를 구축하는 전체 시간 복잡도는 최적의 경우 $O(n \log n)$이 된다.1

잘 구축된 k-d 트리는 다양한 공간 질의를 효율적으로 처리할 수 있다.

• 최근접 이웃(Nearest Neighbor, NN) 탐색: NN 탐색은 주어진 질의점(query point)에서 가장 가까운 점을 찾는 연산이다. 알고리즘은 먼저 일반적인 이진 탐색처럼 질의점이 속할 것으로 예상되는 리프 노드까지 하향식으로 탐색한다. 해당 리프 노드에 도달하면, 그 노드의 점을 현재까지의 최근접 이웃 후보로 설정하고 거리를 계산한다.5 이후, 트리 구조를 따라 상향식으로 되돌아오면서(backtracking) 각 노드를 방문한다. 이 과정에서, 현재까지 찾은 최근접 이웃과의 거리를 반지름으로 하는 초구(hypersphere)와 현재 노드의 분할 초평면이 교차하는지를 검사한다. 만약 교차한다면, 더 가까운 점이 반대편 서브트리에 존재할 가능성이 있으므로 아직 방문하지 않은 다른 자식 노드의 서브트리를 탐색한다. 만약 교차하지 않는다면, 반대편 서브트리 전체를 탐색에서 제외하여 효율적인 가지치기를 수행한다.5 균형 잡힌 트리에서 무작위로 분포된 점들에 대한 NN 탐색의 평균 시간 복잡도는

  $O(\log n)$이다.1

• 범위 탐색(Range Search): 범위 탐색은 주어진 직교 범위(axis-parallel range), 즉 각 축에 대한 최솟값과 최댓값으로 정의된 직사각형(2D) 또는 직육면체(3D) 내에 포함되는 모든 점을 찾는 연산이다. 탐색은 루트 노드부터 시작하여, 현재 노드가 나타내는 공간 영역이 질의 범위와 완전히 포함되는지, 부분적으로 겹치는지, 또는 전혀 겹치지 않는지를 판단하며 재귀적으로 진행된다. 겹치지 않는 노드의 서브트리는 탐색에서 제외된다.9 균형 잡힌 트리에서 범위 탐색의 시간 복잡도는 $O(n^{1-1/k} + m)$으로 알려져 있으며, 여기서 $k$는 차원의 수, $m$은 질의 범위 내에서 발견된 점의 수다.1

정적 환경에서의 뛰어난 성능과 달리, k-d 트리는 점의 삽입과 삭제가 빈번한 동적 환경에서 심각한 문제에 직면한다.

• 단순 삽입(Naive Insertion)과 불균형: 새로운 점을 삽입하는 가장 간단한 방법은 일반적인 이진 탐색 트리와 동일하다. 루트에서부터 시작하여 각 노드의 분할 기준에 따라 왼쪽 또는 오른쪽으로 이동하여 적절한 리프 노드를 찾고, 그 위치에 새로운 노드로 추가하는 것이다.1 이 방식은 매우 빠르지만, 삽입되는 점들의 공간적 분포나 순서에 따라 트리가 심각하게 불균형해질 수 있다.5 예를 들어, 데이터가 특정 축을 따라 단조롭게 증가하거나 감소하는 순서로 삽입된다면, 트리는 한쪽으로만 계속 성장하여 거의 연결 리스트(linked list)와 같은 편향된(skewed) 형태가 된다. 이 경우 트리의 높이가 $O(n)$에 가까워지고, 탐색 성능은 평균 $O(\log n)$에서 최악의 경우 $O(n)$으로 급격히 저하된다.5
• 단순 삭제(Naive Deletion)의 복잡성: 삭제할 노드가 리프 노드인 경우에는 간단히 제거할 수 있다. 그러나 내부 노드를 삭제하는 것은 훨씬 복잡하다. 일반적인 이진 탐색 트리에서는 삭제할 노드의 자식이 하나뿐이면 그 자식으로 대체하지만, k-d 트리에서는 이 방법이 불가능하다. 왜냐하면 부모 노드와 자식 노드는 서로 다른 축을 기준으로 공간을 분할하기 때문에, 단순한 대체는 k-d 트리의 핵심 불변성(invariant)인 ‘레벨에 따른 분할 축 순환’ 규칙을 깨뜨리기 때문이다.5 따라서 내부 노드를 삭제하려면 대체 노드를 신중하게 찾아야 한다. 일반적인 방법은 삭제할 노드($p$)의 분할 축과 동일한 축을 기준으로, $p$의 오른쪽 서브트리에서 최소값을 갖는 노드나 왼쪽 서브트리에서 최대값을 갖는 노드를 찾아 $p$의 위치로 옮기는 것이다. 그 후, 원래 위치에서 옮겨온 대체 노드를 재귀적으로 삭제하는 과정을 거쳐야 한다.5 이처럼 복잡한 과정은 트리의 지역적 구조를 변경하며 균형을 더욱 깨뜨릴 수 있다.
• 재균형의 근본적 한계: 이러한 불균형 문제를 해결하기 위해 AVL 트리나 Red-Black 트리에서 사용되는 트리 회전(tree rotation)과 같은 표준적인 재균형 기법을 k-d 트리에 적용할 수 없다. 회전 연산은 노드의 부모-자식 관계를 바꾸는데, 이는 k-d 트리의 다차원 정렬 불변성, 즉 각 레벨마다 특정 차원으로 공간을 분할한다는 규칙을 파괴하기 때문이다.1 이처럼 k-d 트리의 핵심 장점인 ‘다차원 공간 분할’이라는 특성이 역설적으로 동적 환경에서의 최대 약점인 ‘재균형의 어려움’을 야기한다. 이 근본적인 제약으로 인해, 동적 환경에서 k-d 트리의 균형을 유지하기 위해서는 전체 재구축을 피하면서도 효율적인, 보다 정교한 전략들이 필요하게 되었다.

k-d 트리의 동적 불균형 문제를 해결하기 위해, 트리 회전을 사용하지 않는 다양한 재균형 알고리즘이 제안되었다. 이들은 크게 부분 재구축 기법, 확률적 기법, 그리고 다른 자료구조와의 하이브리드 접근법으로 분류할 수 있다.

Scapegoat 트리는 동적 균형을 유지하기 위한 우아하고 실용적인 해법을 제시한다. AVL 트리나 Red-Black 트리처럼 모든 노드에 색상이나 가중치 같은 추가적인 균형 정보를 저장하는 대신, 전역 변수 몇 개와 ‘게으른(lazy)’ 재균형 전략을 사용하여 효율성을 달성한다.13

• 핵심 아이디어 및 α-가중치-균형: Scapegoat 트리의 핵심은 α-가중치-균형(α-weight-balanced)이라는 개념에 있다. 어떤 노드 x에 대해, 그 자식 노드 child의 서브트리 크기가 부모 노드 x의 서브트리 크기의 특정 비율 $\alpha$를 넘지 않을 때 균형이 유지된다고 본다. 즉, 다음 조건이 만족될 때 노드 x는 $\alpha$-가중치-균형을 만족한다 14: \(size(left) \le \alpha \cdot size(node)\)

  \[size(right) \le \alpha \cdot size(node)\]

  여기서 size()는 서브트리에 포함된 총 노드의 수를 의미하며, $\alpha$는 $0.5 < \alpha < 1$ 범위의 상수로, 트리의 균형도를 조절하는 역할을 한다. 이 조건은 트리의 전체 높이 $h(T)$가 $h(T) \le \log_{1/\alpha}(n)$에 가깝게, 즉 로그 스케일로 유지되도록 보장한다.

• 삽입 연산 및 희생양(Scapegoat) 탐색:

  1. 새로운 노드 u는 일반적인 이진 탐색 트리 방식과 동일하게 트리에 삽입된다.15
  2. 삽입 후, 트리 전체의 노드 수 n과 함께, 마지막으로 전체 재구축이 일어난 이후의 최대 노드 수를 기록하는 q라는 전역 변수를 갱신한다.
  3. 만약 새로 삽입된 노드 u의 깊이가 $log_{1/\alpha}(q)$를 초과하면, 이는 트리가 $\alpha$-높이-불균형 상태가 되었음을 의미하며 재균형 작업이 필요하다.15
  4. 재균형을 위해, 삽입된 노드 u에서부터 루트 방향으로 거슬러 올라가면서 처음으로 $\alpha$-가중치-균형 조건을 위반하는 조상 노드 w를 찾는다. 이 노드 w가 불균형의 원인이 된 ‘희생양(scapegoat)’이다.14
  5. 희생양 w를 루트로 하는 서브트리 전체를 해체하고, 해당 서브트리에 속한 모든 점들을 모아서 완벽하게 균형 잡힌 새로운 k-d 트리를 재구축하여 원래 위치에 교체한다.14

• 삭제 연산: 삭제는 삽입보다 더 간단하게 처리될 수 있다. 노드를 일반적인 방식으로 삭제한 후, 전체 노드 수 n이 최대 노드 수 q의 $\alpha$ 배보다 작아지면 (즉, $n \le \alpha \cdot q$), 이는 삭제로 인해 트리에 너무 많은 공간이 낭비되고 있음을 의미한다. 이 경우, 트리 전체를 재구축하여 공간을 압축하고 q를 n으로 재설정한다.14

• 복잡도 분석: 희생양 서브트리를 재구축하는 비용은 해당 서브트리의 크기 $s$에 대해 $O(s \log s)$로 상당히 높다. 그러나 이러한 비싼 연산은 트리가 매우 불균형해졌을 때만 드물게 발생한다. 그전까지 수많은 삽입 연산은 재구축 없이 $O(\log n)$의 저렴한 비용으로 수행된다. 분할 상환 분석(amortized analysis)을 통해 이 비용을 전체 연산에 분산시키면, 삽입 및 삭제의 상각 시간 복잡도(amortized time complexity)는 $O(\log n)$이 된다. 탐색 연산은 재구조화 과정 없이 수행되므로 최악의 경우에도 $O(\log n)$의 시간 복잡도를 보장한다.13 이처럼 Scapegoat 알고리즘은 재균형 작업이 분할 상환 관점에서 ‘공짜(cost-free)’가 되는 개념을 통해, 추가적인 노드별 저장 공간 없이도 강력한 성능 보장을 제공하는 우아한 해법을 제시한다.13

Scapegoat 트리가 결정론적 규칙에 기반하여 최악의 경우 성능을 보장하는 반면, 무작위 k-d 트리는 확률적 기법을 도입하여 ‘평균적으로’ 또는 ‘기대되는’ 성능을 보장하는 데 초점을 맞춘다. 이는 특정 데이터 입력 순서나 분포로 인해 발생하는 최악의 성능 시나리오를 효과적으로 회피하는 전략이다.

• 알고리즘 (Split and Join 기반): Amalia Duch와 Conrado Martínez의 연구는 무작위 k-d 트리의 동적 업데이트를 위해 split과 join이라는 두 가지 기본 연산에 기반한 알고리즘을 제안했다.19 이 알고리즘들은 서브트리의 크기 정보를 활용하여 삽입 또는 삭제 지점을 무작위화한다. 이를 통해 업데이트 이후에도 트리가 무작위 k-d 트리(random k-d tree)가 갖는 통계적 속성을 그대로 유지하도록 보장한다. 즉, 트리의 구조가 특정 입력에 종속되지 않고 무작위 입력으로 생성된 트리와 유사한 형태를 띠게 된다.
• 기대 비용 분석: 해석적 조합론(analytic combinatorics)이라는 정교한 수학적 도구를 사용한 분석 결과, 이러한 무작위 업데이트 연산의 평균 비용이 정밀하게 밝혀졌다.19
  • 2차원 ($K=2$): 2차원 공간에서는 삽입 및 삭제 연산의 기대 비용(expected cost)이 $\Theta(\log n)$으로, 매우 효율적이다.
  • 고차원 ($K>2$): 그러나 2차원을 초과하는 고차원에서는 기대 비용이 $\Theta(n^{\phi(K)-1})$로 증가한다. 여기서 $\phi(K)$는 차원 $K$에 의존하는 함수로, $1 \le \phi(K) < 1.561552813$의 값을 갖는다.19 이는 차원이 높아질수록 업데이트 비용이 다항식적으로 증가하여 성능 저하가 발생할 수 있음을 시사한다. 이 분석은 k-d 트리가 고차원에서 겪는 근본적인 한계, 즉 ‘차원의 저주(curse of dimensionality)’가 동적 업데이트에서도 나타남을 보여준다.
• 다중 무작위 트리(Multiple Randomized Trees): 단일 k-d 트리는 고차원에서 탐색 공간을 효율적으로 가지치기하는 능력이 급격히 감소한다.9 이 문제를 완화하기 위한 실용적인 접근법으로, 동일한 데이터셋에 대해 여러 개의 독립적인 k-d 트리를 생성하는 기법이 제안되었다. 각 트리를 생성할 때 분할 축이나 분할 점을 무작위로 선택하여 서로 다른 구조를 갖도록 만든다. 최근접 이웃 탐색 시에는 이 모든 트리를 동시에 탐색하여 각 트리에서 찾은 후보들 중 가장 좋은 것을 최종 결과로 선택한다. 이는 독립적인 탐색 경로를 여러 개 가짐으로써, 제한된 수의 노드만 탐색하더라도 실제 최근접 이웃을 찾을 확률을 크게 높여준다.20 이 기법은 결정론적 보장을 포기하는 대신, 확률적으로 더 나은 성능과 강건성을 얻는 트레이드오프를 보여준다.

k-d 트리의 동적 균형 문제를 해결하기 위한 또 다른 접근법은 k-d 트리의 공간 분할 능력과 다른 자료구조의 장점을 결합하는 것이다. 특히 B-트리 계열과의 결합은 대용량 데이터베이스나 높은 업데이트 처리량이 요구되는 시스템 환경에서 주목받았다.

• K-D-B-트리: 이 자료구조는 데이터가 주로 보조 기억장치(디스크)에 저장되는 대용량 데이터베이스 환경을 위해 특별히 설계되었다. K-D-B-트리의 목표는 k-d 트리의 효율적인 다차원 탐색 능력과, B-트리의 뛰어난 I/O 효율성(디스크 페이지 단위로 데이터를 읽고 쓰는 능력)을 동시에 달성하는 것이다.21
  • 구조: B-트리처럼 다분(multi-way) 트리 구조를 가지며, 모든 리프 노드가 동일한 레벨에 위치하여 균형을 유지한다. 내부 노드는 k-d 트리처럼 공간을 분할한 영역(region)들과 해당 영역을 담당하는 자식 페이지의 ID 쌍을 저장한다. 실제 데이터 포인트들은 리프 노드인 ‘포인트 페이지(point page)’에 저장된다.21
  • 연산 및 한계: 삽입으로 인해 페이지가 가득 차면(overflow) 노드 분할이 일어난다. 그러나 이 분할 과정이 B-트리처럼 국소적으로 끝나지 않고, k-d 트리의 분할 방식 때문에 하위 트리로 연쇄적인 분할이 전파될 수 있어 매우 복잡하다.12 또한, 삭제로 인한 언더플로우(underflow)를 처리하기 위한 재조직(reorganization) 메커니즘은 B-트리의 병합/재분배 연산보다 훨씬 복잡하여, 초기 연구 이후 실제 구현 및 상용화에 어려움을 겪었다.21
• Bkd-트리 및 로그 구조화 기법(Logarithmic Method): 이 기법은 정적 자료구조를 동적으로 만드는 고전적인 방법론을 k-d 트리에 적용한 것이다. 하나의 거대하고 복잡한 동적 트리를 관리하는 대신, 여러 개의 작고 관리하기 쉬운 정적 트리들의 집합으로 문제를 분해한다.
  • 핵심 아이디어: 크기가 지수적으로 증가하는 여러 개의 완벽하게 균형 잡힌 정적 k-d 트리들의 집합($T_0, T_1, T_2,…$)을 유지한다. 예를 들어, $T_i$는 $2^i$개의 점을 저장할 수 있다.12
  • 삽입: 새로운 점들은 작은 버퍼나 가장 작은 트리($T_0$)에 먼저 삽입된다. 이 트리가 가득 차면, 같은 크기를 가진 다른 트리와 병합하여 모든 점들을 모아 한 단계 더 큰 크기의 트리($T_1$)를 완전히 새로 생성한다. 이 과정은 마치 이진수 덧셈의 자리 올림(carry) 연산처럼 상위 레벨로 연쇄적으로 일어날 수 있다.
  • 탐색: 질의가 들어오면, 유지하고 있는 모든 트리($T_0, T_1,…$)를 각각 독립적으로 탐색하고, 각 트리에서 얻은 결과를 취합하여 최종 결과를 도출해야 한다. 이로 인해 단일 트리를 탐색할 때보다 $O(\log n)$ 배 만큼의 오버헤드가 발생할 수 있다.22
  • 장점과 단점: 이 구조의 가장 큰 장점은 업데이트, 특히 배치(batch) 단위 업데이트가 매우 효율적이라는 점이다. 재구축이 전역적으로 일어나지 않고 일부 트리에 국한되며, 각 트리에 대한 작업이 독립적이므로 병렬화에 매우 용이하다.22 반면, 질의 성능이 저하될 수 있다는 명확한 단점을 가진다. 이는 ‘업데이트 처리량’과 ‘질의 응답 속도’ 사이의 명확한 트레이드오프를 보여주는 사례다.

이러한 하이브리드 접근법들은 ‘최고의’ 동적 k-d 트리란 존재하지 않으며, 애플리케이션의 특정 제약 조건(메모리, I/O, 업데이트 빈도, 동시성 요구사항)에 따라 최적의 구조가 달라짐을 명확히 보여준다.

동적 포인트 클라우드를 처리하기 위한 자료구조 선택 시, k-d 트리 외에도 여러 대안이 존재한다. 각 자료구조는 공간을 분할하고 관리하는 방식에 있어 고유한 철학과 장단점을 가지므로, 애플리케이션의 요구사항에 맞는 최적의 구조를 선택하기 위해서는 이들 간의 비교 분석이 필수적이다.

k-d 트리와 Octree는 포인트 클라우드 인덱싱에 가장 널리 사용되는 두 가지 공간 분할 트리지만, 근본적인 분할 전략에서 차이를 보인다.

• 공간 분할 방식: k-d 트리는 ‘데이터 기반(data-driven)’ 분할 방식을 사용한다. 즉, 분할 경계가 데이터 포인트들의 중간값(median)에 의해 결정되므로, 데이터의 분포에 따라 분할선(2D)이나 분할면(3D)의 위치가 유동적으로 변한다.3 반면, Octree는 ‘고정 공간(fixed-space)’ 분할 방식을 채택한다. 데이터 분포와는 무관하게 항상 현재 공간의 중심을 기준으로 공간을 8개의 동일한 크기를 갖는 정육면체 하위 공간(octant)으로 균등하게 나눈다.24
• 데이터 분포 민감도: 이 분할 방식의 차이는 데이터 분포에 대한 민감도로 이어진다. k-d 트리는 데이터 분포에 적응적으로 분할하므로, 데이터가 특정 영역에 치우쳐 있는 불균일한 분포에서도 비교적 균형 잡힌 트리를 생성하는 경향이 있다. 반면, Octree는 데이터가 한쪽으로 심하게 몰려 있을 경우, 데이터가 없는 많은 수의 빈 노드가 생성되거나 데이터가 밀집된 영역에서만 트리가 매우 깊어지는 심각한 불균형 상태에 빠질 수 있다.24
• 구축 및 탐색 성능: Octree는 분할 위치를 결정하기 위해 중간값을 계산할 필요가 없으므로, 구축 속도가 일반적으로 k-d 트리보다 빠르다. Octree의 구축 시간 복잡도는 트리의 깊이를 $d$, 점의 개수를 $N$이라 할 때 $O(dN)$인 반면, k-d 트리는 $O(N \log N)$이다.25 그러나 탐색 성능은 데이터 분포에 따라 크게 달라질 수 있다. 데이터가 균일하게 분포되어 있다면 Octree는 좋은 성능을 보이지만, 불균형이 심한 경우 비효율적인 탐색 경로를 유발할 수 있다.24

R-트리는 k-d 트리와 함께 다차원 인덱싱의 양대 산맥으로 불리며, 특히 동적 데이터베이스 시스템에서 널리 사용된다.

• 핵심 차이점: 가장 근본적인 차이는 R-트리가 최소 경계 사각형(Minimum Bounding Rectangle, MBR)과 같은 영역(region) 데이터를 직접 저장할 수 있다는 점이다.26 또한, k-d 트리는 공간 전체를 겹침 없이 분할하는 ‘공간 분할(space-partitioning)’ 방식인 반면, R-트리는 각 노드가 표현하는 경계 상자들이 서로 겹치는 것을 허용하는 ‘데이터 분할(data-partitioning)’ 방식을 사용한다.26
• 동적 업데이트 강건성: R-트리는 B-트리를 다차원으로 확장한 개념에 기반하므로, 삽입 및 삭제 시 발생하는 노드 분할 및 병합 알고리즘이 잘 정립되어 있다. 이 덕분에 R-트리는 동적인 데이터 변경에 매우 강건하며, 트리의 균형을 항상 유지할 수 있다. 이러한 특성 때문에 R-트리는 변경이 잦은 데이터베이스의 공간 인덱스로 선호되는 경향이 있다.26 반면, 앞서 논의된 바와 같이 k-d 트리는 재균형이 본질적으로 어렵다.12
• 탐색 성능과 R*-트리: R-트리의 노드 중첩은 탐색 시 하나의 질의에 대해 여러 개의 하위 경로를 모두 탐색해야 할 가능성을 높여 성능 저하의 주요 원인이 될 수 있다. 이 문제를 개선하기 위해 등장한 것이 R-트리다. R-트리는 노드를 분할할 때 단순히 면적뿐만 아니라, 중첩 영역(overlap), 둘레(margin) 등을 종합적으로 최소화하는 정교한 휴리스틱을 사용하여 R-트리보다 훨씬 우수한 탐색 성능을 보인다.24
• 구현 복잡도: 일반적으로 k-d 트리는 분할 규칙이 단순하여 R-트리 계열보다 개념적으로 이해하고 메모리 내에 구현하기가 비교적 용이하다는 장점을 가진다.26

어떤 단일 자료구조도 모든 시나리오에서 최적의 성능을 보장할 수 없다는 인식 하에, 여러 구조의 장점을 결합하여 단점을 보완하려는 하이브리드(hybrid) 방식이 활발히 연구되고 있다.

• Octree + 3D R*-tree: 대규모 포인트 클라우드 처리를 위한 한 연구에서는 상위 레벨에서 Octree를 사용하여 전체 공간을 빠르게 대규모로 분할하고, Octree의 각 리프 노드 내에 포함된 점들에 대해서는 동적 균형 유지와 효율적인 쿼리에 강점을 가진 3D R-트리를 구축하는 방식을 제안했다. 실험 결과, 이 하이브리드 구조는 3D R-트리보다 훨씬 빠른 구축 시간(Octree의 장점)과, Octree 및 3D R-트리 단독 방식보다 우수한 k-NN 탐색 시간(R-트리의 장점)을 동시에 달성했다.24
• KD-octree: 또 다른 예시로, 먼저 k-d 트리를 사용하여 데이터를 비교적 균형 잡히게 분할한 후, 각 리프 노드에서 Octree를 구축하는 방식이 있다. 이는 k-d 트리가 너무 깊어지는 것을 방지하면서도 데이터 분포에 어느 정도 적응적인 분할을 가능하게 하려는 시도다.24

이러한 하이브리드 구조의 등장은 특정 애플리케이션의 요구사항에 맞춰 자료구조를 ‘설계’하고 ‘조합’하는 방향으로 연구가 발전하고 있음을 보여준다.

아래 표는 개발자와 연구자가 자신의 애플리케이션 요구사항(데이터의 정적/동적 여부, 데이터 타입, 성능 우선순위 등)에 가장 적합한 자료구조를 신속하게 판단할 수 있도록 핵심적인 트레이드오프를 요약하여 정리한 것이다.

자료구조	공간 분할 방식	균형 유지	동적 업데이트 효율성	저장 데이터	주요 장/단점
k-d Tree	데이터 기반 분할 (겹침 없음)	정적 구축 시 보장, 동적 시 어려움 (별도 알고리즘 필요)	낮음 (재균형 비용 높음)	점(Point)	장: 구현 용이, 균일 분포 데이터에 효율적. 단: 동적 데이터에 취약, 차원의 저주.
Octree	고정 공간 분할 (겹침 없음)	데이터 분포에 따라 불균형 발생 가능	중간 (구조가 고정되어 삽입/삭제 용이)	점(Point)	장: 구축 빠름, 구조 단순. 단: 불균일 데이터에 불균형 심화, 메모리 비효율.
R-Tree / R*-Tree	데이터 기반 분할 (겹침 허용)	B-트리 기반으로 항상 균형 유지	높음	영역(Region) 및 점	장: 동적 데이터에 매우 강건, 영역 데이터 저장 가능. 단: 노드 중첩으로 탐색 비효율 가능(R*-tree로 개선).
Ball Tree	데이터 기반 분할 (겹침 허용)	구축 시 균형 보장	중간 (재균형 가능)	점(Point)	장: 고차원 데이터 및 비유클리드 거리 척도에 강함. 단: k-d 트리보다 노드당 계산 비용 높음.

데이터의 규모가 폭발적으로 증가하고 멀티코어 프로세서, PIM(Processing-in-Memory)과 같은 새로운 하드웨어 아키텍처가 등장함에 따라, k-d 트리 역시 이러한 고성능 컴퓨팅 환경에 맞춰 진화하고 있다. 연구의 초점은 알고리즘의 병렬성을 극대화하고 메모리 계층 구조 및 데이터 이동 비용을 최적화하는 방향으로 이동하고 있다.

멀티코어 프로세서의 보편화는 k-d 트리의 구축 및 업데이트와 같은 순차적인 연산을 병렬화하여 대규모 데이터셋을 고속으로 처리하려는 강력한 동기를 부여했다.23 Pkd-tree는 이러한 요구에 부응하여 높은 병렬성과 캐시 효율성을 동시에 달성하도록 설계된 병렬 k-d 트리 구현체다.

• 병렬 구축: 전통적인 순차적 구축 방식은 병렬화에 적합하지 않다. Pkd-tree는 이를 극복하기 위해 다음과 같은 혁신적인 기법을 사용한다.
  • 샘플링 기반 분할: 전체 데이터셋을 정렬하여 중간값을 찾는 대신, 훨씬 작은 크기의 무작위 샘플을 추출하여 분할 기준(splitter)을 근사적으로 결정한다. 이 방식을 통해 트리의 상위 여러 레벨($\lambda$ 레벨)에 대한 분할 기준들을 한 번에 결정하여 ‘스켈레톤 트리(skeleton tree)’를 구성할 수 있다. 이는 전체 데이터에 대한 반복적인 접근을 최소화하여 캐시 효율성과 병렬성을 크게 향상시킨다.23
  • 체질(Sieving) 알고리즘: 스켈레톤 트리에 의해 결정된 분할 기준들을 바탕으로, 전체 데이터셋의 모든 점들을 각자가 속해야 할 하위 공간(버킷)으로 단 한 번의 데이터 이동 패스(pass)를 통해 병렬적으로 재배치한다. 이 과정은 데이터 지역성(data locality)을 높이고 동기화 오버헤드를 줄이는 데 효과적이다.23
• 재구성 기반 배치 업데이트: Pkd-tree는 동적 업데이트를 위해 Scapegoat 트리와 유사하게 $\alpha$-가중치-균형을 유지하는 지연 재균형 전략을 채택한다.23
  • 업데이트는 개별적으로 처리되지 않고 배치(batch) 단위로 수집되어 한 번에 처리된다.
  • 배치 업데이트가 적용된 후, 트리를 순회하며 불균형이 발생한 서브트리를 식별한다.
  • 불균형이 발견되면, 해당 서브트리의 기존 점들과 새로 삽입/삭제될 점들을 모두 모아, 앞서 설명한 병렬 구축 알고리즘을 사용하여 해당 서브트리만 국소적으로(locally) 재구성한다.23
  • 이 접근법은 업데이트 연산의 대부분을 여러 서브트리에 대한 독립적인 병렬 작업으로 변환함으로써, 높은 처리량과 확장성을 달성한다.
• 이론적 성능 보장: Pkd-tree는 병렬 알고리즘의 성능을 평가하는 핵심 지표인 작업(Work, 총 연산량), 스팬(Span, 이상적인 병렬 머신에서의 실행 시간), 캐시 복잡도(Cache Complexity) 세 가지 측면 모두에서 강력한 이론적 성능 보장을 제공한다.23

아래 표는 병렬 컴퓨팅 전문가에게 가장 중요한 성능 지표들을 명시적으로 제시함으로써 Pkd-tree 알고리즘의 이론적 우수성을 정량적으로 보여준다. 이는 알고리즘의 확장성과 효율성을 평가하는 핵심적인 근거가 된다.

연산	Work (순차 실행 시간)	Span (병렬 실행 시간)	Cache Complexity
구축 (n개 점)	$O(n \log n)$	$O(\log^2 n)$ (높은 확률)	$O(\frac{n}{B} \log_M n)$
배치 업데이트 (m개 점)	$O(m \log^2 n)$ (상각)	$O(\log^2 n)$ (높은 확률)	$O(\frac{m}{B}(\log(n/m) + \log_M n))$ (상각)

주: $n$은 트리 크기, $m$은 배치 크기, $M$은 캐시 크기, $B$는 캐시 라인 크기를 의미한다.

데이터 집약적인 k-d 트리 연산의 성능은 종종 CPU의 연산 속도가 아닌, CPU와 메인 메모리 간의 데이터 전송 속도에 의해 제한된다. 이 ‘메모리 월(memory wall)’ 문제는 k-d 트리처럼 포인터 추적(pointer chasing)이 많은 자료구조에서 특히 심각하다. PIM(Processing-in-Memory)은 메모리 칩 내부에 연산 유닛을 통합하여 데이터 이동을 최소화함으로써 이 병목을 근본적으로 해결하려는 새로운 하드웨어 패러다임이다.30

• 설계 목표: PIM 환경에 최적화된 k-d 트리는 기존 알고리즘을 그대로 사용하는 것이 아니라, PIM 아키텍처의 특성을 최대한 활용하도록 재설계되어야 한다. 주요 설계 목표는 다음과 같다: (1) CPU와 PIM 모듈 간의 오프칩(off-chip) 통신 최소화, (2) 다수의 PIM 모듈 간의 작업 부하 균등 분배(로드 밸런싱), (3) 메타데이터 유지를 위한 업데이트 오버헤드 최소화.30
• 핵심 기술: PIM-k-d-tree는 이러한 목표를 달성하기 위해 다음과 같은 독창적인 기술들을 도입했다.
  • 로그-스타 트리 분해(Log-star Tree Decomposition): k-d 트리의 노드들을 높이가 아닌 서브트리의 크기를 기준으로 $O(\log^P)$개의 그룹으로 분해한다 ($P$는 PIM 모듈의 수). 각 그룹에 대해 서로 다른 캐싱 및 데이터 복제 전략을 적용하여, 루트에서 리프까지의 탐색 경로에서 발생하는 오프칩 통신 횟수를 이론적으로 $O(\log n)$에서 $O(\log^n)$으로 획기적으로 줄인다.30
  • 근사 확률 카운터(Approximate Probabilistic Counters): 트리의 균형 상태를 추적하기 위해 각 노드가 유지하는 서브트리 크기 카운터를 모든 업데이트마다 갱신하는 대신, $p = \log n / (\beta V)$ 와 같은 확률에 따라 갱신한다. 이를 통해 메타데이터 업데이트로 인한 통신 비용을 크게 줄이면서도 충분한 정확도를 유지한다.30
  • 지연된 업데이트 및 푸시-풀 검색(Push-Pull Search): 작업 부하가 특정 PIM 모듈에 집중되는 것을 막기 위해, 쿼리 배치의 크기에 따라 작업을 해당 PIM 모듈로 보내서 처리하거나(push), 필요한 노드 정보를 CPU로 가져와서(pull) 병렬 처리하는 동적 전략을 사용하여 로드 밸런스를 유지한다.30
• 성능 분석: PIM-k-d-tree는 배치 병렬 연산에 대해 작업량, PIM 시간, 통신 시간 등 여러 성능 지표에서 최적에 가까운 비용 경계(cost bounds)를 달성함을 이론적으로 증명했다.30 이는 k-d 트리 연구가 순수한 알고리즘 설계를 넘어, 하드웨어의 물리적 제약과 특성을 직접적으로 모델링하고 최적화하는 ‘하드웨어-인식(hardware-aware)’ 알고리즘 설계로 심화되고 있음을 보여주는 대표적인 사례다.

본 보고서는 포인트 클라우드 처리를 위한 동적 균형 k-d 트리의 근본적인 문제점부터 시작하여, 이를 해결하기 위한 고전적 및 현대적 알고리즘, 그리고 고성능 컴퓨팅 환경으로의 진화까지 다각도로 심층 분석했다. 분석을 통해 도출된 종합적인 결론과 향후 연구 방향은 다음과 같다.

분석 결과, 모든 시나리오에 적용 가능한 단일 최적해는 존재하지 않으며, 각 동적 균형 유지 기법은 고유한 장점과 트레이드오프를 가진다는 점이 명확해졌다.

• Scapegoat 트리: 구현이 비교적 간단하고 노드당 추가 메모리 오버헤드가 없으면서도, 탐색에 대한 최악 경우 $O(\log n)$과 업데이트에 대한 상각 $O(\log n)$이라는 강력한 이론적 성능을 보장한다. 이는 범용적인 인-메모리(in-memory) 동적 k-d 트리를 위한 훌륭한 기준선(baseline)이자 실용적인 선택지다.
• 무작위 트리: 결정론적 알고리즘이 취약할 수 있는 악의적인(adversarial) 입력 순서나 데이터 분포에 대한 강건성이 요구될 때 유용하다. 성능 보장이 확률적이지만, 평균적으로 우수한 성능을 기대할 수 있다.
• B-트리 하이브리드(K-D-B, Bkd): 외부 메모리(디스크) 환경에서 I/O 효율이 중요하거나, 배치 업데이트 처리량이 시스템의 핵심 성능 지표인 특정 데이터베이스 및 대규모 시스템 애플리케이션에 특화된 해결책이다. 질의 성능 저하를 감수하고 업데이트 효율을 극대화하는 명확한 트레이드오프를 보여준다.
• 병렬/PIM 트리: 수억 개 이상의 포인트를 다루는 대규모 데이터셋과 멀티코어, PIM과 같은 차세대 하드웨어 환경에서는 순차 알고리즘의 한계가 명확하다. Pkd-tree와 PIM-k-d-tree는 이러한 고성능 컴퓨팅 패러다임에서 k-d 트리가 생존하고 발전하기 위해 나아가야 할 필수적인 방향성을 제시한다.

자율주행 자동차의 LiDAR 센서, 로보틱스의 실시간 환경 인식, 3D 스캐너를 이용한 디지털 트윈 구축, 가상/증강 현실(VR/AR) 등 수많은 현대 기술 분야에서 포인트 클라우드 데이터는 정적인 스냅샷이 아니라, 실시간으로 생성되고 변화하는 동적인 스트림 형태를 띤다.31 이러한 동적 포인트 클라우드로부터 의미 있는 정보를 추출하기 위해서는 고속의 최근접 이웃 탐색, 충돌 감지를 위한 범위 탐색, 객체 추적을 위한 움직임 추정 등이 필수적이다.31 동적 균형 k-d 트리는 이러한 핵심적인 공간 질의 연산을 효율적으로 지원하는 기반 기술로서, 해당 응용 분야 전체의 성능과 실시간성을 좌우하는 매우 중요한 구성 요소라 할 수 있다.

동적 k-d 트리에 대한 연구는 앞으로도 다음과 같은 방향으로 더욱 발전할 것으로 전망된다.

• 딥러닝과의 결합: PointNet과 같은 딥러닝 모델은 포인트 클라우드 데이터의 복잡한 기하학적, 의미론적 특징을 학습할 수 있다.32 이러한 신경망을 사용하여 데이터의 잠재적 분포나 중요도를 학습하고, 이를 k-d 트리의 분할 축 및 분할 점 선택 전략에 반영하여 보다 의미론적으로 효율적인 트리를 구축하는 연구가 가능하다.
• 하드웨어 가속의 심화: GPU나 FPGA와 같은 대규모 병렬 처리 장치의 아키텍처에 더욱 특화된 k-d 트리 탐색 및 업데이트 알고리즘에 대한 연구가 계속될 것이다. 특히 GPU의 SIMT(Single Instruction, Multiple Threads) 모델에 최적화된 스택 없는(stack-less) 탐색 알고리즘의 동적 확장 등이 유망한 연구 주제다.35
• 근사 탐색의 고도화: 많은 실시간 응용에서는 완벽하게 정확한 최근접 이웃 대신, 약간의 오차를 허용하는 근사 최근접 이웃(Approximate Nearest Neighbor, ANN)으로도 충분하다. 동적 환경에서 트리의 균형을 효율적으로 유지하면서도, 빠르고 정확도 높은 ANN 탐색을 보장하는 k-d 트리 변종에 대한 연구가 더욱 활발해질 것이다.
• 압축 기술과의 통합: 대용량 동적 포인트 클라우드는 저장 및 전송을 위해 압축이 필수적이다. MPEG의 V-PCC(Video-based Point Cloud Compression)와 같은 표준 압축 기술과 동적 k-d 트리를 통합하여, 압축된 데이터 스트림 위에서 직접 공간 질의를 수행하거나 스트리밍 환경에 최적화된 새로운 동적 데이터 구조에 대한 연구가 필요하다.31

1. k-d tree - Wikipedia, 8월 1, 2025에 액세스, https://en.wikipedia.org/wiki/K-d_tree
2. Point cloud :: KdTree와 KNN - 당황했습니까 휴먼? - 티스토리, 8월 1, 2025에 액세스, https://ropiens.tistory.com/128
3. [영상처리] 이미지매칭(3) - Nearest Neighbor Search (with kd-tree) - LTNS - 티스토리, 8월 1, 2025에 액세스, https://kimyo-s.tistory.com/54
4. The Ultimate Guide to K-D Trees in ML - Number Analytics, 8월 1, 2025에 액세스, https://www.numberanalytics.com/blog/ultimate-guide-to-k-d-trees-in-ml

5. Introduction to K-D Trees

   Baeldung on Computer Science, 8월 1, 2025에 액세스, https://www.baeldung.com/cs/k-d-trees

6. Search and Insertion in K Dimensional tree - GeeksforGeeks, 8월 1, 2025에 액세스, https://www.geeksforgeeks.org/dsa/search-and-insertion-in-k-dimensional-tree/
7. Balancing KD-Tree: Which approach is more efficient? - Stack Overflow, 8월 1, 2025에 액세스, https://stackoverflow.com/questions/17021379/balancing-kd-tree-which-approach-is-more-efficient
8. User:Duyn/kd-tree Tutorial - Robowiki, 8월 1, 2025에 액세스, https://robowiki.net/wiki/User:Duyn/kd-tree_Tutorial
9. Optimizing Search Strategies in k-d Trees - Stanford InfoLab, 8월 1, 2025에 액세스, http://infolab.stanford.edu/~nsample/pubs/samplehaines.pdf
10. sklearn.neighbors.KDTree complexity for building is not O(n(k+log(n)) #7687 - GitHub, 8월 1, 2025에 액세스, https://github.com/scikit-learn/scikit-learn/issues/7687
11. Deletion in K Dimensional Tree - GeeksforGeeks, 8월 1, 2025에 액세스, https://www.geeksforgeeks.org/dsa/deletion-in-k-dimensional-tree/
12. Bkd-Tree: A Dynamic Scalable kd-Tree - Duke Computer Science, 8월 1, 2025에 액세스, https://users.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf
13. Scapegoat Trees - akira.ruc.dk, 8월 1, 2025에 액세스, http://webhotel4.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/03/Galperin93.pdf
14. Scapegoat tree - Wikipedia, 8월 1, 2025에 액세스, https://en.wikipedia.org/wiki/Scapegoat_tree
15. 8 Scapegoat Trees - Open Data Structures, 8월 1, 2025에 액세스, https://opendatastructures.org/newhtml/ods/latex/scapegoat.html
16. Scapegoat tree - OpenGenus IQ, 8월 1, 2025에 액세스, https://iq.opengenus.org/scapegoat-tree/

17. Galperin93 Scapegoat Trees

    PDF

    Algorithms And Data Structures

    Theoretical Computer Science - Scribd, 8월 1, 2025에 액세스, https://www.scribd.com/document/473882781/Galperin93-Scapegoat-Trees

18. Mastering Scapegoat Trees in Data Structures - Number Analytics, 8월 1, 2025에 액세스, https://www.numberanalytics.com/blog/ultimate-guide-scapegoat-tree-data-structures
19. (PDF) Updating Relaxed K-d Trees - ResearchGate, 8월 1, 2025에 액세스, https://www.researchgate.net/publication/234784644_Updating_Relaxed_K-d_Trees
20. Optimised KD-trees for fast image descriptor matching, 8월 1, 2025에 액세스, https://users.cecs.anu.edu.au/~hartley/Papers/PDF/SilpaAnan:CVPR08.pdf
21. [PDF] The K-D-B-tree: a search structure for large multidimensional …, 8월 1, 2025에 액세스, https://www.semanticscholar.org/paper/The-K-D-B-tree%3A-a-search-structure-for-large-Robinson/541d44c37b6072a5e8073233ff89454be153e40d
22. Parallel Batch-Dynamic kd-trees - arXiv, 8월 1, 2025에 액세스, https://arxiv.org/pdf/2112.06188
23. Parallel kd-tree with Batch Updates - Computer Science and …, 8월 1, 2025에 액세스, https://www.cs.ucr.edu/~ygu/papers/SIGMOD25/kdtree.pdf
24. A Hybrid Spatial Indexing Structure of Massive Point Cloud Based …, 8월 1, 2025에 액세스, https://www.mdpi.com/2076-3417/11/20/9581
25. Efficient Radius Neighbor Search in Three-dimensional Point Clouds - Jens Behley, 8월 1, 2025에 액세스, https://jbehley.github.io/papers/behley2015icra.pdf
26. What is the difference between a KD-tree and a R-tree? - Stack Overflow, 8월 1, 2025에 액세스, https://stackoverflow.com/questions/4326332/what-is-the-difference-between-a-kd-tree-and-a-r-tree
27. A dive into spatial search algorithms : r/programming - Reddit, 8월 1, 2025에 액세스, https://www.reddit.com/r/programming/comments/67vqf3/a_dive_into_spatial_search_algorithms/
28. Fast kd-tree Construction with an Adaptive Error-Bounded Heuristic - ResearchGate, 8월 1, 2025에 액세스, https://www.researchgate.net/publication/224759149_Fast_kd-tree_Construction_with_an_Adaptive_Error-Bounded_Heuristic
29. Parallel kd-tree with Batch Updates - Computer Science and Engineering, 8월 1, 2025에 액세스, https://www.cs.ucr.edu/~zmen002/files/publication/pkd_full.pdf
30. Optimal Batch-Dynamic kd-trees for Processing … - Parallel Data Lab, 8월 1, 2025에 액세스, https://www.pdl.cmu.edu/PDL-FTP/associated/yzhao-SPAA-25.pdf
31. NTIS > 연구성과 상세검색 > 기술요약정보, 8월 1, 2025에 액세스, https://www.ntis.go.kr/outcomes/popup/srchTotlTechInfo.do?cmd=get_contents&rstId=TAI-2021-01311895031&returnURI=aHR0cHM6Ly93d3cubnRpcy5nby5rci9UaFNlYXJjaFRvdGFsTGlzdC5kbz9zZWFyY2hXb3JkPSVFRCU4MSVCNCVFQiU5RCVCQyVFQyU5QSVCMCVFQiU5MyU5Qw==&pageCode=TH_TOTAL_TECHTRAN_RST_DTL
32. [초록 읽기] PointNet (2017) - scone’s data - 티스토리, 8월 1, 2025에 액세스, https://callmescone.tistory.com/243
33. DPCD: A Quality Assessment Database for Dynamic Point Clouds - arXiv, 8월 1, 2025에 액세스, https://arxiv.org/html/2505.12431v1
34. A Dynamic 3D Point Cloud Dataset for Immersive Applications, 8월 1, 2025에 액세스, https://people.cs.nycu.edu.tw/~chuang/pubs/pdf/2023mmsys.pdf
35. GPU상에서 동작하는 Ray Tracing을 위한 효과적인 k-D tree 탐색 알고리즘 - RISS 검색 - 국내학술지논문 상세보기, 8월 1, 2025에 액세스, https://m.riss.kr/search/detail/DetailView.do?p_mat_type=1a0202e37d52c72d&control_no=a86619b2baf3d37effe0bdc3ef48d419
36. 동적 메쉬 생성을 위한 동적 포인트 클라우드의 효율적 변환 방법/최이현, 정종범, 류은석 - 미디어공학회, 8월 1, 2025에 액세스, https://www.kibme.org/resources/journal/20231010164521840.pdf
37. Three-Dimensional Point Cloud Applications, Datasets, and Compression Methodologies for Remote Sensing: A Meta-Survey - MDPI, 8월 1, 2025에 액세스, https://www.mdpi.com/1424-8220/25/6/1660