ANN(Approximate Nearest Neighbor, 근사 최근접 이웃)은 정확한 최근접 이웃(k-NN) 검색의 O(N·d) 복잡도를 줄이기 위해 약간의 정확도를 포기하고 속도를 크게 향상시키는 알고리즘이다.
ANN 알고리즘 비교
| 알고리즘 | 구조 | 쿼리 속도 | 메모리 | 정확도 |
|---|
| HNSW | 계층적 그래프 | 매우 빠름 | 높음 | 매우 높음 |
| IVF | 클러스터링 인덱스 | 빠름 | 낮음 | 중간 |
| PQ | 곱 양자화 | 빠름 | 매우 낮음 | 중간 |
| ANNOY | 랜덤 투영 트리 | 중간 | 중간 | 좋음 |
| LSH | 로컬 민감 해싱 | 빠름 | 중간 | 낮음 |
HNSW (Hierarchical Navigable Small World)
레이어 L (최상위, 소수 노드): 장거리 탐색
레이어 1 (중간): 중거리 탐색
레이어 0 (하위, 전체 노드): 세밀한 탐색
탐색 과정:
1. 레이어 L에서 시작점 진입
2. 각 레이어에서 쿼리와 가장 가까운 이웃으로 이동
3. 레이어 0에서 최종 k-NN 결과 반환
python
import hnswlib
import numpy as np
dim = 128
n_elements = 100_000
# HNSW 인덱스 생성
index = hnswlib.Index(space='cosine', dim=dim)
index.init_index(
max_elements=n_elements,
ef_construction=200, # 구축 시 탐색 범위 (높을수록 정확, 느림)
M=16, # 노드당 연결 수 (높을수록 정확, 메모리 증가)
)
data = np.random.random((n_elements, dim)).astype('float32')
labels = np.arange(n_elements)
index.add_items(data, labels)
# 쿼리 파라미터 조정
index.set_ef(50) # 쿼리 시 탐색 범위 (ef >= k)
query = np.random.random((1, dim)).astype('float32')
labels, distances = index.knn_query(query, k=10)
print(f"최근접 이웃: {labels[0]}")
print(f"거리: {distances[0]}")
# 인덱스 저장/로드
index.save_index("hnsw_index.bin")
index.load_index("hnsw_index.bin", max_elements=n_elements)
정확도 평가 (Recall@K)
python
def compute_recall(ann_results, exact_results, k):
"""ANN 결과의 정확한 NN 대비 재현율"""
recalls = []
for ann_ids, exact_ids in zip(ann_results, exact_results):
ann_set = set(ann_ids[:k])
exact_set = set(exact_ids[:k])
recalls.append(len(ann_set & exact_set) / k)
return np.mean(recalls)
