계층적 내비게이션 가능한 소규모 세계(HNSW)는 근사 최근접 이웃 검색을 위한 알고리즘이다. 이 알고리즘은 대규모 컬렉션에서 쿼리 항목과 유사한 항목을 찾는 데 사용되며, 쿼리를 모든 항목과 하나씩 비교하지 않는다. 이 알고리즘은 문서, 이미지, 노래, 사용자 프로필과 같은 항목이 벡터라고 하는 숫자 목록으로 표현되는 벡터 데이터 검색에 일반적으로 사용된다. 유사한 벡터를 가진 항목은 벡터를 생성한 모델에 따라 유사한 것으로 간주되며, HNSW는 특히 대규모 데이터셋에서 이러한 벡터를 빠르게 검색하는 방법을 제공한다.
HNSW는 벡터를 그래프에 저장한다. 각 벡터는 노드이며, 링크는 일부 근처 벡터와 연결된다. 그래프는 여러 계층으로 구성된다: 상위 계층은 더 적은 노드를 포함하며 대략적인 지도 역할을 하고, 하위 계층은 모든 노드를 포함하며 더 상세한 보기를 제공한다. 검색은 상위 계층에서 시작하여 쿼리에 더 가까운 노드로 링크를 따라 이동하고, 하위 계층에서 이 과정을 반복하여 가능한 최근접 이웃 집합을 찾을 때까지 진행한다
배경
최근접 이웃 검색 문제는 데이터셋에서 어떤 항목이 쿼리 항목과 가장 가까운지 묻는다. 직접 검색은 데이터셋의 모든 항목과 쿼리를 비교할 수 있지만, 데이터셋이 크면 느려진다. k-d 트리와 R-트리와 같은 공간 트리 기반의 정확한 검색 방법은 고차원 데이터에서 효과가 떨어질 수 있으며, 이는 차원의 저주와 관련된 문제이다. 근사 최근접 이웃 방법은 속도나 자원 사용을 위해 일부 정확성을 희생한다. 항상 정확한 가장 가까운 항목을 보장하는 대신, 가까운 항목을 빠르게 반환하려고 한다. 다른 근사 방법으로는 지역성 민감 해싱과 곱 양자화가 있다.
HNSW는 소규모 세계 네트워크와 내비게이션 가능한 그래프에 대한 연구를 기반으로 한다. 소규모 세계 그래프에서 대부분의 노드는 짧은 링크 체인을 통해 다른 노드에서 도달할 수 있다. 내비게이션 가능한 그래프에서 검색 절차는 로컬 정보를 사용하여 대상으로 이동할 수 있다. 존 클라인버그의 소규모 세계 네트워크 내비게이션에 대한 연구는 이 연구 분야의 중요한 예이다. 이후 연구는 그래프를 탐욕적으로 더 쉽게 내비게이션할 수 있도록 링크를 추가하는 방법을 연구했다. HNSW 알고리즘은 유사성 검색을 위한 기존 내비게이션 가능한 소규모 세계 방법을 확장하여 그래프 계층의 계층 구조를 추가한다. 이 계층 구조는 알고리즘이 하위 계층에서 더 상세한 검색을 수행하기 전에 그래프의 좋은 영역을 찾는 데 도움이 된다
알고리즘
HNSW는 근접 그래프를 기반으로 한다. 이 그래프에서 근처 벡터는 에지로 연결된다. 알고리즘은 이러한 에지를 사용하여 데이터셋을 이동하며, 모든 벡터를 스캔하지 않는다. 그래프는 계층적이다. 모든 벡터는 하위 계층에 나타난다. 일부 벡터는 상위 계층에도 배치되며, 계층이 올라갈수록 더 적은 벡터가 나타난다. 상위 계층은 데이터셋 전체에 걸친 장거리 이동을 허용하고, 하위 계층은 유망한 후보 근처에서 더 상세한 검색을 허용한다. 일반적인 검색은 다음과 같이 진행된다:
- 검색은 최상위 계층의 진입점에서 시작한다.
- 각 단계에서 알고리즘은 이웃 노드를 살펴보고 쿼리에 더 가까운 이웃으로 이동한다.
- 해당 계층에서 더 가까운 이웃을 찾을 수 없으면, 다음 계층으로 이동한다.
- 하위 계층에서는 더 넓은 후보 노드 집합을 탐색하고 가장 가까운 후보를 반환한다.
이 검색 전략은 종종 탐욕적 내비게이션으로 설명된다. 알고리즘은 그래프 구조를 사용하여 쿼리 지점에 접근하면서 로컬에서 더 나은 노드를 반복적으로 선택한다.
구축 및 매개변수
HNSW 그래프는 점진적으로 구축된다. 새 벡터가 삽입될 때, 알고리즘은 최대 계층을 할당하고, 근처 기존 노드를 검색하며, 새 노드가 나타나는 각 계층에서 선택된 이웃에 연결한다. 구현은 일반적으로 속도, 정확성, 메모리 사용량, 구축 시간 간의 균형을 제어하는 매개변수를 노출한다. 그래프 연결 수가 많으면 재현율이 향상될 수 있지만 더 많은 메모리가 필요하다. 검색 후보 목록이 크면 정확성이 향상될 수 있지만 쿼리가 느려진다. 구축 후보 목록이 크면 그래프 품질이 향상될 수 있지만 인덱스 구축이 느려진다. HNSW는 근사적이므로 결과가 완전한 정확한 검색과 항상 동일하지는 않다. 실제 성능은 데이터셋, 거리 측정, 구현, 매개변수 설정에 따라 달라진다. 벤치마킹 연구는 HNSW 기반 라이브러리가 근사 최근접 이웃 방법 중 강력한 성능을 보인다는 것을 발견했지만, 최악의 경우 성능은 일반적인 벤치마크 데이터셋의 성능과 다를 수 있다.
벡터 검색 시스템에서의 사용
HNSW는 고차원 벡터를 저장하고 검색하는 시스템에서 인덱스로 사용된다. 이러한 시스템에는 벡터 데이터베이스, 검색 엔진, 데이터베이스 확장이 포함된다. 일반적인 용도로는 의미 검색, 추천 시스템, 이미지 유사성 검색, 검색 증강 생성이 있으며, 이는 생성형 AI 및 대규모 언어 모델 파이프라인에서 자주 적용된다. 여러 소프트웨어 프로젝트가 HNSW를 구현하거나 지원한다. 라이브러리에는 원래 HNSW 저자와 관련된 hnswlib와 FAISS가 포함된다. HNSW 지원을 문서화한 데이터베이스 및 검색 시스템에는 Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant, Redis가 포함된다. 이러한 도구는 생산 머신러닝 워크로드를 위해 Amazon Web Services, Microsoft Azure, Google Cloud와 같은 클라우드 플랫폼에 일반적으로 배포된다.
같이 보기
- 근사 최근접 이웃 검색
- 벡터 데이터베이스
- 지역성 민감 해싱
- 곱 양자화