정렬된 배열에서 특정 값을 찾을 때, 전부 다 순회할 때의 시간 복잡도는 O(n)이다. 하지만 배열이 정렬되어 있다는 사실을 이용하면, 중간값과 비교해서 절반을 날릴 수 있다. 이것이 이진 탐색이고, O(log n) 시간 복잡도를 가진다.
정렬된 배열에서 쿼리 값 q에 가장 가까운 원소를 찾는 최근접 이웃(nearest neighbor) 탐색도 같은 원리이다. brute force로 하면 모든 원소와의 거리를 계산해야 하니 O(n)이다. 하지만 배열이 정렬되어 있으면, q가 배열에서 어디쯤 들어갈지를 이진 탐색으로 O(log n)에 찾을 수 있다. q가 들어갈 위치를 찾았으면, 가장 가까운 원소는 그 위치의 바로 왼쪽 아니면 오른쪽에 있다.
이 문제는 1차원에 해당한다. 하지만 2차원 평면에 점들이 흩어져 있으면 어떻게 할까! x좌표로 정렬하자니 y좌표 정보를 잃고, y좌표로 정렬하자니 x좌표 정보를 잃는다. 두 축을 동시에 고려해야 한다.
축을 번갈아 나누기
KD-tree의 아이디어는 단순하다. 한 축으로 정렬해서 반으로 나누고, 다음 축으로 정렬해서 반으로 나누고, 이걸 번갈아 반복하는 것이다.
구체적인 예시로 보자. 2차원 평면에 6개의 점이 있다.
A(2,3), B(5,4), C(9,6), D(4,7), E(8,1), F(7,2)- 루트: x축 기준
-
먼저 모든 점의 x좌표를 본다: 2, 4, 5, 7, 8, 9
-
중앙값은 7이므로
F(7,2)가 루트가 된다. -
이제
x = 7이라는 수직선이 평면을 둘로 나눈다. (x ≤ 7인 점들{A, B, D}은 왼쪽,x > 7인 점들{C, E}는 오른쪽)y8 |7 | D6 | C5 |4 | B3 | A |2 | F |1 | | E+--+--+--+--+--+--+--+--+-- x2 3 4 5 6 7 8 9↑x = 7 (루트 분할)
- 왼쪽 서브트리: y축 기준
-
{A(2,3), B(5,4), D(4,7)}의 y좌표는 3, 4, 7이다. -
중앙값은 4이므로
B(5,4)가 이 서브트리의 루트가 된다. -
y = 4라는 수평선으로 나눈다. (A(y=3)는 아래,D(y=7)는 위)왼쪽 영역 (x ≤ 7):y8 |7 | D 위 (y > 4)6 |5 |4 |- - B - - - - ← y = 4 (B 분할)3 | A 아래 (y ≤ 4)2 |+--+--+--+--+--+-- x2 3 4 5 6 7
- 오른쪽 서브트리: y축 기준.
{C(9,6), E(8,1)}의 y좌표는 1, 6이다.- 중앙값은
E(8,1). E가 루트가 되고 C는 위쪽 자식이 된다.
결과 트리:
F(7,2) [x축] / \ B(5,4) [y축] E(8,1) [y축] / \ \ A(2,3) D(4,7) C(9,6)각 내부 노드는 공간을 둘로 나누는 분할면(splitting plane)을 정의한다. F(7,2)는 x = 7이라는 수직선으로 공간을 나누고, B(5,4)는 y = 4라는 수평선으로 나눈다. 이 분할면들이 평면을 재귀적으로 쪼개서, 각 리프 노드는 자기만의 영역을 갖게 된다.
전체 평면의 분할:
y8 | | |7 | D | |6 | | | C5 | | |4 |- - B - -| |3 | A | F |2 | | |1 | | | E +--+--+--+--+--+--+--+--+-- x 2 3 4 5 6 7 8 9 | y=4 분할 x=7 분할n개의 점에 대해 매번 중앙값을 골라 반으로 나누므로 트리의 높이는 O(log n)이다. 구성 시간은 각 레벨에서 중앙값을 찾는 비용까지 포함하면 O(n log n)이다.
코드로 보면 이렇다.
struct Node { double pt[2]; Node *left, *right; int axis; // 0: x축, 1: y축};
Node* build(vector<array<double,2>>& pts, int depth, int lo, int hi) { if (lo >= hi) return nullptr; int axis = depth % 2; int mid = (lo + hi) / 2; nth_element(pts.begin()+lo, pts.begin()+mid, pts.begin()+hi, [axis](auto& a, auto& b){ return a[axis] < b[axis]; }); Node* node = new Node{pts[mid][0], pts[mid][1], nullptr, nullptr, axis}; node->left = build(pts, depth+1, lo, mid); node->right = build(pts, depth+1, mid+1, hi); return node;}nth_element는 O(n)에 중앙값을 제자리에 놓는다. 전체 정렬이 아니라 k번째 원소만 올바른 위치에 놓으면 되기 때문에, quick select 알고리즘을 사용하여 평균 O(n)에 동작한다. 중앙값 왼쪽은 모두 더 작고 오른쪽은 모두 더 크다는 것만 보장하면 충분하다.
각 레벨에서 모든 노드를 합치면 총 n개의 점을 처리하고, 레벨이 O(log n)개이므로 전체 구성 시간은 O(n log n)이다.
최근접 이웃 탐색
트리를 만들었으니 이제 쿼리를 처리해보자. 쿼리 점 Q(6,3)에 가장 가까운 점을 찾고 싶다.
탐색의 기본 전략은 이렇다. 쿼리 점이 속하는 쪽의 서브트리를 먼저 깊이 우선으로 탐색한다. 그러면서 만나는 노드와의 거리를 계산해 현재까지의 최소 거리를 갱신한다. 돌아오는 길에, 반대쪽 서브트리에 더 가까운 점이 있을 가능성이 있는지 확인한다. 가능성이 없으면 건너뛴다.
탐색 과정
Q(6,3)을 쿼리한다.
y8 | | |7 | D | |6 | | | C5 | | |4 |- - B - -| |3 | A | Q F |2 | | |1 | | | E +--+--+--+--+--+--+--+--+-- x 2 3 4 5 6 7 8 9-
루트 F(7,2)에서 시작: x축 기준이고 Q의 x = 6 < 7이므로, Q는 F의 왼쪽 영역에 속한다. 왼쪽 서브트리를 먼저 탐색한다. 동시에 F와의 거리를 계산해둔다.
- dist(Q, F) =
√((6-7)² + (3-2)²) = √(1 + 1) = √2 ≈ 1.41 - 현재 최소: 1.41 (F)
- dist(Q, F) =
-
B(5,4) 확인: y축 기준이고 Q의
y = 3 < 4이므로 왼쪽(아래)으로 간다. B와의 거리도 계산한다.- dist(Q, B) =
√((6-5)² + (3-4)²) = √(1 + 1) = √2 ≈ 1.41 - 현재 최소: 1.41 (F 또는 B, 동률)
- dist(Q, B) =
-
A(2,3) 확인: 리프 노드
- dist(Q, A) =
√((6-2)² + (3-3)²) = √(16 + 0) = 4 - 4 > 1.41. 갱신 없음.
- dist(Q, A) =
-
A에서 돌아와서, B의 반대쪽(위)을 확인해야 할까?
B는 y = 4로 공간을 나눴다. Q에서 이 분할면까지의 거리는
|3 - 4| = 1이다. 이것은 “반대쪽 영역에 있는 어떤 점이든, Q와의 y축 방향 거리가 최소 1이다”라는 뜻이다. 하지만 전체 유클리드 거리는 y축 거리보다 클 수도 있고 같을 수도 있다. 중요한 건,1 < 1.41이므로 반대쪽에 더 가까운 점이 있을 가능성을 배제할 수 없다. 탐색해야 한다.분할면까지 거리: |3 - 4| = 1현재 최소 거리: 1.411 < 1.41 → 반대쪽 탐색 필요만약 현재 최소 거리가 0.5였다면? 분할면까지의 거리 1이 0.5보다 크므로, 반대쪽의 어떤 점도 0.5보다 가까울 수 없다. 이 경우 반대쪽을 통째로 건너뛸 수 있다!
-
D(4,7)을 확인한다.
dist(Q, D) = √((6-4)² + (3-7)²) = √(4 + 16) = √20 ≈ 4.474.47 > 1.41. 갱신 없음. -
B의 서브트리를 다 봤다. F로 돌아와서, F의 반대쪽(오른쪽)을 확인해야 할까? F는 x = 7로 나눴다.
분할면까지 거리: |6 - 7| = 1현재 최소 거리: 1.411 < 1.41 → 반대쪽 탐색 필요 -
E(8,1)을 확인한다.
dist(Q, E) = √((6-8)² + (3-1)²) = √(4 + 4) = √8 ≈ 2.832.83 > 1.41. 갱신 없음. -
E의 반대쪽에 C(9,6)이 있다. E는 y = 1로 나눴다.
분할면까지 거리: |3 - 1| = 2현재 최소 거리: 1.412 > 1.41 → 건너뛴다!드디어 가지치기가 발동했다. C(9,6)은 아예 보지 않는다. Q에서 y = 1 분할면까지 거리가 2인데, 현재 최선이 1.41이니까, C가 어디에 있든 1.41보다 가까울 수 없다.
결과: Q(6,3)의 최근접 이웃은 F(7,2) 또는 B(5,4), 거리 √2. 6개 점 중 C를 제외한 5개만 확인했다. 점이 수만 개라면 가지치기로 건너뛰는 서브트리가 훨씬 커진다.
가지치기가 정당한 이유
분할면은 공간을 두 반공간(half-space)으로 나눈다. 쿼리 점에서 분할면까지의 거리를 d_plane, 현재까지 찾은 최소 거리를 d_best라 하자.
반대쪽 반공간에 있는 임의의 점 P를 생각하자. Q에서 P까지의 유클리드 거리를 d(Q, P)라 하면, 이 거리는 분할면에 수직인 성분과 평행한 성분으로 분해할 수 있다.
d(Q, P)² = d_plane² + d_parallel²d_parallel² ≥ 0이므로 d(Q, P)² ≥ d_plane²이다. 따라서 d(Q, P) ≥ d_plane이다.
d_plane > d_best이면, 반대쪽의 모든 점 P에 대해 d(Q, P) ≥ d_plane > d_best이다. 현재 최선보다 가까운 점이 반대쪽에 있을 수 없다.
double best_dist; // 거리의 제곱을 저장 (√ 연산을 피하기 위해)const double* best_pt;
void nn_search(Node* node, const double query[2]) { if (!node) return;
// 현재 노드와의 거리 계산 double dist = 0; for (int i = 0; i < 2; i++) dist += (query[i] - node->pt[i]) * (query[i] - node->pt[i]); if (dist < best_dist) { best_dist = dist; best_pt = node->pt; }
// 쿼리가 속하는 쪽을 먼저 탐색 double diff = query[node->axis] - node->pt[node->axis]; Node* near = diff <= 0 ? node->left : node->right; Node* far = diff <= 0 ? node->right : node->left;
nn_search(near, query);
// 가지치기: 분할면까지의 거리² < 현재 최소 거리²이면 반대쪽도 탐색 if (diff * diff < best_dist) nn_search(far, query);}코드에서 dist와 best_dist는 거리의 제곱을 저장한다. 매번 √를 계산하는 건 비싸고, 대소 비교에서는 제곱을 비교해도 결과가 같기 때문이다. diff * diff도 분할면까지 거리의 제곱이다.
2~3차원에서 점들이 균일하게 분포되어 있으면, 이 가지치기가 대부분의 서브트리를 쳐내서 평균 O(log n)에 탐색이 가능하다. 지도에서 가장 가까운 음식점 찾기, 게임에서 가장 가까운 적 유닛 찾기 같은 저차원 공간 문제에 적합하다.
범위 탐색
KD-tree는 최근접 이웃 말고도 범위 탐색(range search)에 쓸 수 있다. “이 직사각형 안에 있는 점을 모두 찾아라”는 질문이다.
아까 만든 트리에서 “x ∈ [3, 8], y ∈ [2, 5]인 점을 찾아라”를 처리해보자.
쿼리 직사각형: [3,8] × [2,5]
y8 | | |7 | D | |6 | | | C5 | +---------+ |4 | | B | |3 | A | | F |2 | +---|------+ |1 | | | | E +--+--+--+--+--+--+--+--+-- x 2 3 4 5 6 7 8 9-
루트 F(7,2). x = 7 분할. 쿼리 범위 [3, 8]이 7을 포함하므로 양쪽 다 탐색해야 한다. F 자체는 (7, 2)인데, y = 2는 [2, 5]에 포함된다. F는 결과에 포함.
-
왼쪽 B(5,4). y = 4 분할. 쿼리 범위 [2, 5]가 4를 포함하므로 양쪽 다 탐색. B 자체는 (5, 4)이고 [3,8]×[2,5]에 포함된다. B도 결과에 포함.
-
B의 아래 A(2,3). x = 2는 [3, 8]에 포함되지 않는다. A는 결과에 미포함. A는 리프이므로 끝.
-
B의 위 D(4,7). y = 7은 [2, 5]에 포함되지 않는다. D는 결과에 미포함. 리프이므로 끝.
-
오른쪽 E(8,1). y = 1 분할. E 자체는 (8, 1)인데, y = 1은 [2, 5]에 포함되지 않는다. E는 미포함. 쿼리 범위 [2, 5]가 y = 1보다 위에만 있으므로 E의 아래쪽 서브트리(없음)는 건너뛰고 위쪽만 본다.
-
E의 위 C(9,6). x = 9는 [3, 8]에 포함되지 않는다. C는 미포함.
결과: {B(5,4), F(7,2)}.
핵심은 3단계와 5단계다. A(2,3)의 서브트리 전체가 x < 3이라면 쿼리 범위 [3, 8]에 포함될 수 없으므로 통째로 건너뛸 수 있다. E의 아래쪽 서브트리도 마찬가지다. 각 노드가 자기 서브트리의 바운딩 박스를 알고 있으면, 바운딩 박스가 쿼리 범위와 겹치지 않을 때 서브트리를 통째로 건너뛰고, 바운딩 박스가 쿼리 범위에 완전히 포함될 때는 서브트리의 모든 점을 한꺼번에 보고할 수 있다.
O(√n) 복잡도
이 범위 연산의 복잡도가 흥미롭다. 2D KD-tree에서 축에 정렬된 직사각형 범위 쿼리의 복잡도는 O(√n)이다.
왜 O(√n)일까? 트리를 레벨별로 생각해보자.
x축으로 나누는 레벨에서, 쿼리 직사각형의 x 범위 [x1, x2]가 어떤 노드의 분할값을 포함하면 양쪽 자식을 모두 탐색해야 한다. 포함하지 않으면 한쪽만 간다.
그런데 같은 레벨에서 양쪽으로 갈라지는 노드는 최대 2개다. 생각해보면, 각 레벨의 노드들은 x축 기준으로 정렬되어 있다. 쿼리 범위의 왼쪽 경계 x1이 지나가는 노드 하나, 오른쪽 경계 x2가 지나가는 노드 하나. 그 사이의 노드들은 분할값이 [x1, x2] 안에 완전히 포함되어 한쪽(내부)으로만 가고, 바깥의 노드들은 반대쪽(외부)으로만 간다.
x축 분할 레벨의 노드들:
←외부→ ←갈라짐→ ←내부→ ←갈라짐→ ←외부→ 한쪽만 양쪽 한쪽만 양쪽 한쪽만 ↑ ↑ x1 x2x축 분할에서 최대 2개가 갈라지고, 그 다음 y축 분할에서도 최대 2개가 갈라진다. 따라서 2레벨(x → y)을 내려갈 때마다 갈라지는 노드 수가 최대 2배가 된다.
트리 높이가 log n이므로 “2레벨 쌍”은 (log n)/2개이다. 갈라지는 노드 수를 T(n)이라 하면:
T(n) = 2 · T(√n) + O(1)왜 T(√n)일까? n개의 점을 x축으로 반, y축으로 반 나누면 각 사분면에 n/4개가 있다. 갈라지는 노드 하나가 담당하는 서브트리 크기가 n/2이고, 그 서브트리 안에서 다음 x축 분할까지(2레벨) 내려가면 크기가 n/4, 즉 원래의 √(n/2) ≈ √n이 된다.
이 점화식을 풀어보자. T(n) = c · √n이라 가정하면:
T(n) = 2 · T(√n) + O(1) = 2 · c · √(√n) + O(1) = 2 · c · n^(1/4) + O(1)
이것이 c · √n = c · n^(1/2)과 같아야 한다.음, 좀 더 정확하게 살펴보자. 레벨별로 추적하면:
레벨 0 (x축): 갈라지는 노드 2개레벨 1 (y축): 각각에서 2개씩, 총 4개레벨 2 (x축): 각각에서 2개씩? 아니다.
실제로는:- 레벨 0 (x축): x 경계에서 갈라지는 노드 2개- 레벨 1 (y축): 갈라진 2개 노드에서 y 경계에서 갈라지는 노드 각 2개, 총 4개- 레벨 2 (x축): 4개 노드에서 x 경계에서 갈라지는 노드 각 2개? 아니다! 레벨 2의 x축 분할에서, x 경계 하나가 지나가는 노드는 여전히 1개뿐이다. 경계가 2개(x1, x2)이므로 최대 2개. 하지만 이들은 레벨 1에서 갈라진 4개 노드의 자식들이다.정리하면, x축 분할 레벨에서는 x 경계 때문에 +2개가 갈라지고, y축 분할 레벨에서는 y 경계 때문에 +2개가 갈라진다. 2레벨을 내려갈 때마다 갈라지는 노드 수가 2개 추가된다.
(log n)/2 레벨 쌍 × 2개씩 = O(√n)이다. 왜냐하면 2^((log n)/2) = √n이기 때문이다.
대입해서 검증해보자. n = 16일 때:
트리 높이: log₂ 16 = 4 (레벨 0~3)레벨 0 (x축): 갈라지는 노드 2개 → 4개 서브트리레벨 1 (y축): 4개 중 각 경계에서 갈라지는 노드 2개 → 총 방문 노드 누적 ~4개레벨 2 (x축): ...레벨 3 (y축): ...
총 방문 노드: O(√16) = O(4)따라서 2D KD-tree에서 직사각형 범위 쿼리의 복잡도는 **O(√n)**이다. 일반적으로 d차원에서는 O(n^(1-1/d))이다. d = 2이면 O(n^(1/2)) = O(√n), d = 3이면 O(n^(2/3))이다.
세그먼트 트리처럼 쓰기
이 O(√n) 범위 연산 덕분에 KD-tree를 2D 세그먼트 트리처럼 쓸 수 있다. 1D 세그먼트 트리가 구간에 대한 업데이트와 쿼리를 O(log n)에 처리하듯이, KD-tree는 2D 직사각형에 대해 O(√n)에 처리한다.
1D 세그먼트 트리를 떠올려보자. “구간 [l, r]에 값 w를 더하라”는 연산에서, 세그먼트 트리의 노드가 담당하는 구간이 [l, r]에 완전히 포함되면 lazy 값만 갱신하고 멈춘다. 겹치지 않으면 건너뛴다. 부분적으로 겹치면 자식으로 내려간다.
KD-tree도 같은 방식이다. 각 노드는 자기 서브트리의 2D 바운딩 박스를 알고 있다. 업데이트 직사각형이 이 바운딩 박스를 완전히 포함하면 lazy만 갱신하고 멈춘다.
구체적으로, 4×4 격자에서 range add + range max를 해보자.
초기 상태 (4×4, 모두 0):
1 2 3 4 +---+---+---+---+1 | 0 | 0 | 0 | 0 | +---+---+---+---+2 | 0 | 0 | 0 | 0 | +---+---+---+---+3 | 0 | 0 | 0 | 0 | +---+---+---+---+4 | 0 | 0 | 0 | 0 | +---+---+---+---+16개의 셀을 KD-tree에 넣는다. 각 노드는 바운딩 박스, 서브트리 최댓값, lazy 값을 관리한다.
연산 1: add([1,3] × [1,2], 5) — 왼쪽 위 6칸에 5를 더한다.
1 2 3 4 +---+---+---+---+1 | 5 | 5 | 5 | 0 | +---+---+---+---+2 | 5 | 5 | 5 | 0 | +---+---+---+---+3 | 0 | 0 | 0 | 0 | +---+---+---+---+4 | 0 | 0 | 0 | 0 | +---+---+---+---+KD-tree에서 이 연산을 처리할 때, 바운딩 박스가 [1,3]×[1,2]에 완전히 포함되는 서브트리는 lazy만 갱신한다. 부분적으로 겹치는 노드만 자식으로 내려간다. O(√16) = O(4)개의 노드만 방문하면 된다.
연산 2: add([2,4] × [2,4], 3) — 오른쪽 아래 9칸에 3을 더한다.
1 2 3 4 +---+---+---+---+1 | 5 | 5 | 5 | 0 | +---+---+---+---+2 | 5 | 8 | 8 | 3 | +---+---+---+---+3 | 0 | 3 | 3 | 3 | +---+---+---+---+4 | 0 | 3 | 3 | 3 | +---+---+---+---+쿼리: max([1,3] × [1,3]) — 왼쪽 위 9칸의 최댓값?
범위 내의 값: 5, 5, 5, 5, 8, 8, 0, 3, 3최댓값: 8KD-tree에서 이 쿼리를 처리할 때, 바운딩 박스가 [1,3]×[1,3]에 완전히 포함되는 서브트리는 저장된 서브트리 최댓값(+ lazy)을 바로 반환한다. 이 최댓값이 현재까지 찾은 답보다 작으면 아예 건너뛸 수도 있다.
BOJ 18756 (Data Structure Quiz)가 정확히 이 문제다. n×n 행렬에 직사각형 범위 덧셈을 수행한 뒤 직사각형 범위 최댓값을 묻는다. 문제 지문 자체가 “After learning KD-tree, you came up with the following problem”으로 시작한다. 시간 제한이 8초인 건 O(√n) 연산의 상수가 크기 때문이다.
고차원의 저주
여기까지 보면 KD-tree가 만능처럼 보인다. 하지만 차원이 올라가면 상황이 완전히 달라진다.
거리 집중 현상
d차원 공간에 n개의 점을 균일 분포로 뿌렸다고 하자. 쿼리 점에서 가장 가까운 점까지의 거리를 D_min, 가장 먼 점까지의 거리를 D_max라 하면
(D_max - D_min) / D_min → 0 (d → ∞)이 성립한다. “가장 가까운 점”과 “가장 먼 점”의 상대적 차이가 사라지는 것이다.
왜 그럴까? 유클리드 거리는 각 차원의 기여분을 합산한 것이다.
dist² = (x₁-y₁)² + (x₂-y₂)² + ... + (x_d-y_d)²각 항 (xᵢ-yᵢ)²는 독립적인 확률변수다. d개의 독립적인 확률변수를 더하면 큰 수의 법칙에 의해 합은 기댓값 근처에 집중된다. d가 크면 거의 모든 점 쌍의 거리가 평균 거리 근처에 몰린다.
구체적인 숫자로 보자. [0,1]^d 균일 분포에서 두 점 간 거리²의 기댓값은 d/6이다. 각 차원에서 (xᵢ-yᵢ)²의 기댓값이 1/6이고 (두 개의 독립 균일분포의 차이의 제곱), 이것을 d번 더하니까 d/6이다. 분산은 7d/180이다. 거리²의 변동계수(CV = 표준편차/평균)는
CV = √(7d/180) / (d/6) = √(7/180) × 6 / √d ≈ 1.18 / √dd = 2: CV ≈ 0.84 거리 분포가 넓다. 가까운 점과 먼 점이 잘 구분된다.d = 10: CV ≈ 0.37 좁아지기 시작한다.d = 100: CV ≈ 0.12 거의 비슷비슷하다.d = 1000: CV ≈ 0.037 사실상 모든 점이 같은 거리에 있다.d = 1000이면 거리²의 표준편차가 평균의 3.7%에 불과하다. “가장 가까운 점”이라는 개념 자체가 희미해진다.
부피 집중
d차원 단위 초구(hypersphere)를 생각하자. 반지름 r인 구의 부피는 r^d에 비례한다. 따라서 반지름 1인 구 대비 반지름 (1-ε)인 구의 부피 비율은 (1-ε)^d이다.
ε = 0.01, 즉 반지름을 1%만 줄였을 때:
d = 2: 0.99² = 0.98 → 부피의 98%가 안쪽에. 껍질은 2%.d = 10: 0.99¹⁰ ≈ 0.904 → 껍질에 10%.d = 100: 0.99¹⁰⁰ ≈ 0.366 → 껍질에 63%. 절반 이상이 껍질이다.d = 500: 0.99⁵⁰⁰ ≈ 0.0066 → 99.3%가 껍질.d = 1000: 0.99¹⁰⁰⁰ ≈ 0.00004 → 99.996%가 껍질.1000차원에서는 구의 부피 중 99.996%가 반지름 0.99~1.0 사이의 두께 0.01짜리 껍질에 들어있다. 점들이 전부 표면 근처에 몰려 있는 셈이다.
이것은 직관에 반하지만, 수식으로 보면 당연하다. 2차원에서 원의 넓이는 πr²이고, 3차원에서 구의 부피는 (4/3)πr³이다. 지수가 d이면 r이 1보다 조금만 작아도 d번 곱해지면서 급격히 줄어든다.
이게 KD-tree와 무슨 상관일까? KD-tree의 최근접 이웃 탐색에서, 현재 최소 거리 d_best로 원(구)을 그리면 그 안에 더 가까운 점이 있을 수 있는 영역이다. 고차원에서는 이 구의 부피 대부분이 표면 근처에 몰려있으므로, 구가 분할면과 교차할 확률이 매우 높다. 교차하면 반대쪽을 건너뛸 수 없다.
프루닝 실패
이제 KD-tree로 돌아오자. 가지치기 조건을 다시 보면
if (diff * diff < best_dist) nn_search(far, query);diff는 한 축에서의 거리 차이이고, best_dist는 전체 유클리드 거리²이다.
d차원에서 전체 거리²은 d개 축의 기여분을 합산한 것이다. 각 축이 대략 비슷하게 기여한다고 하면, 한 축의 기여분은 전체의 약 1/d이다.
best_dist ≈ d × (한 축의 평균 기여분)diff² ≈ 한 축의 기여분 ≈ best_dist / d따라서 diff² < best_dist는 best_dist/d < best_dist와 비슷하고, d ≥ 2이면 항상 참이다.
구체적으로, d = 2이면 diff²이 best_dist의 약 1/2이다. 절반 정도의 경우에 프루닝이 가능하다. d = 10이면 diff²이 best_dist의 약 1/10이다. 거의 항상 diff² < best_dist가 성립해서 반대쪽을 건너뛸 수가 없다. d = 768이면 1/768 수준이라 프루닝은 사실상 일어나지 않는다.
결국 모든 노드를 방문하게 되고, 트리 구조 유지 비용만 추가된 brute force보다 느린 결과가 된다.
이론적 분석
Friedman, Bentley, Finkel(1977)의 원래 분석에 따르면 KD-tree의 탐색 비용은 O(2^d · log n)이다. 고정 차원에서 2^d는 상수이므로 O(log n)이라고 쓸 수 있지만, 차원이 변수가 되면 이야기가 다르다.
brute force는 O(d · n)이다. 각 점과의 거리를 계산하는 데 d번의 연산이 필요하고, n개의 점을 봐야 하니까.
역전 조건은 2^d · log n ≈ d · n이다. 양변에 구체적인 숫자를 넣어보면:
n = 1,000,000 (log₂ n ≈ 20): 2^d × 20 = d × 1,000,000 d = 10: 2^10 × 20 = 20,480 vs 10 × 1,000,000 = 10,000,000 → KD-tree 승 d = 15: 2^15 × 20 = 655,360 vs 15 × 1,000,000 = 15,000,000 → KD-tree 승 d = 17: 2^17 × 20 = 2,621,440 vs 17 × 1,000,000 = 17,000,000 → KD-tree 승 d = 20: 2^20 × 20 = 20,971,520 vs 20 × 1,000,000 = 20,000,000 → 거의 동률 d = 25: 2^25 × 20 = 671,088,640 vs 25 × 1,000,000 = 25,000,000 → brute force 승
n = 10,000 (log₂ n ≈ 13): d = 10: 2^10 × 13 = 13,312 vs 10 × 10,000 = 100,000 → KD-tree 승 d = 13: 2^13 × 13 = 106,496 vs 13 × 10,000 = 130,000 → 거의 동률 d = 15: 2^15 × 13 = 425,984 vs 15 × 10,000 = 150,000 → brute force 승데이터가 많을수록 역전 지점이 약간 뒤로 밀리지만, 대략 10~20차원 근처에서 KD-tree가 brute force에 밀린다.
Weber, Schek, Blott(1998, VLDB)는 KD-tree를 포함한 파티셔닝 기반 인덱스들을 실험적으로 비교해서, 약 10차원을 넘으면 순차 탐색이 이긴다는 것을 보였다. 이론보다 빠르게 역전되는 이유는, 위의 분석이 평균적인 경우를 가정하는 반면 실제 데이터는 차원 간 상관관계가 있어서 프루닝 효과가 이론치보다 떨어지기 때문이다.
scikit-learn은 이 결과를 반영해서 algorithm='auto'에서 D > 15이면 brute force로 전환한다.
그래서 고차원에선 어떻게 하나
임베딩 벡터는 768차원(BERT), 1536차원(OpenAI ada-002), 3072차원(text-embedding-3-large) 수준이다. KD-tree로는 어림도 없는 차원이다.
정확한 최근접 이웃을 효율적으로 찾는 것이 불가능하므로, 정확도를 약간 포기하고 속도를 얻는 방식을 쓴다. 이것이 Approximate Nearest Neighbor(ANN)이다.
- IVF: k-means로 클러스터를 만들고, 쿼리에 가까운 클러스터만 탐색한다. 4096개 클러스터에서 16개만 보면 전체의 0.4%만 탐색하는 셈이다.
- LSH: 가까운 벡터가 같은 버킷에 들어가도록 해시 함수를 설계한다. 랜덤 초평면으로 공간을 나누는 SimHash가 대표적이다.
- PQ: 768차원 벡터를 8개의 96차원 sub-vector로 쪼개서 각각 256개 코드워드로 양자화한다. 3072바이트가 8바이트로 압축된다.
- HNSW: 스킵 리스트처럼 계층적 그래프를 만들어 그리디 탐색한다. 상위 레이어에서 대충 근처로 이동하고, 하위 레이어에서 정밀하게 찾는다.
축 기반 분할은 고차원에서 실패한다. 하지만 해싱, 클러스터링, 그래프 같은 다른 방식으로 탐색 범위를 줄이는 것은 가능하다. KD-tree가 “축 하나로 절반을 날린다”면, ANN 방법들은 “데이터의 구조 자체를 활용해서 대부분을 날린다.” 방법만 바뀌었을 뿐, “전부 다 보지 않고 좋은 후보를 빠르게 찾자”는 목표는 같다.
참고 자료
- Friedman, Bentley, Finkel. “An Algorithm for Finding Best Matches in Logarithmic Expected Time.” ACM TOMS, 1977
- Weber, Schek, Blott. “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces.” VLDB, 1998
- Beyer, Goldstein, Ramakrishnan, Shaft. “When Is ‘Nearest Neighbor’ Meaningful?” ICDT, 1999
- scikit-learn Nearest Neighbors documentation
- BOJ 18756 - Data Structure Quiz