HNSW (Hierarchical Navigable Small World)

📖 상세 설명

HNSW(Hierarchical Navigable Small World)는 고차원 벡터 공간에서 근사 최근접 이웃(ANN)을 빠르게 찾는 그래프 기반 알고리즘입니다. 2016년 Yu. A. Malkov와 D. A. Yashunin이 발표했으며, 현재 가장 널리 사용되는 벡터 검색 알고리즘 중 하나입니다.

HNSW는 Small World 네트워크 이론에 기반합니다. 계층적 구조로 그래프를 구성하여 상위 레이어에서는 멀리 점프하고, 하위 레이어로 내려가면서 정밀하게 탐색합니다. 이 방식으로 O(log N) 시간 복잡도의 검색이 가능합니다.

핵심 파라미터는 M(각 노드의 최대 연결 수)과 ef(검색 시 탐색할 후보 수)입니다. M이 클수록 정확도가 높아지지만 메모리를 많이 사용하고, ef가 클수록 검색 정확도가 높아지지만 속도가 느려집니다.

Pinecone, Weaviate, Milvus, Qdrant 등 대부분의 벡터 데이터베이스가 HNSW를 기본 인덱스로 사용합니다. 100억 개 이상의 벡터에서도 밀리초 단위 검색이 가능해 RAG, 추천 시스템, 이미지 검색 등에 필수적인 기술입니다.

💻 코드 예제

import numpy as np
import hnswlib

# HNSW 인덱스 생성 및 검색 예제
def create_hnsw_index(vectors, dim=128):
    num_elements = len(vectors)

    # HNSW 인덱스 초기화
    index = hnswlib.Index(space='cosine', dim=dim)

    # 인덱스 파라미터 설정
    # M: 노드당 연결 수 (높을수록 정확, 메모리 증가)
    # ef_construction: 인덱스 구축 시 탐색 범위
    index.init_index(
        max_elements=num_elements,
        ef_construction=200,
        M=16
    )

    # 벡터 추가
    ids = np.arange(num_elements)
    index.add_items(vectors, ids)

    # 검색 시 ef 파라미터 설정 (높을수록 정확, 느림)
    index.set_ef(100)

    return index

# 사용 예시
dim = 128
num_vectors = 100000
vectors = np.random.randn(num_vectors, dim).astype('float32')

# 인덱스 생성
index = create_hnsw_index(vectors, dim)

# 쿼리 벡터로 검색
query = np.random.randn(1, dim).astype('float32')
labels, distances = index.knn_query(query, k=10)

print(f"가장 유사한 10개 벡터 ID: {labels[0]}")
print(f"코사인 거리: {distances[0]}")

🗣️ 실무에서 이렇게 말하세요

벡터 DB 선정 회의에서

"1억 개 임베딩을 저장해야 하는데, HNSW 기반 인덱스가 필수예요. Milvus나 Qdrant가 HNSW를 잘 지원하고, ef와 M 파라미터 튜닝으로 recall 95% 이상 나옵니다."

기술 면접에서

"HNSW와 IVF의 차이는 구조입니다. IVF는 클러스터 기반으로 메모리 효율적이지만 recall이 낮고, HNSW는 그래프 기반으로 recall이 높지만 메모리를 더 사용합니다. 대부분의 경우 HNSW가 품질 면에서 유리합니다."

성능 최적화 논의에서

"검색 지연이 50ms인데 10ms 이하로 줄여야 해요. ef를 100에서 50으로 낮추면 속도는 빨라지지만 recall이 떨어지니, 먼저 벤치마크로 적절한 트레이드오프를 찾아야 합니다."

⚠️ 흔한 실수 & 주의사항

1

메모리 사용량

HNSW는 그래프 구조를 메모리에 유지해야 합니다. 1억 개 768차원 벡터는 약 300GB+ 메모리가 필요할 수 있으니 용량을 미리 계산하세요.

2

인덱스 구축 시간

대규모 데이터셋에서 HNSW 인덱스 구축은 수 시간이 걸릴 수 있습니다. 배치 삽입과 병렬 처리를 활용하세요.

3

파라미터 튜닝 필요

M, ef_construction, ef 파라미터는 데이터셋 특성에 따라 최적값이 다릅니다. 반드시 자체 벤치마크로 튜닝하세요.

🔗 관련 용어

📚 더 배우기

HNSW 원본 논문 (arXiv) hnswlib - 공식 Python 라이브러리 Pinecone - HNSW 알고리즘 가이드