KD-Tree로 다차원 포인트를 빠르게 찾는 방법
KD-Tree의 축 순환 분할과 가지치기 원리, 저차원 최근접 이웃·반경 질의 성능, 재구축과 대안 인덱스 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
포인트 검색 범위를 분할하는 KD-Tree
KD-Tree(K-dimensional Tree)는 다차원 포인트 집합을 빠르게 찾기 위한 고전적인 공간 인덱스다. 이진 탐색 트리의 분기 개념을 K차원 공간으로 넓혀, 하이퍼플레인으로 탐색할 영역을 계속 좁힌다. 소규모 데이터셋과 저차원 환경, 대체로 k ≤ 10 내외에서 특히 실효성이 있다.
각 노드는 포인트 하나와 분할 축을 가진다. 선택한 축을 기준으로 공간을 둘로 나누고, 깊이가 내려갈 때마다 축을 순환시킨다. 2차원 좌표라면 x→y→x→y 순서가 된다.
트리는 메인 메모리에서 포인트를 다루는 데 초점이 맞춰져 있다. 삽입 순서에 따라 점진적으로 구성하면 불균형해질 수 있으며, 데이터가 특정 영역에 몰리면 탐색 성능도 저하될 수 있다.
축 순환과 영역 경계가 탐색을 줄이는 방식
깊이 d에서 선택된 축에 대해 p[d] < key[d]이면 왼쪽, 그렇지 않으면 오른쪽 서브트리로 분기한다. 이 직교 하이퍼플레인 분할로 각 노드는 암묵적인 하이퍼직사체 영역을 맡는다.
최근접 이웃을 찾을 때는 먼저 질의점이 속한 방향으로 내려간다. 리프에서 후보를 갱신한 뒤에는 되돌아오면서, 반대쪽 영역의 경계거리가 현재 후보보다 가까울 가능성이 있는지 판단한다. 가능성이 없으면 해당 서브트리를 건너뛴다.
노드에는 포인트, 분할 축, 좌우 포인터가 저장된다. 리프에 소수의 포인트를 버킷으로 묶어 두는 구성도 가능하다.
균형 트리의 평균 탐색 시간은 O(log n)이며, 최악의 경우는 O(n)이다. k-NN 탐색은 백트래킹과 가지치기를 통해 평균적으로 선형 탐색보다 큰 이득을 얻는다. 포인트 수 n에 따라 메모리는 선형으로 증가하고, 포인터와 메타데이터 때문에 원시 데이터 대비 1.2~2.5배 수준의 오버헤드가 생길 수 있다.
차원이 증가하면 박스와 구의 체적 차이가 커져 가지치기 효과가 빠르게 약해진다. 실무에서는 k ≤ 10~20, n이 수십만 미만인 범위에서 효과적이다.
갱신이 잦다면 균형을 운영 지표로 다룬다
삽입과 삭제가 반복되면 트리가 한쪽으로 기울 수 있다. n 변화율 20~30% 또는 높이·균형 지표 초과를 재구축 기준으로 두는 방식이 쓰인다.
리프 버킷에 B=8~32개의 포인트를 저장하면 캐시 지역성을 높이고 리빌드 주기를 완화할 수 있다. 반대로 디스크 기반 처리나 균형 보장이 필요한 경우에는 K-D-B-Tree(K-D_B)를 고려할 수 있다. K-D-B-Tree는 페이지 단위로 균형을 유지해 범위 질의 성능을 안정화한다.
입력 자체가 한쪽에 치우친 경우에는 삽입 무작화(randomized), 주기적인 미디안 리빌드, 리밸런싱 배치 작업으로 높이 증가를 완화한다. 고차원에서는 Ball-Tree, HNSW, Annoy가 대안이 될 수 있으며, 대용량·지속성 요구에서는 K-D-B-Tree나 R-Tree 계열이 더 적합하다.
위치 검색부터 저차원 임베딩까지
실시간 위치·센서 처리에서는 2D/3D 좌표의 k-NN 질의와 반경 질의(radius search)에 사용할 수 있다. 근접 기지국 탐색이나 로봇 장애물 회피가 여기에 해당한다.
게임과 시뮬레이션에서는 충돌 후보를 줄이는 브로드페이즈, 시야 판정, 공간 파티셔닝에 활용된다. 프레임마다 근접 포인트를 빠르게 찾아야 할 때 유용하다.
ML·추천 전처리에서는 저차원 임베딩으로 k-NN 그래프를 만들거나 이상치를 탐지할 수 있다. 데이터 크기 수만~수십만, k ≤ 20 범위가 적용 대상이다. GIS에서도 타일이나 씬 단위 포인트를 서버 메모리 캐시 인덱스로 운영할 수 있다.
k-NN 질의에서 내려가고 되돌아오는 과정
질의점 q, 트리 루트, 반환할 이웃 수 k를 입력으로 받는다. 분할 축 d를 따라 리프까지 내려간 후 후보를 갱신하고, 경계거리로 반대편 서브트리를 방문할지 결정한다. 결과는 거리 오름차순 k개 포인트이며, 빈 트리는 빈 결과를 반환하고 동점에는 안정 정렬 기준을 정의한다.
인덱스 선택은 데이터 차원과 저장 환경에서 갈린다
| 인덱스 | 성능(저차원) | 확장성(대용량) | 일관성/균형 | 안정성(편향 데이터) | 운영 편의 |
|---|---|---|---|---|---|
| KD-Tree | k-NN/반경 질의 우수, 평균 O(log n) | 메모리 한계, 수십만 미만 권장 | 삽입 기반 불균형 가능 | 분포 편향 시 성능 급락 | 구현 단순, 재구축 필요 |
| K-D-B-Tree | 페이지 단위 균형, 안정적 범위 질의 | 디스크/SSD 친화, 대용량 적합 | B-Tree식 균형 유지 | 편향 영향 완화 | 구현 복잡, 페이지 튜닝 필요 |
| R-Tree(변종 포함) | 사각 영역 질의 강점 | 디스크 기반 확장 용이 | 노드 분할 알고리즘 의존 | 중첩 증가 시 성능 저하 | 공간 객체 전반에 적합 |
| Ball-Tree | 고차원/메트릭 공간에 우수 | 메모리, 중간 규모 적합 | 중심/반경 기반 분할 | 분포에 따라 성능 변동 | KD 대안, k>20에서 유리 |
저차원에서 균형과 가지치기가 유효하다면 k-NN 질의는 선형 스캔 대비 평균 10100배 단축될 수 있다. 반경 질의에서 후보 수가 전체의 p%이면 평균 연산량은 ~ O(p·n + log n) 수준이다. 리프 버킷을 쓰면 캐시 적중률 향상으로 1030% 추가 개선 가능성이 있다.
이 구조는 메모리 안에서 일관된 응답 시간을 확보하기 쉽고 구현과 디버깅도 단순하다. 배치 재구축을 운영 절차에 결합하면 성능 예측 가능성도 높아진다.
정적 데이터와 증분 데이터의 구축 전략
정적 데이터셋은 미디안 분할로 배치 구축해 높이 균형을 확보하는 방식이 적합하다. 증분 삽입은 단순하지만 불균형 위험이 있으므로 n 변화율 임계치에 도달하면 전체 재구축을 병행한다.
리프 버킷은 B=8~32로 설정해 포인트 클러스터를 저장할 수 있다. 이 방식은 트리 높이와 포인터 오버헤드를 줄인다. 운영 중에는 트리 높이, 평균 리프 크기, 백트래킹 시 방문 서브트리 비중인 가지치기 비율을 관찰한다.
디스크·대용량 환경에서는 K-D-B-Tree를 선택하고 페이지 크기, 채움 계수, 분할 정책을 함께 튜닝한다.
Python에서 KD-Tree를 사용하는 예
전제조건
- Python 3.10+
- scikit-learn >= 1.3, numpy
설치
- pip install scikit-learn numpy
예시 코드
import numpy as np
from sklearn.neighbors import KDTree
# 데이터 생성: 2D 포인트 50,000개
rng = np.random.default_rng(42)
X = rng.normal(size=(50_000, 2)).astype(np.float32)
# KD-Tree 구축
# leaf_size: 리프 버킷 크기, 커질수록 트리 낮아지고 리프 내 선형 검색 증가
tree = KDTree(X, leaf_size=32, metric='euclidean')
# 1) k-NN 질의
q = np.array([[0.2, -0.1]], dtype=np.float32)
dist, idx = tree.query(q, k=5, return_distance=True)
print("kNN indices:", idx[0], "distances:", dist[0])
# 2) 반경 질의 (반경 r 내 포인트 인덱스 리스트 반환)
r = 0.5
indices = tree.query_radius(q, r=r)[0]
print("radius count:", indices.size)
# 3) 축 범위 질의 (사각 범위) - 간단 구현: 필터링 결합
# KDTree는 박스 질의를 직접 지원하지 않으므로, 필요 시 후보 추출 후 필터링
min_xy, max_xy = np.array([-0.5, -0.5]), np.array([0.5, 0.5])
# 반경 후보 추출(대략 박스 대각선 길이로 완화), 이후 박스 내 필터링
diag = np.linalg.norm(max_xy - min_xy)
c = (min_xy + max_xy) / 2
cand = tree.query_radius(c.reshape(1, -1), r=diag / 2)[0]
box_idx = cand[(X[cand] >= min_xy).all(axis=1) & (X[cand] <= max_xy).all(axis=1)]
print("box query count:", box_idx.size)
# 4) 동적 갱신 전략: 일정 비율 삽입 후 재구축
new_points = rng.normal(size=(5_000, 2)).astype(np.float32)
X = np.vstack([X, new_points])
# 간단 재구축
tree = KDTree(X, leaf_size=32, metric='euclidean')leaf_size는 k가 크거나 반경 질의 비중이 높을 때 크게, k가 작을 때 작게 조정한다. 데이터 누적이나 분포 변화가 감지되면 배치 재구축을 수행한다. 차원 k가 커지면 BallTree(sklearn.neighbors.BallTree) 전환을 검토한다.