HNSW

개요

HNSW(Hierarchical Navigable Small World)는 고차원 벡터 공간에서 근사 최근접 이웃(Approximate Nearest Neighbor, ANN) 검색을 수행하는 그래프 기반 알고리즘이다. 계층적 그래프 구조를 활용하여 로그 복잡도의 검색 성능을 제공하며, 빠른 검색 속도와 높은 재현율(recall)로 현대 벡터 데이터베이스에서 가장 널리 사용되는 인덱싱 방식 중 하나다.

배경과 역사

• HNSW는 2016년 Yury Malkov와 Dmitry Yashunin이 논문 “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”에서 발표했다.
• NSW(Navigable Small World) 알고리즘과 확률적 스킵 리스트(Probabilistic Skip List)의 개념을 결합하여 개발되었다.
• Pinecone, Milvus, Weaviate, Vespa 등 주요 벡터 데이터베이스가 기본 인덱스로 채택하고 있다.
• 중간 크기의 벡터 데이터셋에서 특히 뛰어난 성능을 보이며, 다양한 도메인(임베딩 검색, 추천 시스템, 이미지 검색 등)에서 활용된다.

기본 구조

계층적 그래프

HNSW는 여러 계층(layer)으로 구성된 그래프 구조를 가진다:

• 최상위 계층: 가장 적은 노드, 가장 긴 연결(long-range links)
• 중간 계층: 점진적으로 노드 수 증가
• 최하위 계층: 모든 노드 포함, 가장 짧은 연결(short-range links)

각 노드는 벡터 하나를 나타내며, 계층 간 연결을 통해 빠른 탐색 경로를 형성한다.

Small World 속성

• Small World 네트워크: 높은 클러스터링 계수와 짧은 평균 경로 길이를 가진 네트워크
• 소셜 네트워크의 “6단계 분리 이론”과 유사한 원리
• 긴 거리의 “바로가기” 연결과 짧은 거리의 지역 연결을 동시에 활용

검색 알고리즘

1. 진입점 선택

최상위 계층의 진입점(entry node)에서 검색 시작

2. 탐욕적 검색 (Greedy Search)

각 계층에서:

1. 현재 노드의 이웃 중 쿼리 벡터와 가장 가까운 노드 선택
2. 더 가까운 노드가 없을 때까지 반복
3. 지역 최솟값(local minimum)에 도달하면 다음 계층으로 이동

3. 계층 하강

• 상위 계층: 긴 연결로 빠르게 대략적인 영역 탐색
• 하위 계층: 짧은 연결로 정밀한 최근접 이웃 탐색

4. 최종 결과

최하위 계층에서 k개의 최근접 이웃 반환

주요 파라미터

M (연결 수)

• 각 노드가 가질 수 있는 최대 양방향 연결 수
• 높을수록: 더 나은 재현율, 더 많은 메모리 사용
• 일반적 범위: 12~48
• 기본값: 16

efConstruction (구축 시 탐색 크기)

• 그래프 구축 중 후보 이웃 탐색 범위
• 높을수록: 더 나은 그래프 품질, 더 긴 구축 시간
• 일반적 범위: 100~500

efSearch (검색 시 탐색 크기)

• 검색 중 탐색할 후보 노드 수
• 높을수록: 더 나은 재현율, 더 긴 검색 시간
• 동적으로 조정 가능

복잡도 분석

연산	시간 복잡도	공간 복잡도
삽입	$O(\log N)$	$O(M\cdot N)$
검색	$O(\log N)$	$O(M\cdot N)$
삭제	$O(M\cdot \log N)$	-

• $N$: 데이터셋 크기
• $M$: 연결 수 파라미터

HNSW와 다른 알고리즘 비교

