근사 최근접 이웃 탐색 (approximate nearest neighbor search)
한 줄 정의: 약간의 정확도를 포기하는 대신 고차원 벡터 중 가장 가까운 것을 매우 빠르게 찾는 기법입니다.
쉽게 풀면
수억 개의 벡터 중에서 질의와 가장 가까운 것을 찾으려면 전부와 거리를 계산해야 해서 느립니다. 근사 탐색은 정답을 100% 보장하지 않는 대신, 미리 만들어 둔 색인을 이용해 유망한 후보만 훑어보고 답을 냅니다. 재현율을 조금 낮추면 속도는 수백 배 빨라지는 교환이 가능합니다.
왜 중요한가
임베딩으로 의미를 다루는 오늘날의 검색과 추천, 그리고 검색증강생성의 실질적 기반 기술입니다. 벡터 데이터베이스의 핵심 엔진이 바로 이 알고리즘이며, 응답 속도와 인프라 비용을 직접 좌우합니다. 대규모 검색 시스템 논문에서 재현율과 초당 질의 수의 상충 곡선으로 성능을 보고하는 것이 관례입니다.
논문에서는 이렇게 쓰입니다
"HNSW 색인을 사용한 근사 최근접 이웃 탐색에서 재현율 0.95를 유지하면서 전수 탐색 대비 질의 지연을 120배 단축하였다."
거의 정확한 답을 유지하면서 검색 속도를 크게 높였다는 성능 보고입니다.
조금 더 깊게 보면
대표적 계열로는 이웃 관계를 여러 층의 그래프로 쌓아 탐색하는 HNSW, 벡터를 부분 공간으로 쪼개 코드북으로 압축하는 곱 양자화, 공간을 군집으로 나눠 일부만 뒤지는 역파일 색인, 그리고 지역 민감 해싱이 있습니다. 실무에서는 군집 분할과 양자화를 결합해 메모리와 속도를 함께 잡는 구성이 흔합니다. 평가는 정확한 정답 집합 대비 재현율과 질의 처리량을 함께 그린 곡선으로 이루어집니다.
주의할 점
K-최근접 이웃은 이웃들의 라벨로 예측하는 분류·회귀 알고리즘이고, 이쪽은 이웃을 빠르게 찾아내는 검색 문제라는 점에서 층위가 다릅니다. 색인을 만들 때의 설정이 재현율을 좌우하므로 속도 비교는 반드시 같은 재현율 수준에서 해야 합니다.