Brain💡 핵심 인사이트 ANN(Approximate Nearest Neighbor, 근사 최근접 이웃)은 "정확한 Nearest Neighbor(NN) 검색보다 훨씬 빠르게, 그러나 완전히 정확하지는 않은(대략 95~99% 정확도) 결과를 반환하는" 벡터 검색 알고리즘입니다. 100만 개 또는 10억 개의 벡터에서 "가장 비슷한 K개를 찾아라"는 Query를 생각해봅시다. 정확히 하려면 100만~10억 번의 거리 계산을 해야 합니다. ANN은 군집화, 그래프 탐색, 해시 등의 기법으로 거의 정확한 결과를 수 밀리초 내에 반환합니다. **벡터 데이터베이스의 핵심 기술**입니다.
Ⅰ. 정확히 찾기 vs 빠르게 찾기: KNN의 딜레마
정확한 Nearest Neighbor(NN) 검색은 모든 벡터와 거리를 계산합니다.
[KNN vs ANN: 시간 복잡도 비교]
┌─────────────────────────────────────────────────────────────────┐
│ 벡터 규모별 검색 시간 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 벡터 수 KNN (정확) ANN (근사) │
│ ───────── ───────────────── ───────────────── │
│ 1,000 1,000 계산 ~20 계산 (2%) │
│ 1,000,000 1,000,000 계산 ~20,000 계산 (2%) │
│ 1,000,000,000 1,000,000,000 계산 ~20,000,000 계산 (2%) │
│ │
│ 실제 소요 시간 (1회 Query 기준): │
│ - KNN 1M 벡터: ~30초 ~ 수십 초 │
│ - ANN 1M 벡터: ~5밀리초 ~ 수십 밀리초 │
│ │
│ 정확도: │
│ - KNN: 100% (정확히 K개 반환) │
│ - ANN: 95~99% (대부분 정확, 소수 오류 가능) │
│ │
└─────────────────────────────────────────────────────────────────┘
정확도와 속도의 Trade-off: ANN은 **"거의 정확한 결과를 엄청나게 빠르게"** 반환합니다. 99%의 정확도로 100배 빠른 것이 многи 应用에서 훨씬 유용합니다.
Ⅱ. ANN 알고리즘 분류
[ANN 알고리즘 주요 분류]
┌─────────────────────────────────────────────────────────────────┐
│ ANN 알고리즘 분류 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 1. 트리 기반 (Tree-based) │
│ - KD-Tree: k-차원 공간 분할 트리 │
│ - Ball Tree: 초구(Hypersphere) 분할 │
│ - ANNOY: Spotify의 근사 nearest neighbor │
│ ※ 저차원(수십 차원)에서 효과적, 고차원에서 효율 저하 │
│ │
│ 2. 그래프 기반 (Graph-based) │
│ - HNSW: 계층적 탐색 가능 세계 (가장 인기) │
│ - NSW: Navigable Small World │
│ ※ 고차원에서도 효과적, 메모리 사용량 많음 │
│ │
│ 3. 해시 기반 (Hash-based) │
│ - LSH: 지역 민감 해시 (Locality-Sensitive Hashing) │
│ - PQ:.Product Quantization │
│ ※ 메모리 효율적, 대량 데이터에 적합 │
│ │
│ 4. 군집 기반 (Clustering-based) │
│ - IVF: Inverted File Index │
│ ※ 다른 인덱스와 결합하여 사용 │
│ │
└─────────────────────────────────────────────────────────────────┘
Ⅲ. HNSW: 가장 널리 사용되는 ANN 알고리즘
Hierarchical Navigable Small World(HNSW)는 그래프 기반 ANN의 대표주자입니다.
[HNSW 구조]
┌─────────────────────────────────────────────────────────────────┐
│ HNSW 다층 구조 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Layer 2 (최상위): │
│ ●━━━━━━━━━━━━━━━━━━━━● │
│ │ │
│ │ (상위 레벨ほど 넓은 범위에서 빠르게 탐색) │
│ │ │
│ ●━━━━━●━━━━━●━━━━━●━━━━━● │
│ │ │
│ │ │
│ ▼ │
│ Layer 1 (중간): │
│ ●━●━●━●━●━●━●━●━●━●━●━●━●━●━● │
│ │ │
│ │ (중간 레벨에서 지역적 탐색) │
│ │ │
│ ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● │
│ │ │
│ ▼ │
│ Layer 0 (최하위): │
│ ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● │
│ (세밀한 연결, 각 노드와 직접 연결된 최근접 이웃) │
│ │
└─────────────────────────────────────────────────────────────────┘
탐색 과정:
1. 랜덤 포인트에서 시작
2. Layer 2에서 가장 가까운 노드 탐색
3. 하위 레벨로 이동
4. Layer 1에서 가장 가까운 노드 탐색
5. 하위 레벨로 이동
6. Layer 0에서 최종 결과 도출
HNSW 핵심 파라미터:
# HNSW 파라미터 의미
index = hnswlib.init(space='cosine', dim=1536)
# M (M - Maximum connections): 각 노드의 연결 수
M=16 # 높을수록 정확도↑, 메모리↑
# efConstruction: 빌드 시 탐색 범위
efConstruction=200 # 높을수록 정확도↑, 빌드 시간↑
# efSearch: 검색 시 탐색 범위
efSearch=100 # 높을수록 정확도↑, 검색 시간↑
# 정확도와 성능의 Trade-off:
# M=16, efConstruction=200 → Recall~95% (일반적)
# M=32, efConstruction=400 → Recall~99% (고정확도)
Ⅳ. IVF: 군집 기반 ANN
Inverted File Index(IVF)는 군집화 기반 ANN입니다.
[IVF 동작原理]
┌─────────────────────────────────────────────────────────────────┐
│ IVF 구조 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 전체 벡터 공간: │
│ │
│ ●●● ●● ┌─────────────────────────────────────┐ │
│ ●●●●● ●● │ Centroid 0 │ │
│ ●●●●●●●●● │ [vectors belonging to cluster 0]│ │
│ ●●● ●● └──────────┬──────────────────────────┘ │
│ │ │
│ ●●● ●● ┌─────────────┴─────────────┐ │
│ ●●●●● ●● │ Centroid 1 │ │
│ ●●●●●●●● │ [cluster 1] │ │
│ ●●●●● ●● └─────────────┬─────────────┘ │
│ │ │
│ │ q (쿼리 벡터) │
│ ▼ │
│ 가장 가까운 Centroid 선택 │
│ (q와 centroid 1의 거리가 가장 가까움) │
│ │ │
│ ▼ │
│ Centroid 1에 속한 벡터들과만 거리 계산 │
│ (전체 스캔이 아닌 후보만 계산) │
│ │
└─────────────────────────────────────────────────────────────────┘
# IVF 파라미터
nlist=1024 # 군집 수 (벡터 수에 비례, 일반적으로 √N)
# 검색 시 nprobe 파라미터
nprobe=10 # 탐색할 군집 수 (높을수록 정확도↑, 속도↓)
Ⅴ. ANN의 실제 적용과 📢 비유
** ANN 성능 평가 지표:**
# Recall@K: ANN이 반환한 K개 중 실제 Nearest Neighbor의 비율
# 예: Recall@10 = 0.95 → ANN이 반환한 Top-10 중 95%가 실제 NN
# 실제 구현:
from sklearn.neighbors import NearestNeighbors
nn = NearestNeighbors(n_neighbors=10, metric='cosine')
nn.fit(vectors)
distances, indices = nn.kneighbors(query_vector) # 실제 NN
# ANN 결과와 비교하여 Recall 계산
인덱스 선택 가이드:
[인덱스 선택 기준]
고차원(数百~数千) + 고정확도 → HNSW
- Milvus, Weaviate, Qdrant 등主流 벡터 DB의 기본
- 메모리 사용량 많음 (전체 인덱스를 메모리에 올려야)
대량 데이터 + 메모리 제약 → IVF + PQ
- Faiss에서 주로 사용
- 디스크 기반也可能
- 메모리 효율적
저차원(数十) + 단순한 구조 → KD-Tree, ANNOY
- 50차원 이하에서 효과적
- ANN(Approximate Nearest Neighbors) 사용
📢 섹션 요약 비유: ANN은 **"大型 도서관에서司書의 直感的 검색에 비유"**할 수 있습니다. (정확한) (KNN이) (图书管理员が全书籍を1冊ずつ確認してsimilar書を 찾는다") (数百만冊 全書籍 確認) (다면,ANN은) (熟练した) (司書が) (まず) (「この分野」「この时代」「この著者」) (という) (大分類) (で) (大きく) (絞込み) (→) (次に) (同じ) (分類の) (書籍を) (实际的) (確認) (して) (similar書) (を見つける) (것) (입니다) (대략) (95~99%) (정확히) (맞지만) (수) (밀리초) (안에) (결과를) (얻을) (수) (있습니다) ())。) (다만) (가끔) (「類似書」として_) (无误ではない) (書籍) (을) (추천) (하는) (경우) (도) (있다는) (점을) (감안) (해야) (합니다) ())_。