최근접 이웃 탐색

수치해석 통계 소프트웨어 마지막 수정: 2026-08-28 04:47:55

1. 개요[편집]

저차원에서는 풀린 문제고, 고차원에서는 «정확히 푸는 것을 포기하는 법»에 관한 문제다.

최근접 이웃 탐색(nearest neighbor search, NNS)은 $D$ 차원 거리공간 $(\mathcal X, \delta)$ 위의 점 집합 $S = \{p_1,\dots,p_n\}$ 을 미리 전처리해 두고, 질의점 $q$ 가 들어올 때마다 $\delta(q,p)$ 를 최소로 하는 $p \in S$ 를 빠르게 돌려주는 문제다. 한 줄로 쓰면 시시해 보이지만, 이 한 줄이 점군 정합의 대응 탐색, SPH 입자의 이웃 목록, $k$ -NN 분류, 추천 시스템의 후보 생성, 그리고 요즘 LLM 검색 증강의 벡터 조회까지를 전부 떠받치고 있다.

이 문서는 문제 자체와 고차원에서의 탈출 전략을 다룬다. 저차원 공간 분할 자료구조의 내부 동작은 KD-트리 문서가, 전체 자료구조 지도는 공간 분할 자료구조 문서가 맡는다.

2. 문제의 네 가지 얼굴[편집]

같은 이름 아래 서로 난이도가 꽤 다른 문제 넷이 섞여 있다.

변종	요구	성격
정확 NN	가장 가까운 점 하나	고차원에서 사실상 전수탐색
$k$ -NN	가장 가까운 $k$ 개	최선 반경 대신 힙의 최댓값으로 가지치기
반경 질의	거리 $r$ 이내 전부	반경이 고정이라 격자와 궁합이 좋다
$c$ -근사 NN	최적의 $c$ 배 이내인 점 하나	고차원에서 유일하게 이론적 보증이 남는 형태

$c$ -근사 NN의 정의를 정확히 써 두면 뒤의 이론이 편해진다. 최적해가 $p^\star$ 일 때

\delta(q, \hat p) \;\le\; c \cdot \delta(q, p^\star), \qquad c > 1

를 만족하는 $\hat p$ 를 (보통 높은 확률로) 돌려주면 성공이다. 이 한 글자 $c$ 를 양보하는 대가로 얻는 것이 지수 → 다항의 전환이다.

전수탐색의 비용은 질의당 $O(nD)$ 다. 우습게 볼 게 아니다 — 메모리를 순차로 훑으니 캐시·SIMD·GPU 친화적이라 상수가 극단적으로 작고, $n$ 이 수십만 정도면 어지간한 트리를 그냥 이긴다. 자료구조를 도입하기 전에 전수탐색을 재는 것이 이 분야의 첫 번째 국룰이다.

3. 저차원 — 이미 끝난 이야기[편집]

$D$ 가 2~3, 넉넉히 잡아 10 정도면 정확 NN은 해결된 문제다.

보로노이 다이어그램 + 점 위치 결정. NN 문제의 답을 공간에 미리 그려 둔 것이 보로노이 셀이므로, 평면에서는 셀을 만들고( $O(n\log n)$ ) 점 위치 자료구조를 얹으면 질의가 $O(\log n)$ 이다. 이론적으로 완벽하고 고차원에서 즉사한다 — $D$ 차원 보로노이 다이어그램의 복잡도가 $O(n^{\lceil D/2 \rceil})$ 이라 $D=6$ 만 돼도 저장 자체가 불가능하다.
KD-트리. 축 정렬 초평면으로 재귀 분할하고, 「질의점에서 분할면까지의 거리가 현재 최선 반경 이상이면 형제 가지를 버린다」로 가지치기한다. 고정 $D$ ·균등 분포에서 기대 $O(\log n)$ .
볼 트리·VP-트리. 축 대신 초구로 자른다. 축이 의미 없는 좌표계나 비유클리드 거리(삼각부등식만 있으면 된다)에서 KD-트리보다 낫다.
R-트리 계열. 원래 공간 데이터베이스용 디스크 자료구조로, 경계 상자를 계층으로 묶는다는 점에서 경계 볼륨 계층의 친척이다. GIS와 DBMS 인덱스로 살아 있다.
균일 격자·공간 해싱. 반경 질의가 목적이고 밀도가 고르면 이게 이긴다. 셀 변을 $r$ 로 잡으면 후보가 인접 $3^D$ 칸으로 끝나 질의당 $O(1)$ .

4. 고차원 — 저주가 내려앉는 지점[편집]