알고리즘	검색 속도	재현율	메모리 사용량	구축 시간
HNSW	매우 빠름	높음	높음	보통
IVF (Inverted File)	빠름	보통	낮음	빠름
NSW	빠름	높음	높음	빠름
LSH (Locality Sensitive Hashing)	보통	보통	낮음	매우 빠름
Brute Force	느림	완벽	매우 낮음	없음

장점과 단점

장점

• 로그 복잡도의 빠른 검색 성능
• 높은 재현율 (95~99% 이상 가능)
• 고차원 데이터에서도 성능 유지
• 동적 삽입/삭제 지원
• 파라미터 튜닝을 통한 성능-메모리 트레이드오프 조절

단점

• 높은 메모리 사용량 (각 노드당 $M$개의 연결 저장)
• 대규모 데이터셋에서 메모리 제약
• 구축 시간이 상대적으로 길 수 있음
• 완전한 정확도를 보장하지 않음 (근사 알고리즘)

최적화 및 변형

압축 기법

• Quantization: 벡터를 양자화하여 메모리 절감
• Product Quantization (PQ): 벡터를 서브벡터로 분할하여 압축
• DiskANN: 디스크 기반 저장으로 대규모 데이터셋 지원

하이브리드 접근

• HNSW + IVF: 1차 클러스터링 후 HNSW 적용
• HNSW + PQ: 메모리 효율성과 검색 성능 균형

구현 시 고려 사항

벡터 정규화

• 코사인 유사도 사용 시 벡터 정규화 권장
• L2 거리 사용 시 정규화 불필요

파라미터 튜닝 전략

1. M 선택: 데이터셋 크기와 메모리 제약 고려

   • 소규모 (<100K): M=16
   • 중규모 (100K~1M): M=32
   • 대규모 (>1M): M=48+

2. efConstruction: 그래프 품질 우선 시 높게 설정

   • 빠른 구축: 100~200
   • 균형: 200~400
   • 최고 품질: 400~800

3. efSearch: 실시간 조정 가능

   • 빠른 검색: k * 1~2
   • 균형: k * 10~20
   • 높은 재현율: k * 50~100

거리 메트릭 선택

• L2 (Euclidean): 절대 거리 중요 시
• IP (Inner Product): 내적 기반 유사도
• Cosine: 방향 유사도 (정규화된 IP)

메모리 관리

• 인메모리 vs. 디스크 기반 저장소 선택
• 벡터 압축 기법 적용 (PQ, Scalar Quantization)
• 배치 삽입으로 구축 효율성 향상

모니터링 지표

• 재현율(Recall): 정확도 측정
• QPS(Queries Per Second): 처리량
• P99 레이턴시: 응답 시간
• 메모리 사용량: 리소스 효율성

활용 사례

시맨틱 검색

• 텍스트 임베딩 기반 문서 검색
• 질의-응답 시스템
• BM25와 하이브리드 검색

추천 시스템

• 아이템 유사도 기반 추천
• 사용자 임베딩 매칭

이미지/비디오 검색

• 시각적 유사도 검색
• 얼굴 인식
• 중복 감지

멀티모달 검색

• 텍스트-이미지 크로스 검색
• CLIP 등 멀티모달 임베딩 활용

참고 자료

논문 및 학술 자료

• Malkov, Y. A., & Yashunin, D. A. (2016). “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs” - arXiv:1603.09320 - HNSW 원논문
• Malkov, Y., Ponomarenko, A., et al. (2014). “Approximate nearest neighbor algorithm based on navigable small world graphs” - Information Systems - NSW 알고리즘 논문

기술 문서 및 튜토리얼

• Pinecone: HNSW Tutorial - HNSW 작동 원리 및 FAISS 구현
• Milvus Blog: Understanding HNSW - HNSW 심층 분석
• Weaviate: HNSW Index - 실무 적용 가이드

구현 및 라이브러리

• hnswlib - C++ 기반 고성능 HNSW 구현체 (Python 바인딩 포함)
• FAISS - Meta의 벡터 검색 라이브러리 (HNSW 포함)