HNSW: 수억 개의 벡터를 밀리초(millisecond) 안에 검색하는 비결

벡터 검색은 텍스트, 이미지, 오디오 등 다양한 데이터를 고차원 벡터(High-dimensional Vector)로 표현하여 의미적 유사성을 파악하는 기술이다. 코사인 유사도(Cosine Similarity) 또는 유클리드 거리(Euclidean Distance)를 사용하여 벡터 간의 거리를 측정하고, 가장 가까운 벡터를 찾아낸다. 이러한 방식은 키워드 기반 검색의 한계를 극복하고, 의미 기반 검색(Semantic Search)을 가능하게 한다. 특히, 추천 시스템, 이미지 유사성 검색, 이상 감지 등 다양한 분야에서 활용된다.

HNSW는 계층적 구조(Hierarchical Structure)를 활용하여 고속 검색을 가능하게 한다. 최상위 계층에서는 먼 거리를 이동하고, 하위 계층으로 내려가면서 정밀도를 높이는 방식으로 작동한다. 새로운 벡터를 삽입할 때, 지수적으로 감소하는 확률 분포(Exponentially Decaying Probability Distribution)를 사용하여 각 벡터에 무작위 최대 레이어를 할당한다. 이러한 계층적 구조는 검색 속도를 향상시키고, 근사 최근접 이웃(Approximate Nearest Neighbor) 검색을 효율적으로 수행할 수 있게 한다.

HNSW의 성능은 두 가지 주요 파라미터, 즉 각 노드가 유지하는 연결 수(M)와 검색 빔 너비(ef)에 의해 제어된다. M 값을 높이면 정확도가 향상되지만, 메모리 사용량이 증가하고 삽입 속도가 느려진다. ef 값을 높이면 더 많은 그래프를 탐색하여 정확도가 높아지지만, 거리 계산량이 증가한다. 일반적으로 M=16, ef=64로 시작하여, 필요에 따라 정확도와 속도 간의 트레이드오프(Trade-off)를 조절한다.

HNSW는 Pinecone, Weaviate, pgvector, Qdrant, Olingo와 같은 현대적인 벡터 데이터베이스에서 널리 사용된다. 이러한 데이터베이스는 수억 개의 벡터에 대해 밀리초(millisecond) 단위로 검색 결과를 반환할 수 있다. HNSW는 근사 검색(Approximate Search)을 통해 정확도를 약간 희생하는 대신, 계산 복잡도(Computational Complexity)를 크게 줄여 대규모 데이터셋에서도 빠른 검색 속도를 유지한다. 이는 대규모 데이터 처리(Large-scale Data Processing) 환경에서 매우 중요한 장점이다.