$D$ 가 커지면 위의 자료구조가 하나씩 전수탐색으로 수렴한다. 원인은 차원의 저주의 거리 집중 현상이다. 좌표가 대략 독립이면 제곱거리 $\sum_i (q_i - p_i)^2$ 가 $D$ 개 항의 합이라 큰 수의 법칙으로 평균 근방에 몰리고, 최근접과 최원접의 상대 격차가 $0$ 으로 간다. 「반대편은 볼 필요 없다」는 가지치기 논거는 거리들이 서로 충분히 다를 때만 성립하므로, 거리가 다 비슷해지는 순간 모든 가지가 살아남는다.

정량적으로도 우울하다. 정확 NN을 질의 시간 $\mathrm{poly}(D, \log n)$ 에 푸는 자료구조는 공간이 $n$ 에 대해 지수적이어야 한다는 하계 결과들이 있고, 실무 경험칙도 같은 말을 한다 — $n \gg 2^D$ 가 아니면 트리를 쓸 이유가 없다. 512차원 임베딩 1억 개는 이 조건 근처에도 못 간다.

여기서 길은 둘로 갈린다. 차원을 줄이거나(주성분 분석, 무작위 사영 — 존슨-린덴슈트라우스 보조정리는 $O(\varepsilon^{-2}\log n)$ 차원으로 줄여도 모든 쌍 거리가 $1\pm\varepsilon$ 안에 보존됨을 보장하며, 이 목표 차원이 원래 $D$ 와 무관하다는 것이 핵심이다), 정확성을 줄이거나. 실무는 대개 둘 다 한다.

5. LSH — 충돌이 곧 이웃[편집]

국소 민감 해싱(Locality-Sensitive Hashing, LSH)은 인디크와 모트와니(1998)가 연 길이다. 발상은 해시 함수의 통념을 뒤집는다. 보통 해시는 비슷한 입력을 최대한 멀리 흩뜨리는 것이 미덕인데, LSH는 가까운 점끼리 일부러 충돌시킨다.¹

해시 족 $\mathcal H$ 가 $(r_1, r_2, p_1, p_2)$ -민감하다는 것은, $h$ 를 $\mathcal H$ 에서 무작위로 뽑을 때

\delta(p,q) \le r_1 \Rightarrow \Pr[h(p)=h(q)] \ge p_1, \qquad \delta(p,q) \ge r_2 \Rightarrow \Pr[h(p)=h(q)] \le p_2

이고 $p_1 > p_2$ 인 경우를 말한다. 이런 족이 있으면 해시 $k$ 개를 이어 붙여 충돌 확률을 벌리고( $p^k$ ), 그런 테이블을 $L$ 개 두어 놓칠 확률을 낮추는(AND-OR 증폭) 표준 구성으로 $c = r_2/r_1$ 근사 NN을 풀 수 있다. 비용은

\text{질의 } O(n^{\rho}),\quad \text{공간 } O(n^{1+\rho}),\qquad \rho = \frac{\ln(1/p_1)}{\ln(1/p_2)}

다. $\rho < 1$ 이면 전수탐색보다 점근적으로 빠르다는 것이 이 이론의 전부이자 아름다운 부분이다. 해밍 거리의 비트 샘플링은 $\rho = 1/c$ , 유클리드 거리는 안도니와 인디크(2006)가 $\rho \to 1/c^2$ 를 달성했다.

거리별로 해시 족이 따로 있다.

거리·유사도	해시 족	아이디어
해밍 거리	비트 샘플링	무작위로 비트 한 자리를 본다
자카드 유사도	MinHash	무작위 순열에서 최솟값 원소를 본다
코사인 유사도	SimHash	무작위 초평면의 어느 쪽인지 부호를 본다
유클리드 거리	p-안정 분포 사영	가우시안 방향으로 사영해 폭 w 구간으로 양자화

가우시안이 2-안정 분포라는 사실이 마지막 줄의 정체다 — 가우시안 벡터와의 내적이 원 벡터의 유클리드 노름에 비례하는 가우시안이 되므로, 사영값의 차이가 원 거리에 비례한다. 이론적으로 가장 튼튼한 방법이지만, 실측 성능에서는 아래의 그래프 기반에 밀렸다. 보증이 최악 케이스 기준이라 실제 데이터의 구조를 전혀 이용하지 못하기 때문이다.

6. 그래프 기반 — 실무의 승자[편집]

