hnswlib 개요 — 헤더 전용 HNSW 구현

hnswlib 개요 — 헤더 전용 HNSW 구현

hnswlib은 HNSW(Hierarchical Navigable Small World) 그래프 기반의 고속 근사 최근접 이웃 검색 라이브러리예요. 헤더 전용 C++ 구현에 파이썬 바인딩을 붙이고, 삽입과 업데이트를 지원한다는 점이 특징이에요.

출처: https://github.com/nmslib/hnswlib

주요 특징을 짚어볼게요.

  1. 가볍고 헤더 전용 — C++ 11 외에 의존성이 없어요.
  2. 다양한 인터페이스 — C++, Python을 기본 지원하고 Java, R은 외부 지원이 있어요.
  3. 증분 인덱스 — 인덱스 구성과 요소 업데이트를 완전히 지원하고, 요소 삭제(인덱스에 표시 후 다른 요소로 교체 가능)도 돼요. Python 인덱스는 pickle로 직렬화할 수 있어요.
  4. 커스텀 거리 — C++에서 사용자 정의 거리 함수를 쓸 수 있어요.
  5. 메모리 효율 — 기존 nmslib 구현보다 메모리 사용이 훨씬 적고 빌드가 빨라요.

Python 바인딩은 세 가지 거리 측도를 지원해요.

Distance parameter Equation
Squared L2 'l2' d = sum((Ai-Bi)^2)
Inner product 'ip' d = 1.0 - sum(Ai*Bi)
Cosine distance 'cosine' d = 1.0 - sum(AiBi) / sqrt(sum(AiAi) * sum(Bi*Bi))

한 가지 주의할 점은 inner product는 실제 거리(metric)가 아니라는 거예요. 어떤 요소는 자기 자신보다 다른 요소에 더 가까울 수 있죠. 그래서 자기 자신보다 가까운 요소가 없는 것들만 남기면 검색 속도를 높일 수 있어요.

hnswlib.Index(space, dim)으로 space('l2', 'ip', 'cosine')와 차원 dim을 지정해 인덱스를 만들고, init_index로 용량을 잡고 add_items로 데이터를 넣고 knn_query로 검색해요.

더 알아보기