kd-tree(k-Dimensional Tree, 이하 kd-tree)는 k차원의 유클리드 공간(Euclidean space)에 존재하는 점(point) 데이터를 효율적으로 조직화하고 검색하기 위해 설계된 공간 분할(Space Partitioning) 기반의 자료 구조이다.1 본질적으로 이는 컴퓨터 과학의 가장 기본적인 자료 구조 중 하나인 이진 탐색 트리(Binary Search Tree, BST)의 개념을 다차원 공간으로 확장하고 일반화한 것이다.3 각 노드가 k차원 공간상의 한 점을 나타내며, 트리의 각 레벨은 특정 차원 축에 수직인 초평면(hyperplane)을 기준으로 공간을 두 개의 하위 공간(subspace), 즉 반공간(half-space)으로 재귀적으로 분할하는 구조를 가진다.5
kd-tree의 핵심적인 의의는 다차원 데이터셋에 대한 두 가지 기본적이면서도 중요한 질의(query)를 효율적으로 처리하는 능력에 있다. 첫째는 특정 지점에서 가장 가까운 데이터 포인트를 찾는 최근접 이웃 탐색(Nearest Neighbor Search, NN Search)이며, 둘째는 주어진 범위 내에 포함되는 모든 데이터 포인트를 찾는 범위 질의(Range Query)이다.1 이러한 기능 덕분에 kd-tree는 컴퓨터 그래픽스, 머신러닝, 로보틱스, 공간 데이터베이스, 컴퓨터 비전 등 방대한 데이터를 신속하게 탐색해야 하는 수많은 응용 분야에서 핵심적인 역할을 수행한다.8
kd-tree의 가치는 단순히 다차원 검색이 가능하다는 사실을 넘어선다. 그 진정한 가치는 이진 탐색 트리라는 단순하고 이론적으로 우아한 모델을 다차원 공간이라는 복잡한 문제 영역에 적용하여 실용적이고 강력한 해결책을 제시했다는 데 있다. 이는 컴퓨터 과학 분야에서 잘 정립된 이론적 기반이 어떻게 복잡한 현실 세계의 문제를 해결하는 데 직접적으로 기여할 수 있는지를 보여주는 대표적인 사례로 평가받는다.
본 보고서는 kd-tree에 대한 포괄적이고 심층적인 고찰을 목표로 한다. 이를 위해 먼저 제2장에서 공간 분할이라는 핵심 원리를 탐구하고, 트리의 성능을 좌우하는 다양한 구축 알고리즘을 상세히 분석한다. 제3장에서는 데이터의 삽입 및 삭제와 같은 기본 연산의 메커니즘을 해부하며, 특히 삭제 연산의 복잡성이 시사하는 구조적 한계를 조명한다.
제4장에서는 kd-tree의 존재 이유라 할 수 있는 최근접 이웃 탐색과 범위 탐색 알고리즘의 작동 원리를 단계별로 분석하고, 탐색 공간을 효율적으로 축소하는 ‘가지치기(pruning)’ 기법을 집중적으로 다룬다. 제5장에서는 이러한 알고리즘들의 성능을 시간 및 공간 복잡도 관점에서 정량적으로 분석하고, 고차원 데이터에서 성능이 급격히 저하되는 ‘차원의 저주(Curse of Dimensionality)’ 현상과 동적 데이터 처리의 비효율성이라는 근본적인 한계를 탐구한다.
제6장에서는 표준 kd-tree의 한계를 극복하기 위해 제안된 Randomized kd-tree와 Adaptive kd-tree와 같은 주요 변형들을 소개하며, 이들이 어떠한 방식으로 문제에 접근하는지를 분석한다. 제7장에서는 R-tree, Ball Tree, Quadtree 등 다른 주요 공간 자료 구조와의 비교를 통해 kd-tree의 상대적인 장단점과 위상을 명확히 한다. 제8장에서는 머신러닝, 로보틱스, 컴퓨터 그래픽스, 데이터베이스 등 다양한 분야에서의 구체적인 활용 사례를 연구하여 이론이 실제 응용과 어떻게 연결되는지를 보인다. 마지막으로 제9장에서는 전체 논의를 종합하여 kd-tree의 핵심 가치와 한계를 요약하고, 현대 컴퓨팅 환경에서의 위상과 향후 연구 방향을 제시하며 보고서를 마무리한다.
kd-tree의 근간을 이루는 핵심 아이디어는 k차원 공간을 재귀적으로 이진 분할(Binary Space Partitioning)하는 것이다. 트리의 루트 노드는 전체 k차원 공간을 표현한다. 비-리프 노드(non-leaf node)는 각각 하나의 축에 정렬된(axis-aligned) 분할 초평면(splitting hyperplane)을 암시적으로 정의하며, 이 초평면은 해당 노드가 차지하는 공간 영역을 두 개의 서로소(disjoint)인 하위 공간, 즉 반공간(half-space)으로 나눈다.2 이렇게 나뉜 두 하위 공간은 각각 해당 노드의 왼쪽 자식과 오른쪽 자식에게 할당된다.
분할은 트리의 깊이(depth)에 따라 결정되는 특정 축을 기준으로 이루어진다. 가장 일반적인 방식은 차원 축을 순환적으로 선택하는 것이다. 즉, 트리의 깊이가 $d$이고 전체 데이터의 차원이 $k$일 때, 분할에 사용되는 축은 $(d \pmod k)$번째 축이 된다.1 예를 들어 3차원 공간($k=3$)이라면, 루트 노드(깊이 0)는 x축에 수직인 평면으로 공간을 분할하고, 그 자식 노드들(깊이 1)은 y축에 수직인 평면으로, 손자 노드들(깊이 2)은 z축에 수직인 평면으로 각자의 하위 공간을 분할한다. 그 다음 레벨에서는 다시 x축을 기준으로 분할을 시작한다.8 이 과정을 시각화하면, 3차원 공간이 처음에는 빨간색 수직 평면(x축 기준)으로 나뉘고, 생성된 두 개의 셀이 각각 초록색 수평 평면(y축 기준)으로 나뉘며, 결과적으로 생긴 네 개의 셀이 다시 파란색 수직 평면(z축 기준)으로 분할되는 모습을 상상할 수 있다.2 이 과정은 각 하위 공간에 하나의 데이터 포인트만 남을 때까지 반복된다.
kd-tree의 탐색 성능은 트리의 균형 상태에 크게 좌우된다. 트리가 한쪽으로 치우친 비균형 상태가 되면 탐색 경로가 길어져 성능이 저하될 수 있다.11 AVL 트리나 레드-블랙 트리와는 달리, kd-tree는 구조의 다차원적 제약으로 인해 회전(rotation)과 같은 효율적인 재균형(rebalancing) 연산을 적용하기 어렵다.12 따라서 초기 구축 단계에서 최대한 균형 잡힌 트리를 생성하는 것이 매우 중요하다. 균형 잡힌 트리를 구축하기 위한 알고리즘은 크게 ‘분할 축 선택 전략’과 ‘분할 기준점 선택 전략’의 조합으로 구성된다.
어떤 축을 기준으로 공간을 분할할지 결정하는 데에는 여러 전략이 존재하며, 각 전략은 구축 비용과 결과적인 트리 품질 간의 트레이드오프를 가진다.
분할 축이 결정되면, 해당 축 상의 어느 지점에서 공간을 나눌 것인지를 결정해야 한다. 트리의 균형을 맞추기 위한 가장 효과적인 전략은 현재 노드에 속한 데이터 포인트들을 선택된 분할 축의 좌표값을 기준으로 정렬한 뒤, 그 중앙값(median)을 분할 기준점으로 사용하는 것이다.6 중앙값을 기준으로 분할하면, 그 값보다 작은 점들의 집합과 크거나 같은 점들의 집합의 크기가 거의 동일해진다. 따라서 이 두 집합이 각각 왼쪽과 오른쪽 서브트리로 재귀적으로 할당될 때, 트리의 높이가 양쪽에서 균일하게 증가하여 전체적으로 균형 잡힌 구조를 유지하게 된다.11
중앙값을 찾는 과정은 전체 트리 구축 알고리즘의 시간 복잡도에 결정적인 영향을 미친다. 가장 직관적인 방법은 매 분할마다 해당 차원의 값들을 정렬하는 것으로, 이는 $O(n \log n)$의 시간을 필요로 한다.6 이 경우, 전체 트리 구축의 시간 복잡도는 $O(n \log^2 n)$이 된다. 보다 효율적인 방법으로, Blum 등이 제안한 ‘median of medians’ 알고리즘을 사용하면 정렬 없이 선형 시간, 즉 $O(n)$에 중앙값을 찾을 수 있다.12 이 방법을 적용하면 각 레벨의 모든 노드에 대한 분할이 총 $O(n)$ 시간에 이루어지므로, 전체 트리 구축 시간 복잡도를 $O(n \log n)$으로 단축할 수 있다.12
이러한 구축 전략의 선택은 근본적인 트레이드오프 관계를 보여준다. 한편에는 구축이 빠르지만 데이터 분포에 따라 품질이 저하될 수 있는 순환 방식이 있고, 다른 한편에는 높은 구축 비용을 감수하고서라도 항상 균형 잡힌 고품질의 트리를 생성하는 중앙값 기반 방식이 있다. 이 선택은 해당 kd-tree가 사용될 애플리케이션의 특성에 따라 달라진다. 예를 들어, 한 번 구축된 후 수많은 검색 질의를 처리하는 정적 데이터셋(예: 3D 렌더링)의 경우, 초기 구축 비용이 높더라도 탐색 성능이 뛰어난 균형 트리를 만드는 것이 전체적인 효율성 측면에서 유리하다. 반면, 데이터의 삽입과 삭제가 빈번한 동적 환경에서는 이러한 높은 구축 및 재구축 비용이 큰 부담으로 작용할 수 있다.
2차원 공간에 6개의 점 {(2,3), (4,7), (5,4), (8,1), (9,6), (7,2)}가 주어졌을 때, 중앙값을 이용한 kd-tree 구축 과정은 다음과 같다.6
(2,3), (4,7), (5,4), (7,2), (8,1), (9,6).(7,2)를 중앙값으로 선택하여 루트 노드로 삼는다.{(2,3), (4,7), (5,4)}는 왼쪽 서브트리로, 7보다 큰 점들 {(8,1), (9,6)}은 오른쪽 서브트리로 보낸다.{(2,3), (4,7), (5,4)}를 y좌표 기준으로 정렬한다: (2,3), (5,4), (4,7).(5,4)를 노드로 선택한다.(2,3)은 (5,4)의 왼쪽 자식이 되고, 5.4보다 큰 (4,7)은 오른쪽 자식이 된다. 이들은 모두 리프 노드가 된다.{(8,1), (9,6)}을 y좌표 기준으로 정렬한다: (8,1), (9,6).(9,6)을 노드로 선택한다.(8,1)은 (9,6)의 왼쪽 자식이 된다. 오른쪽 자식은 없다.이 과정을 통해 최종적으로 균형 잡힌 kd-tree가 구성된다. 각 노드는 공간을 분할하는 선을 암시하며, 전체 트리는 2차원 평면을 여러 개의 직사각형 영역으로 분할하는 구조를 형성한다.
kd-tree에 새로운 데이터 포인트를 삽입하는 연산은 이진 탐색 트리(BST)의 삽입 과정과 매우 유사한 원리를 따른다.3 연산은 트리의 루트에서 시작하여, 각 노드에서 현재 노드의 분할 축과 분할 값을 기준으로 새로 삽입할 포인트의 위치를 결정하며 재귀적으로 하강한다.
구체적인 과정은 다음과 같다. 삽입하려는 포인트를 p라 하고, 현재 방문 중인 노드를 v라고 하자. v의 깊이가 d이고 전체 차원이 k일 때, 비교에 사용될 축은 d mod k번째 축이다. p의 (d mod k)번째 좌표값과 v의 (d mod k)번째 좌표값을 비교한다. 만약 p의 값이 v의 값보다 작으면 왼쪽 자식 노드로 이동하고, 크거나 같으면 오른쪽 자식 노드로 이동한다.15 이 과정을 자식 노드가 없는 NULL 포인터에 도달할 때까지 반복하며, 해당 위치에 p를 저장하는 새로운 리프 노드를 생성하여 트리에 연결한다.
이처럼 kd-tree의 삽입은 BST의 원리를 다차원으로 확장한 것으로, 균형 잡힌 트리에서는 평균적으로 $O(\log n)$의 시간 복잡도를 가진다. 하지만 트리가 불균형할 경우, 최악의 경우에는 트리의 높이만큼 탐색해야 하므로 $O(n)$의 시간이 소요될 수 있다.
kd-tree에서의 데이터 삭제는 삽입보다 훨씬 복잡한 과정을 거치며, 삭제 대상 노드가 가진 자식의 수에 따라 처리 방식이 달라진다. 이 과정의 복잡성은 kd-tree가 동적 데이터 환경에 근본적으로 부적합함을 시사하는 중요한 지표가 된다.
Case 1: 삭제할 노드가 리프 노드인 경우
이 경우는 가장 간단하다. 해당 노드를 가리키는 부모 노드의 포인터를 NULL로 설정하여 트리에서 제거하기만 하면 된다.4
Case 2: 삭제할 노드가 하나의 자식만 갖는 경우
일부 구현에서는 이 경우를 두 개의 자식을 갖는 경우와 동일한 로직으로 처리하여 알고리즘을 단순화하기도 한다.4 근본적으로는 해당 노드를 제거하고 그 자리에 유일한 자식 서브트리를 연결하면 되지만, 이는 트리의 분할 축 규칙을 위반할 수 있어 더 복잡한 처리가 필요하다.
Case 3: 삭제할 노드가 두 개의 자식을 모두 갖는 경우
이 경우가 가장 복잡하며, 삭제 후에도 kd-tree의 구조적 속성을 유지하기 위해 대체 노드를 찾아야 한다. 과정은 다음과 같다.4
v의 분할 축(예: d mod k번째 축)을 확인한다.v의 오른쪽 서브트리에서, v와 동일한 분할 축을 기준으로 최소값을 갖는 노드를 찾는다. 이 노드를 대체 노드 r이라 한다. 만약 오른쪽 서브트리가 존재하지 않는다면, 왼쪽 서브트리에서 최대값을 갖는 노드를 찾아 r로 삼고, v의 왼쪽 자식을 오른쪽 자식으로 이동시키는 추가적인 구조 조정이 필요할 수 있다.5v의 위치에 대체 노드 r의 데이터 포인트를 복사한다.r이 있던 자리에서 r을 재귀적으로 삭제하는 과정을 수행한다. 이 재귀 호출은 다시 위의 세 가지 경우 중 하나에 해당하게 되며, 리프 노드 삭제에 도달할 때까지 연쇄적으로 발생할 수 있다.4이러한 삭제 알고리즘의 복잡성은 중요한 구조적 한계를 드러낸다. BST의 변형인 AVL 트리나 레드-블랙 트리는 삭제 연산 후 발생하는 불균형을 회전(rotation)과 같은 메커니즘을 통해 $O(\log n)$ 시간 내에 효율적으로 복구한다. 그러나 kd-tree에는 이러한 자가 균형 메커니즘이 부재하다. 삭제 과정에서 대체 노드를 찾는 것은 단순히 구조적 유효성을 유지하기 위한 절차일 뿐, 트리의 균형을 보장하지 않는다. 오히려 특정 패턴의 삭제가 반복될 경우, 트리는 한쪽으로 길게 늘어선 비효율적인 형태로 퇴화할 수 있다. 이러한 ‘불균형에 대한 취약성’은 kd-tree가 데이터 변경이 잦은 동적 데이터베이스 환경보다, 한 번 구축 후 주로 읽기 연산만 수행되는 정적 데이터셋의 인덱싱에 더 적합한 근본적인 이유가 된다.
kd-tree의 진정한 가치는 다차원 공간에서의 효율적인 탐색 능력에서 발현된다. 특히 최근접 이웃 탐색과 범위 탐색은 kd-tree를 활용하는 가장 대표적인 연산이며, 두 알고리즘 모두 ‘가지치기(pruning)’라는 기법을 통해 불필요한 탐색 공간을 제거함으로써 성능을 극대화한다.
NN 탐색은 주어진 질의점(query point) q에 대해 kd-tree에 저장된 모든 점들 중 유클리드 거리가 가장 가까운 점을 찾는 알고리즘이다. 이 과정은 단순히 트리를 따라 내려가는 것으로 끝나지 않고, 더 나은 해를 찾기 위해 되돌아 올라가는 백트래킹(backtracking) 과정을 포함하는 전역 최적해 탐색 문제이다.7
알고리즘은 다음과 같은 단계로 진행된다.
q를 트리에 삽입한다고 가정했을 때의 경로를 따라 루트 노드부터 리프 노드까지 내려간다. 이 과정은 각 노드의 분할 축과 값을 q의 해당 좌표값과 비교하며 진행된다. 최종적으로 도달한 리프 노드를 현재까지 가장 가까운 점, 즉 ‘현재 최적해(current best)’로 가정한다. 그리고 q와 이 점 사이의 거리를 계산하여 ‘최적 거리(best_dist)’로 저장한다.7v에 대해 다음 두 가지 검사를 수행한다.
q와 현재 노드 v의 점 사이의 거리를 계산한다. 만약 이 거리가 현재의 best_dist보다 작다면, v의 점을 새로운 최적해로 갱신하고 best_dist를 이 더 작은 거리로 업데이트한다.7v는 특정 축에 수직인 분할 평면(splitting hyperplane)을 기준으로 공간을 나눈다. 하향 탐색 과정에서는 이 평면의 한쪽으로만 진행했다. 이제 백트래킹 과정에서는 아직 방문하지 않은 ‘반대편 서브트리’에 현재의 최적해보다 더 가까운 점이 존재할 가능성이 있는지를 검사해야 한다.
q를 중심으로 하고 반지름이 best_dist인 초구(hypersphere)를 상상한다.v의 분할 평면과 교차한다면, 이는 반대편 서브트리가 정의하는 공간 영역 내에 best_dist보다 더 가까운 점이 존재할 수도 있다는 것을 의미한다. 따라서 이 경우에는 반드시 반대편 서브트리에 대해 재귀적으로 NN 탐색을 수행해야 한다.7q와 분할 평면 사이의 최단 거리가 현재의 best_dist보다 크다면, 반대편 서브트리 내의 모든 점들은 기하학적으로 현재 최적해보다 멀리 떨어져 있음이 보장된다. 이 경우, 해당 서브트리 전체를 탐색 대상에서 제외할 수 있다. 이것이 바로 ‘가지치기(pruning)’이며, 탐색 공간을 극적으로 줄여 알고리즘의 효율성을 높이는 핵심 원리이다.17이 백트래킹 과정이 루트 노드까지 완료되면, 최종적으로 best_dist와 함께 저장된 점이 q의 진정한 최근접 이웃이 된다.
범위 탐색은 사용자가 지정한 k차원 직사각형(hyperrectangle) 형태의 질의 범위 R 안에 완전히 포함되는 모든 데이터 포인트를 찾는 것을 목표로 한다.7 이 알고리즘 역시 kd-tree의 공간 분할 구조를 활용하여 효율적인 가지치기를 수행한다.
알고리즘은 루트 노드에서 시작하여 트리 전체를 재귀적으로 탐색하며, 각 노드 v에서 다음과 같은 판단을 내린다.
v가 암시적으로 나타내는 공간 영역(region)을 고려한다. 루트 노드의 영역은 전체 공간이며, 자식 노드의 영역은 부모 노드의 영역을 분할 평면으로 나눈 하위 공간이다.v의 공간 영역과 질의 범위 R 사이의 관계를 다음 세 가지 경우로 나누어 판단한다.
v의 공간 영역이 질의 범위 R에 완전히 포함된다면, v를 루트로 하는 서브트리에 속한 모든 점들은 질의 조건을 만족한다. 따라서 해당 서브트리의 모든 점들을 결과 목록에 추가하고, 더 이상 이 서브트리 아래로는 재귀 탐색을 진행할 필요가 없다. 이는 탐색을 조기에 종료시키는 중요한 최적화이다.21v의 공간 영역이 질의 범위 R과 전혀 겹치지 않는다면, 해당 서브트리에는 질의 조건을 만족하는 점이 존재할 수 없다. 따라서 이 서브트리 전체를 탐색 대상에서 제외(가지치기)한다.22v의 공간 영역이 질의 범위 R과 부분적으로만 겹친다면, 결과에 포함될 점과 그렇지 않은 점이 섞여 있을 수 있다. 이 경우, 먼저 현재 노드 v에 저장된 점이 R 내에 있는지 확인하여 결과에 추가할지 결정한다. 그 후, v의 왼쪽 자식과 오른쪽 자식 노드에 대해 이 범위 탐색 과정을 재귀적으로 계속 수행한다.11이러한 재귀적 탐색과 가지치기 과정을 통해, 범위 탐색 알고리즘은 질의 범위와 무관한 방대한 공간을 방문하지 않고도 정확한 결과를 효율적으로 찾아낼 수 있다.
kd-tree 탐색 알고리즘의 효율성은 본질적으로 ‘가지치기’의 성공률에 달려 있다. 그리고 이 성공률은 데이터가 분포하는 공간의 기하학적 구조, 특히 차원 수에 의해 직접적으로 결정된다. 저차원 공간에서는 점들이 비교적 조밀하게 분포하여 NN 탐색 시 best_dist가 빠르게 작은 값으로 수렴하고, 이 작은 탐색 반경은 대부분의 분할 평면과 교차하지 않아 효과적인 가지치기를 가능하게 한다. 그러나 고차원 공간에서는 상황이 역전된다. 다음 장에서 자세히 다룰 ‘차원의 저주’ 현상으로 인해 데이터는 극도로 희소해지고, 점들 간의 거리는 매우 멀어진다. 이는 best_dist가 매우 큰 값으로 유지되게 만들며, 결과적으로 거대한 탐색 초구는 거의 모든 분할 평면과 교차하게 된다. 결국 가지치기 메커니즘은 무력화되고, 탐색은 거의 모든 노드를 방문하는 선형 스캔에 가까워진다. 이 인과 관계는 ‘차원의 저주’가 알고리즘 수준에서 어떻게 kd-tree의 성능을 저하시키는지에 대한 구체적인 메커니즘을 명확히 보여준다.
kd-tree의 성능은 이론적으로 시간 및 공간 복잡도를 통해 분석될 수 있다. 성능은 데이터의 분포와 차원 수에 민감하며, 평균적인 경우(데이터가 무작위로 분포)와 최악의 경우(데이터가 편향되거나 특정 구조를 가짐) 사이에 상당한 차이를 보인다.
구축 (Construction): $n$개의 점으로 균형 잡힌 kd-tree를 구축하는 시간 복잡도는 분할 기준점인 중앙값을 찾는 방법에 따라 결정된다. 각 분할마다 정렬을 사용하면 $O(n \log n)$이 소요되어 전체적으로 $O(n \log^2 n)$이 되지만, 선형 시간 선택 알고리즘(median of medians)을 사용하면 각 레벨의 분할을 $O(n)$에 수행할 수 있어 전체 구축 시간은 $O(n \log n)$이 된다.12
삽입 및 삭제 (Insertion & Deletion): 균형이 잘 잡힌 트리에서 새로운 점을 삽입하거나 기존 점을 삭제하는 연산은 트리의 높이에 비례하므로 평균적으로 $O(\log n)$의 시간이 걸린다. 그러나 반복적인 삽입과 삭제로 트리가 불균형해지면, 트리의 높이가 $n$에 가까워져 최악의 경우 $O(n)$의 시간 복잡도를 가질 수 있다.18
최근접 이웃 탐색 (Nearest Neighbor Search): 데이터 포인트가 무작위로 분포되어 있을 때, NN 탐색은 효율적인 가지치기 덕분에 평균적으로 $O(\log n)$의 성능을 보인다.18 하지만 최악의 경우, 가지치기가 거의 일어나지 않아 트리 대부분의 노드를 방문해야 하므로
$O(n)$까지 성능이 저하될 수 있다.18
범위 탐색 (Range Search): $d$차원 공간에서 $n$개의 점에 대한 범위 탐색의 시간 복잡도는 결과로 반환되는 점의 개수 $k$에 의존한다. 최악의 경우, 방문해야 하는 노드의 수는 $O(d \cdot n^{1-1/d})$에 비례하며, 따라서 전체 시간 복잡도는 $O(d \cdot n^{1-1/d} + k)$가 된다.18 2차원의 경우 이는
$O(\sqrt{n} + k)$로 표현된다.
공간 복잡도 (Space Complexity): kd-tree는 $n$개의 각 점에 대해 하나의 노드를 생성하므로, 추가적인 포인터 공간을 포함하여 총 $O(n)$의 저장 공간을 필요로 한다.18
이러한 복잡도 특성은 아래 표 1에 요약되어 있다. 이 표는 kd-tree의 성능 특성을 한눈에 파악할 수 있는 핵심 정보를 제공하며, 특정 연산의 비용을 직관적으로 이해하고 다른 자료 구조와 정량적으로 비교하는 기준점이 된다.
| 연산 (Operation) | 평균 시간 복잡도 | 최악 시간 복잡도 |
|---|---|---|
| 구축 (Construction) | $O(n \log n)$ | $O(n \log n)$ 또는 $O(n \log^2 n)$ |
| 삽입 (Insertion) | $O(\log n)$ | $O(n)$ |
| 삭제 (Deletion) | $O(\log n)$ | $O(n)$ |
| 최근접 이웃 탐색 | $O(\log n)$ | $O(n)$ |
| 범위 탐색 | - | $O(d \cdot n^{1-1/d} + k)$ |
| 공간 복잡도 | $O(n)$ | $O(n)$ |
kd-tree의 가장 근본적인 한계는 고차원 공간에서 그 성능이 급격히 저하되는 ‘차원의 저주’ 현상이다.25 일반적으로 데이터의 차원이 10~20개를 넘어가기 시작하면 kd-tree의 탐색 효율성은 선형 스캔(brute-force search)과 별다른 차이가 없게 된다.17
이 현상의 근본 원인은 고차원 공간의 기하학적 특성과 그로 인한 데이터 희소성(sparsity)에 있다. 차원이 증가할수록 공간의 부피는 지수적으로 팽창한다. 고정된 수의 데이터 포인트는 이 광활한 공간에 극도로 드문드문 분포하게 되며, 결과적으로 거의 모든 점들이 서로에게서 멀리 떨어져 있게 된다.27
이러한 데이터 희소성은 제4장에서 설명한 kd-tree의 핵심 최적화 기법인 ‘가지치기’를 무력화시킨다. NN 탐색을 예로 들면, 고차원 공간에서는 질의점과 가장 가까운 이웃조차도 매우 멀리 떨어져 있을 가능성이 높다. 이는 탐색 초기에 설정되는 ‘최적 거리(best_dist)’가 매우 큰 값을 갖게 됨을 의미한다. 또한, 고차원 공간의 부피는 대부분 중심에서 먼 ‘모서리’ 부분에 집중되어 있어, 임의의 질의점은 거의 모든 분할 초평면과 가깝게 위치하게 된다. 결과적으로, 질의점을 중심으로 한 거대한 반지름의 탐색 초구는 거의 모든 분할 초평면과 교차하게 되고, 질의점-평면 간 거리 < best_dist 라는 조건이 거의 항상 참이 되어 버린다. 이는 알고리즘이 반대편 서브트리를 가지치기하지 못하고 거의 모든 노드를 방문해야 함을 의미하며, 이는 사실상 모든 점과의 거리를 계산하는 선형 스캔과 다를 바 없다.17
kd-tree의 또 다른 주요 한계는 동적 데이터, 즉 삽입과 삭제가 빈번하게 발생하는 환경에서의 비효율성이다. 제3장에서 분석했듯이, kd-tree의 삽입 및 삭제 연산은 트리의 균형을 고려하지 않는다. 따라서 데이터의 삽입/삭제 순서에 따라 트리는 쉽게 불균형 상태가 될 수 있으며, 최악의 경우 한쪽으로만 노드가 연결된 연결 리스트(linked list)와 같은 형태로 퇴화할 수 있다.30 이 경우 탐색 시간은 $O(\log n)$에서 $O(n)$으로 저하된다.
이 문제를 해결하기 위해서는 트리를 주기적으로 전체 재구축(rebuilding)해야 하지만, 이는 $O(n \log n)$의 높은 비용을 수반하는 작업이다. kd-tree는 다차원 정렬 제약 때문에 표준적인 트리 회전(tree rotation)을 통한 효율적인 재균형 메커니즘을 가지고 있지 않기 때문이다.12 이러한 특성으로 인해 kd-tree는 데이터의 변경이 거의 없는 정적(static) 데이터셋에 대한 인덱싱 구조로는 매우 효과적이지만, 데이터가 지속적으로 변하는 동적 환경에서는 사용하기에 적합하지 않다.3
표준 kd-tree가 가진 근본적인 한계, 특히 고차원 데이터에서의 성능 저하 문제를 극복하기 위해 다양한 변형 알고리즘이 제안되었다. 이 변형들은 문제 해결에 대한 서로 다른 철학적 접근을 보여주며, 이는 자료 구조 설계가 ‘일반성(generality)’에서 ‘특화(specialization)’로 나아가는 컴퓨터 과학의 더 넓은 흐름을 반영한다. Randomized kd-tree는 알고리즘 자체의 강건성을 높여 어떤 데이터 분포에서도 평균적으로 잘 동작하도록 진화한 반면, Adaptive kd-tree는 특정 워크로드에 구조를 동적으로 최적화하는 방향으로 진화했다.
Randomized kd-tree는 고차원 공간에서의 ‘차원의 저주’ 문제를 완화하기 위한 대표적인 접근법이다. 이 기법의 핵심은 결정론적인 단일 트리를 구축하는 대신, 무작위성을 도입하여 여러 개의 서로 다른 트리를 생성하고 이를 ‘숲(forest)’으로 만들어 사용하는 것이다.14
표준 kd-tree는 각 분할 단계에서 데이터의 분산이 가장 큰 축을 결정론적으로 선택한다. 이는 특정 데이터 분포에 대해 트리가 편향된 구조를 갖게 만들 위험이 있다. Randomized kd-tree는 이러한 결정론을 완화한다. 트리를 구축할 때, 분산이 가장 큰 단일 축을 선택하는 대신, 분산이 큰 상위 몇 개(예: 5개)의 축 중에서 무작위로 하나를 선택하여 분할 축으로 삼는다.14 또 다른 접근법으로는, 데이터를 kd-tree에 입력하기 전에 전체 데이터셋을 임의의 직교 기저(random orthogonal basis)로 회전시키는 전처리 단계를 거치기도 한다.34
이러한 무작위성은 다음과 같은 효과를 가져온다.
이러한 접근은 퀵 정렬에서 피벗을 무작위로 선택하여 최악의 경우를 피하는 고전적인 알고리즘 설계 기법과 맥을 같이하며, ‘어떤 입력에 대해서도’ 준수한 평균 성능을 내는 것을 목표로 한다.
Adaptive kd-tree는 주로 데이터베이스 환경에서 수행되는 탐색적 데이터 분석(exploratory data analysis) 워크로드의 특성에 대응하기 위해 제안된 변형이다.35 탐색적 분석에서는 사용자의 질의 패턴을 미리 예측하기 어렵고, 데이터의 특정 부분만 반복적으로 접근될 수 있다.
이러한 환경에서 Adaptive kd-tree는 다음과 같은 ‘적응적’ 특성을 보인다.
이러한 적응적 방식은 다음과 같은 이점을 제공한다.
Adaptive kd-tree의 철학은 “미리 최적의 구조를 알 수 없다면, 실제 사용 패턴을 관찰하며 점진적으로 최적화하자”는 것으로 요약될 수 있다. 이는 데이터베이스의 적응형 인덱싱이나 운영체제의 캐싱 전략 등에서 볼 수 있는 ‘온라인 학습’ 또는 ‘동적 최적화’ 패러다임과 일치하며, kd-tree가 특정 응용 분야의 요구에 맞춰 어떻게 특화될 수 있는지를 보여주는 흥미로운 사례이다.
kd-tree는 수많은 공간 자료 구조 중 하나이며, 그 특성을 명확히 이해하기 위해서는 다른 대표적인 구조들과의 비교가 필수적이다. 각 자료 구조는 서로 다른 설계 철학을 바탕으로 특정 문제 상황에 최적화되어 있으므로, 이들의 장단점을 비교 분석하는 것은 적절한 도구를 선택하기 위한 실용적인 지침을 제공한다.
R-tree는 동적 데이터와 영역 기반 객체를 효율적으로 처리하기 위해 설계된, 디스크 기반 데이터베이스 환경에서 널리 사용되는 공간 인덱스 구조이다.
분할 방식: 가장 근본적인 차이는 분할 방식에 있다. kd-tree는 공간 분할(space partitioning) 방식을 사용하여, 각 노드가 공간 전체를 겹치지 않는 두 개의 하위 공간으로 나눈다.36 반면, R-tree는
데이터 분할(data partitioning) 방식을 채택하여, 하위 노드에 포함된 데이터 객체들을 감싸는 최소 경계 사각형(Minimum Bounding Rectangle, MBR)을 기준으로 공간을 그룹화한다. 이 MBR들은 서로 겹칠 수 있다.36
균형 및 동적 특성: R-tree는 B-tree 구조에 기반하여 항상 균형 잡힌 상태를 유지하도록 설계되었다. 데이터의 삽입 및 삭제 시 노드의 분할(split)과 병합(merge)을 통해 트리의 높이 균형을 동적으로 조절한다. 이로 인해 동적 데이터 환경에 매우 강건하다. 반면, kd-tree는 균형 유지를 보장하지 않아 동적 데이터 처리에 비효율적이다.36
저장 매체: R-tree의 노드는 디스크의 페이지(page) 크기에 맞춰 설계되어 디스크 I/O를 최소화하는 데 최적화되어 있다. 이는 대용량 데이터베이스 시스템에 적합한 이유이다. kd-tree는 주로 주기억장치(in-memory)에서의 빠른 연산을 목표로 설계된 구조이다.3
저장 객체: kd-tree는 기본적으로 점(point) 데이터만을 저장할 수 있다. 반면, R-tree는 MBR을 사용하므로 점뿐만 아니라 선, 다각형(polygon) 등 영역을 가지는 기하학적 객체들도 효율적으로 저장하고 검색할 수 있다.36
Ball Tree는 kd-tree와 마찬가지로 최근접 이웃 탐색을 가속화하기 위한 자료 구조이지만, 특히 고차원 공간에서의 성능 저하 문제를 해결하는 데 중점을 둔다.
Quadtree(2차원)와 Octree(3차원)는 kd-tree와 같이 공간을 재귀적으로 분할하지만, 분할 방식에 있어 중요한 차이가 있다.
분할 방식: kd-tree는 데이터 기반(data-driven) 분할 방식을 사용한다. 즉, 데이터의 중앙값을 기준으로 공간을 나누므로 분할 경계가 데이터의 분포에 따라 적응적으로 결정된다 (이를 object-space decomposition이라 한다).40 반면, Quadtree와 Octree는
고정된(fixed) 분할 방식을 사용한다. 각 노드는 항상 자신의 공간 영역을 규칙적으로 4개(Quadtree) 또는 8개(Octree)의 동일한 크기의 하위 영역으로 분할한다 (이를 key-space decomposition이라 한다).40
트리 구조: 이러한 분할 방식의 차이는 트리 구조로 이어진다. kd-tree는 항상 이진 트리(binary tree)인 반면, Quadtree는 4-ary 트리, Octree는 8-ary 트리 구조를 가진다.40
균형: kd-tree는 중앙값을 사용하여 데이터 수의 균형을 맞추려 하지만, Quadtree/Octree는 공간을 균등하게 분할하므로 데이터가 한쪽에 몰려있을 경우 매우 깊고 비효율적인 트리가 생성될 수 있다.
아래 표 2는 이러한 주요 공간 자료 구조들의 핵심적인 특징을 비교하여 요약한 것이다. 이 표는 특정 응용 시나리오에 어떤 자료 구조가 가장 적합한지에 대한 의사결정을 돕는 실용적인 가이드라인을 제공한다.
| 특성 | kd-tree | R-tree | Ball Tree | Quadtree/Octree |
|---|---|---|---|---|
| 분할 방식 | 공간 분할 (Space Partitioning) | 데이터 분할 (Data Partitioning) | 데이터 분할 (Data Partitioning) | 공간 분할 (Space Partitioning) |
| 분할 형태 | 축-정렬 초평면 | 최소 경계 사각형 (MBR) | 최소 경계 초구 (MBH) | 규칙적 사분/팔분 |
| 영역 겹침 | 없음 | 허용 | 허용 | 없음 |
| 트리 구조 | 이진 트리 | N-ary 트리 (B-tree 기반) | 이진 트리 | 4-ary / 8-ary 트리 |
| 균형 유지 | 보장 안 됨 (정적) | 보장됨 (동적) | 보장됨 (동적) | 데이터 분포에 따라 다름 |
| 주요 저장 객체 | 점 (Point) | 영역 (Region) | 점 (Point) | 점 또는 영역 |
| 고차원 성능 | 취약 (차원의 저주) | 취약 | 상대적으로 강건 | 취약 |
| 저장 매체 | 메모리 지향 | 디스크 지향 | 메모리 지향 | 메모리 지향 |
kd-tree의 이론적 효율성은 다양한 실제 응용 분야에서 그 가치를 입증해왔다. 여러 분야에서 kd-tree의 역할은 표면적으로 달라 보일 수 있으나, 그 본질은 모두 ‘불필요한 계산을 배제하는 가지치기(pruning) 원리’의 구체적인 구현이라는 공통점을 가진다. kd-tree는 ‘공간적 근접성에 기반한 가지치기’라는 근본적인 계산 문제를 해결하는 우아하고 효율적인 프레임워크를 제공함으로써, 여러 도메인에 걸쳐 존재하는 ‘전체 탐색 회피’라는 보편적인 최적화 문제를 해결한다.
k-최근접 이웃(k-NN) 알고리즘은 분류(classification)와 회귀(regression) 문제에 사용되는 가장 직관적인 비모수적(non-parametric) 머신러닝 기법 중 하나이다. 이 알고리즘의 핵심은 새로운 미분류 데이터 포인트가 주어졌을 때, 기존 훈련 데이터셋에서 거리가 가장 가까운 $k$개의 이웃을 찾는 것이다.41 분류 문제에서는 이 $k$개 이웃의 다수결 투표로 클래스를 결정하고, 회귀 문제에서는 이웃들의 값의 평균 또는 가중 평균으로 값을 예측한다.42
가장 단순한 접근법은 새로운 포인트와 훈련 데이터셋의 모든 포인트 간의 거리를 일일이 계산하는 Brute-force 방식이다. 훈련 데이터의 크기가 $N$일 때, 이 방식의 시간 복잡도는 $O(N)$으로, 데이터셋이 커질수록 예측 시간이 선형적으로 증가하여 비효율적이 된다.17
kd-tree는 이 k-NN 탐색 과정을 획기적으로 가속화하는 핵심적인 데이터 구조로 활용된다. 훈련 데이터셋을 미리 kd-tree로 구축해두면, 새로운 포인트에 대한 k-최근접 이웃 탐색을 평균 $O(\log N)$의 시간 복잡도로 수행할 수 있다.24 이는 관련 없는 방대한 수의 데이터 포인트와의 거리 계산을 가지치기 원리를 통해 생략함으로써 가능해진다. Scikit-learn과 같은 주요 머신러닝 라이브러리에서는 KNeighborsClassifier나 KNeighborsRegressor의 algorithm 파라미터를 'kd_tree'로 명시적으로 선택하여 이 가속화 기법을 사용할 수 있다.42
자율주행 자동차의 LiDAR 센서나 3D 스캐너는 주변 환경을 수백만 개에서 수억 개에 이르는 3차원 점들의 집합, 즉 포인트 클라우드(point cloud)로 인식한다. 이 방대한 데이터로부터 로봇이 장애물을 감지하고, 객체를 인식하며, 지도를 생성하기 위해서는 점들 간의 공간적 관계를 신속하게 파악하는 것이 필수적이다.8
kd-tree는 이러한 포인트 클라우드 데이터를 효율적으로 구조화하고 질의하는 데 핵심적인 역할을 한다. 예를 들어, 포인트 클라우드를 여러 객체로 분할하는 군집화(clustering) 알고리즘인 유클리디안 클러스터링(Euclidean clustering)에서는 특정 거리 임계값 내에 있는 이웃 점들을 하나의 군집으로 묶는다.11 만약 모든 점 쌍 간의 거리를 계산한다면 엄청난 계산량이 요구되지만, 포인트 클라우드를 kd-tree로 구성하면 각 점에 대한 반경 내 이웃 탐색(radius search)을 매우 빠르게 수행하여 ‘너무 멀리 있는 3D 포인트’와의 불필요한 거리 계산을 생략할 수 있다.11 이는 로봇의 실시간 인지 및 의사결정 능력에 결정적인 기여를 한다.
실사 수준의 고품질 이미지를 생성하는 렌더링 기법인 광선 추적(Ray Tracing)은 시점에서부터 가상의 광선을 쏘아 씬(scene) 내의 객체들과의 상호작용을 시뮬레이션하는 방식이다. 이 과정에서 가장 계산 비용이 많이 드는 부분은 하나의 광선이 수많은 삼각형(polygon)으로 구성된 씬 내의 모든 객체와 교차하는지를 검사하는 것이다.9
kd-tree는 이 교차 검사 횟수를 극적으로 줄이는 가속 구조(acceleration structure)로 사용된다. 씬의 모든 객체(또는 객체를 구성하는 폴리곤)를 kd-tree로 구성하면, 공간이 계층적인 셀(cell)들로 분할된다. 광선이 특정 셀과 교차하지 않는다면, 그 셀 내부에 포함된 모든 객체는 해당 광선과 교차할 가능성이 없으므로 검사 대상에서 제외할 수 있다. 즉, ‘광선이 닿지 않는 공간’ 전체를 가지치기하는 것이다. 이를 통해 렌더링 성능을 수십, 수백 배 향상시킬 수 있다.9
유사한 원리가 게임 물리 엔진이나 시뮬레이션에서의 충돌 감지(collision detection)에도 적용된다. 씬 내의 모든 객체 쌍에 대해 충돌 여부를 검사하는 것은 $O(N^2)$의 복잡도를 가져 비효율적이다. 객체들을 kd-tree로 구성하면, 공간적으로 멀리 떨어져 있어 충돌 가능성이 없는 객체 쌍들을 빠르게 배제하고, 인접한 셀에 위치한 잠재적 충돌 후보군에 대해서만 정밀한 충돌 검사를 수행할 수 있다.48
지리 정보 시스템(GIS)과 같은 공간 데이터베이스에서 다차원 데이터(예: 위도, 경도 좌표)를 효율적으로 검색하기 위해서는 공간 인덱스가 필수적이다. kd-tree는 주기억장치(in-memory)에서 동작하는 공간 인덱스로서, 소규모의 다차원 점 데이터를 인덱싱하고 빠른 검색을 제공하는 데 적합하다.3
그러나 표준 kd-tree는 디스크 기반의 대용량 데이터베이스 환경에는 몇 가지 한계를 가진다. 노드 구조가 디스크 페이지와 정렬되지 않고, 동적 데이터에 대한 균형 유지 메커니즘이 부재하기 때문이다. 이러한 한계를 극복하기 위해 kd-tree의 아이디어를 B-tree의 장점과 결합한 BKD-tree (Block KD-tree)와 같은 변형이 등장했다.50 BKD-tree는 리프 노드가 단일 포인트가 아닌 여러 포인트를 담는 블록(block)으로 구성되며, 이는 디스크 I/O 효율을 극대화한다. Elasticsearch와 같은 현대적인 검색 엔진은 지리 공간 데이터(geospatial data) 인덱싱에 BKD-tree를 사용하여 대규모 데이터셋에 대해서도 빠르고 효율적인 위치 기반 검색을 제공한다.50 이는 kd-tree의 핵심적인 공간 분할 아이디어가 실제 시스템의 제약 조건에 맞춰 어떻게 성공적으로 진화하고 적용되었는지를 보여주는 중요한 사례이다.
본 고찰을 통해 kd-tree가 다차원 공간 데이터를 처리하는 데 있어 고전적이면서도 여전히 중요한 위치를 차지하는 자료 구조임을 확인하였다. 그 핵심 가치는 이진 탐색 트리라는 단순하고 명료한 이론을 다차원 공간으로 확장하여, 최근접 이웃 탐색 및 범위 질의와 같은 복잡한 근접성 문제에 대한 효율적인 해결책을 제공한다는 데 있다. 공간을 재귀적으로 분할하고 ‘가지치기’를 통해 탐색 공간을 극적으로 줄이는 원리는 저차원의 정적 데이터셋에 대해 평균 $O(\log n)$이라는 로그 시간 복잡도의 탐색 성능을 가능하게 한다. 이러한 이론적 우아함과 실용적 효율성의 결합은 kd-tree가 머신러닝, 컴퓨터 그래픽스, 로보틱스 등 수많은 분야에서 기본 도구로 자리 잡게 한 원동력이 되었다.
그러나 kd-tree는 명확한 이론적, 실용적 한계를 내포하고 있다. 가장 치명적인 한계는 고차원 공간에서 성능이 급격히 저하되는 ‘차원의 저주’ 현상이다. 고차원 공간의 기하학적 특성으로 인해 데이터가 희소해지면서, 탐색 알고리즘의 핵심인 가지치기 메커니즘이 사실상 무력화되어 성능이 선형 스캔 수준으로 퇴보한다. 또한, 효율적인 재균형 메커니즘의 부재로 인해 데이터의 삽입과 삭제가 빈번한 동적 환경에서는 트리의 균형이 쉽게 깨져 성능 저하를 유발한다. 이로 인해 kd-tree의 주된 적용 분야는 비교적 차원이 낮고 데이터 변경이 적은 정적 환경에 국한되는 경향이 있다.
이러한 한계에도 불구하고 kd-tree의 기본 원리는 사장되지 않고 현대 컴퓨팅 환경의 요구에 맞춰 끊임없이 진화하고 있다. ‘차원의 저주’에 대응하기 위해 무작위성을 도입한 Randomized kd-tree, 대규모 디스크 기반 데이터베이스를 위해 B-tree와 결합된 BKD-tree, 그리고 탐색적 분석 워크로드에 동적으로 최적화되는 Adaptive kd-tree와 같은 변형들은 kd-tree의 핵심 아이디어가 여전히 강력하며 현대적인 문제 해결에 효과적으로 기여하고 있음을 보여준다.
향후 연구는 kd-tree의 원리를 더욱 발전시켜 현재와 미래의 컴퓨팅 패러다임에 적용하는 방향으로 나아갈 것으로 전망된다. 첫째, GPU와 같은 대규모 병렬 처리 아키텍처의 이점을 최대한 활용하기 위한 kd-tree의 구축 및 탐색 알고리즘에 대한 연구가 활발히 진행될 것이다.51 SIMD(Single Instruction, Multiple Data) 연산을 통해 여러 탐색 경로를 동시에 처리하거나, 수만 개의 코어를 활용하여 트리를 병렬로 구축하는 기법은 실시간 3D 렌더링이나 대규모 시뮬레이션의 성능을 한 단계 끌어올릴 잠재력을 가지고 있다.
둘째, 전통적인 유클리드 거리 척도를 넘어, 머신러닝 및 데이터 마이닝 분야에서 중요성이 커지고 있는 다양한 비유클리드(non-Euclidean) 거리 메트릭(예: 코사인 유사도, 맨해튼 거리)을 효율적으로 지원하는 kd-tree의 변형에 대한 연구가 필요하다. 이는 kd-tree의 응용 범위를 텍스트 분석, 추천 시스템 등 새로운 영역으로 확장하는 데 기여할 것이다.
결론적으로, kd-tree는 그 자체로 완벽한 자료 구조는 아니지만, 공간 분할이라는 근본적인 아이디어를 통해 수많은 후속 연구와 변형 알고리즘에 영감을 주었다. 앞으로도 kd-tree와 그 파생 기술들은 다차원 데이터 처리 분야의 발전에 있어 중요한 이론적, 실용적 기반을 계속해서 제공할 것이다.
| [Data Structures] KD-Tree | KD-트리 - Archive - 티스토리, accessed August 17, 2025, https://dad-rock.tistory.com/589 |
| [나의 개발일지] - KD-Tree With C++ | ENTP 개발자, accessed August 17, 2025, https://kangminsu1.github.io/algorithm/first/ |
| k-d Trees for nearest neighbor search | by Muneeb ur Rahman …, accessed August 17, 2025, https://medium.com/@notesbymuneeb/k-d-trees-for-nearest-neighbor-search-df4fc459da51 |
| Range searching and kd-trees - ICS | Utrecht University, accessed August 17, 2025, https://ics-websites.science.uu.nl/docs/vakken/ga/2024/slides/slides5a.pdf |
| 근사 최근접 이웃(ANN) 알고리즘 이해 | Elastic Blog, accessed August 17, 2025, https://www.elastic.co/kr/blog/understanding-ann |
| KD-Tree and Ball Tree. Introduction: | by Srihari Reddy | Medium, accessed August 17, 2025, https://medium.com/@sriharir84/kd-tree-and-ball-tree-2108ed1e3530 |
| Ray tracing with KD-Tree from scratch | by Arthur F. S. Neto | Medium, accessed August 17, 2025, https://arthurflor23.medium.com/ray-tracing-with-kd-tree-from-scratch-9b218823bc00 |
| Elasticsearch 는 어떻게 위치 검색도 빠를까 - 2 | by allocProc, accessed August 17, 2025, https://jaeyeong951.medium.com/elasticsearch-%EB%8A%94-%EC%96%B4%EB%96%BB%EA%B2%8C-%EC%9C%84%EC%B9%98-%EA%B2%80%EC%83%89%EB%8F%84-%EB%B9%A0%EB%A5%BC%EA%B9%8C-2-54e47ab9de9d |
| What is KD-Tree? | Activeloop Glossary, accessed August 17, 2025, https://www.activeloop.ai/resources/glossary/kd-tree/ |