오늘날 벡터 검색의 사실상 표준은 근접 이웃 그래프 위를 탐욕적으로 걷는 방식이다. 각 점을 노드로, 「이웃일 법한 점」들을 간선으로 이어 두고, 질의가 오면 아무 노드에서 시작해 질의에 더 가까워지는 이웃으로 계속 이동한다. 후보 힙을 들고 다니며 폭 $ef$ 만큼 넓게 훑으면 정확도와 속도를 손잡이 하나로 맞바꿀 수 있다.

HNSW(Hierarchical Navigable Small World, 말코프·야셰닌 2016)가 대표다. 그래프를 여러 층으로 쌓되 위층일수록 노드가 기하적으로 희박해져 긴 간선(고속도로) 역할을 하고, 아래층으로 내려갈수록 촘촘해져 정밀 탐색을 맡는다. 스킵 리스트를 그래프에 이식한 구조라고 보면 정확하다. 간선을 고를 때 단순히 가까운 순으로 $M$ 개를 잇지 않고 방향이 다양해지도록 가지치기하는 것이 핵심 디테일인데, 그러지 않으면 간선이 한 방향으로 몰려 탐욕 탐색이 국소 최소에 갇힌다.

NSG(Navigating Spreading-out Graph, 푸 외 2019)는 계층을 없애는 대신 단조 탐색 경로가 존재하도록 간선을 설계해, 더 희박한 그래프로 비슷한 성능을 낸다. HNSW의 약점이 메모리(원본 벡터 + 간선 리스트를 전부 램에 올려야 한다)라는 점을 생각하면 의미 있는 방향이다.

그래프 기반의 실무적 단점은 셋이다. 구축이 느리고(대개 $O(n \log n)$ 이지만 상수가 크다), 삭제가 어렵고(간선 그래프에서 노드를 빼면 연결성이 망가진다), 그리고 이론적 보증이 사실상 없다. 그럼에도 이긴 이유는 단순하다 — 벤치마크에서 압도적으로 빠르다.²

7. 양자화 — 메모리를 이긴다[편집]

벡터 자체를 압축하는 계열도 있다. 곱양자화(Product Quantization, PQ; 제구·두즈·슈미트 2011)는 $D$ 차원 벡터를 $m$ 개 부분벡터로 쪼개고 각 조각을 256개 중심으로 벡터 양자화해 벡터 하나를 $m$ 바이트로 줄인다.³ 질의와의 거리는 조각별 거리표를 미리 만들어 놓고 더하기만 하면 되므로(비대칭 거리 계산), 원본을 복원하지 않고 압축 상태에서 바로 거리를 잰다. 128차원 float 벡터 512바이트가 8~16바이트가 되니 램에 올릴 수 있는 데이터가 수십 배로 늘어난다.

실전 조합은 IVFPQ다. 먼저 $k$ -평균으로 데이터를 수천 개 클러스터로 나눠 역파일(inverted file) 인덱스를 만들고, 질의는 가까운 몇 개 클러스터만 열어 본 뒤, 그 안에서 중심으로부터의 잔차를 PQ로 압축해 비교한다. 조립 부품이 전부 고전 기법인데 합쳐 놓으면 십억 개 규모가 노트북에서 돈다.

라이브러리로는 페이스북의 FAISS(2017)가 사실상 표준 구현이고, 구글의 ScaNN(2020)은 내적 검색에서 잔차의 방향에 따라 오차의 중요도가 다르다는 관찰로 양자화 손실을 이방적으로 가중해 정확도를 끌어올렸다. 요즘 벡터 데이터베이스라 불리는 제품들은 대개 HNSW 아니면 IVFPQ, 혹은 둘의 조합을 엔진으로 쓴다.

8. 평가 — 재현율-지연시간 곡선[편집]

근사 검색을 「정확도 몇 %」 한 숫자로 보고하는 것은 무의미하다. 모든 방법이 손잡이를 돌려 정확도와 속도를 맞바꾸기 때문이다(HNSW의 $ef$ , IVF의 탐색 클러스터 수, LSH의 테이블 수). 그래서 표준 평가는 곡선이다.

가로축: 초당 질의 수(QPS) 또는 질의 지연시간.
세로축: recall@ $k$ — 정답 $k$ -NN 중 몇 개를 실제로 회수했는가.
손잡이를 쓸어 가며 점을 찍어 파레토 곡선을 그리고, 두 방법을 곡선끼리 비교한다.

ANN-Benchmarks(아우뮐러 외)가 이 방식을 표준화한 공개 벤치마크이고, 새 방법을 주장하려면 여기 곡선을 올리는 것이 예의가 됐다. 곡선을 보면 지형이 명확해진다 — 낮은 재현율 구간에서는 양자화 계열이, 90% 이상 고재현율 구간에서는 그래프 계열이 대체로 이긴다. 그리고 재현율 99.9% 근처에서는 결국 전수탐색과 겨루게 된다.⁴

9. 시뮬레이션 쪽에서의 얼굴[편집]

이 문제가 순수 검색 기술처럼 보이지만, 수치 시뮬레이션에서도 같은 뼈대가 계속 나온다.

입자법 이웃 탐색. SPH와 분자동역학의 이웃 찾기는 반경이 고정된 반경 질의다. 그래서 근사도 트리도 필요 없고, 셀 변을 컷오프로 잡은 균일 격자(셀 리스트)가 질의당 $O(1)$ 로 압승한다. 여기에 컷오프보다 약간 큰 «껍질»(skin)까지 이웃으로 저장해 두고 몇 스텝 동안 재사용하는 베를레 목록을 얹는 것이 표준이다. 이 분야에서 「고차원」이란 말은 나오지 않는다 — $D=3$ 이니까.
희소행렬 패턴 생성. 무격자법(RBF 보간, 이동최소자승)이나 $k$ -NN 그래프 기반 스펙트럴 군집화·다양체 학습에서는 이웃 관계가 곧 행렬의 비영 패턴이다. $k$ -NN 탐색이 어셈블리 전 단계이고, 여기서 이웃을 잘못 고르면 시스템의 조건수와 희소성이 통째로 망가진다.
$k$ -NN 회귀·대리모형. 값비싼 해석의 결과를 저장해 두고 새 설계점에서 가까운 사례를 찾아 보간하는 방식은 가장 원시적인 대리모형이다. 설계변수가 스무 개만 넘어가도 차원의 저주에 정면으로 부딪히며, 그래서 실무는 거리를 스케일링하거나 차원을 줄이고 들어간다.
검색 증강. 텍스트·코드 임베딩을 벡터 인덱스에 넣고 질의 근처를 뽑아 오는 지금의 파이프라인은, 결국 트랜스포머가 만든 고차원 벡터에 대한 근사 NN 질의다. 이 문서의 모든 기법이 그대로 쓰인다.

10. 고르는 법[편집]

$n$ 과 $D$ 를 먼저 적는다. $D \lesssim 10$ 이면 KD-트리나 격자로 끝내고 근사는 쳐다보지 않는다.
반경이 고정인가? 그렇다면 격자다. 트리는 반경이 질의마다 다를 때 값을 한다.
전수탐색을 재 본다. $n \le 10^5$ 이고 GPU가 있으면 정확 전수탐색이 대개 충분하고, 무엇보다 정답을 준다.
정확도 요구를 숫자로 정한다. recall@10 이 0.95면 되는지 0.999가 필요한지에 따라 답이 갈린다. 정하지 않으면 튜닝이 끝나지 않는다.
램에 들어가나? 들어가면 HNSW, 안 들어가면 IVFPQ. 이 한 줄이 실무 결정의 절반이다.
거리 함수를 확인한다. 코사인 유사도를 쓸 거면 벡터를 미리 정규화해 유클리드 문제로 바꿔라. 대부분의 인덱스가 내적/유클리드에 최적화돼 있다.

11. 관련 문서[편집]

LSH가 「비슷한 것을 일부러 충돌시키는 해시」라는 점은 암호학적 해시와 정확히 반대다. 암호 해시의 목표는 1비트만 바뀌어도 출력이 완전히 달라지는 눈사태 효과인데, LSH는 1비트 바뀌면 출력도 거의 그대로이길 원한다. 같은 「해시」라는 단어를 쓰는 두 분야가 서로의 목표를 결함이라고 부른다. ↩
그래프 기반 방법이 왜 그렇게 잘 되는지에 대한 만족스러운 이론은 아직 없다. 「실제 데이터는 내재 차원이 낮은 다양체 위에 있어서」가 통용되는 설명인데, 그 다양체가 뭔지 아무도 모른다. 실무가 이론을 20년쯤 앞서 달리는 흔치 않은 사례. ↩
PQ의 조각당 중심 개수가 하필 256인 이유는 우아하지 않다. 1바이트에 딱 들어가서다. 알고리즘 설계에서 «메모리 정렬이 하이퍼파라미터를 정한다»의 교과서적 사례. ↩
그래서 벤치마크에서 가장 정직한 기준선은 언제나 전수탐색이다. 「우리 인덱스가 100배 빠르다」의 분모가 무엇인지 확인하지 않으면, 정확도를 90%로 낮춘 결과와 정확한 답을 비교하는 그림이 나온다. 재현율 축이 없는 속도 비교는 읽지 않아도 된다. ↩