HNSWLib는 근사 최근접 이웃 검색을 위한 계층적 탐색 가능 소규모 세계(HNSW) 알고리즘을 구현하는 헤더 전용 C++ 라이브러리입니다. 이 라이브러리는 대규모 벡터 데이터 컬렉션에서 쿼리 항목과 유사한 항목을 찾기 위해 설계되었으며, 쿼리를 모든 항목과 개별적으로 비교하지 않습니다. 속도와 확장성이 중요한 기계 학습 시스템, 인공 지능 애플리케이션 및 벡터 데이터베이스에서 일반적으로 사용됩니다.
HNSWLib가 구현하는 HNSW 알고리즘은 벡터를 다층 그래프 구조에 저장합니다. 각 벡터는 노드가 되고, 링크는 이를 인근 벡터와 연결합니다. 상위 레이어에는 더 적은 노드가 포함되어 대략적인 지도 역할을 하며, 하위 레이어에는 모든 노드가 포함되어 상세 검색을 수행합니다. 검색은 상위 레이어에서 시작하여 쿼리에 더 가까운 노드로 링크를 따라 이동한 다음, 하위 레이어에서 이 과정을 반복하여 가능성이 높은 최근접 이웃 집합을 식별합니다.
배경
최근접 이웃 검색 문제는 데이터 세트에서 어떤 항목이 쿼리 항목에 가장 가까운지 묻습니다. 직접 검색은 쿼리를 모든 항목과 비교하므로 대규모 데이터 세트에서는 느려집니다. k-d 트리나 R-트리와 같은 공간 트리를 사용하는 정확한 방법은 차원의 저주로 인해 고차원 데이터에서 효과를 잃습니다. 근사 최근접 이웃 방법은 정확성을 속도와 맞바꾸어 절대적으로 가장 가까운 항목을 보장하는 대신 가까운 항목을 빠르게 반환합니다.
HNSW는 소규모 세계 네트워크와 탐색 가능한 그래프에 대한 연구를 기반으로 합니다. 소규모 세계 그래프에서 대부분의 노드는 짧은 링크 체인을 통해 연결됩니다. Jon Kleinberg의 소규모 세계 네트워크 탐색 연구는 탐욕적으로 탐색하기 쉬운 링크를 추가하는 이후 연구에 영향을 미쳤습니다. HNSW 알고리즘은 그래프 레이어의 계층 구조를 추가하여 이전의 탐색 가능한 소규모 세계 방법을 확장하며, 이는 상세 검색 전에 좋은 영역을 찾는 데 도움이 됩니다.
알고리즘
HNSWLib는 인접 벡터가 가장자리로 연결된 근접 그래프를 사용합니다. 알고리즘은 모든 벡터를 스캔하는 대신 이러한 가장자리를 통해 데이터 세트를 이동합니다. 그래프는 계층적입니다. 모든 벡터는 하위 레이어에 나타나며, 일부 벡터는 레이어가 올라갈수록 더 적은 벡터로 상위 레이어에도 나타납니다. 상위 레이어는 장거리 이동을 가능하게 하고, 하위 레이어는 유망한 후보 근처에서 상세 검색을 허용합니다.
일반적인 검색은 최상위 레이어의 진입점에서 시작됩니다. 각 단계에서 알고리즘은 인접 노드를 검사하고 쿼리에 더 가까운 노드로 이동합니다. 해당 레이어에서 더 가까운 이웃이 없으면 다음 레이어로 내려갑니다. 하위 레이어에서는 더 넓은 후보 집합을 탐색하고 발견된 가장 가까운 후보를 반환합니다. 이 탐욕적 탐색은 쿼리 지점에 접근하기 위해 지역적으로 더 나은 노드를 반복적으로 선택합니다.
구축 및 매개변수
HNSW 그래프는 증분 방식으로 구축됩니다. 새 벡터를 삽입할 때 알고리즘은 최대 레이어를 할당하고, 기존 인근 노드를 검색한 다음, 새 노드가 나타나는 각 레이어에서 선택된 이웃에 연결합니다. 구현은 속도, 정확성, 메모리 사용 및 구축 시간 간의 균형을 제어하는 매개변수를 노출합니다. 더 높은 그래프 연결은 재현율을 향상시키지만 더 많은 메모리가 필요합니다. 더 큰 검색 후보 목록은 정확성을 향상시키지만 쿼리를 느리게 합니다. 더 큰 구축 후보 목록은 그래프 품질을 향상시키지만 인덱스 구축을 느리게 합니다.
HNSW는 근사적이므로 결과는 정확한 검색과 다를 수 있습니다. 실제 성능은 데이터 세트 특성, 거리 측정, 구현 품질 및 매개변수 설정에 따라 달라집니다. 벤치마킹 연구에 따르면 HNSW 기반 라이브러리는 근사 최근접 이웃 방법 중 강력한 성능을 보이지만, 최악의 경우 성능은 일반적인 벤치마크 결과와 다를 수 있습니다.
벡터 검색 시스템에서의 사용
HNSWLib는 고차원 벡터를 저장하고 검색하는 시스템에서 인덱스로 사용되며, 벡터 데이터베이스, 검색 엔진 및 데이터베이스 확장을 포함합니다. 일반적인 애플리케이션에는 의미 검색, 추천 시스템, 이미지 유사성 검색 및 검색 증강 생성이 포함됩니다. 이 라이브러리는 원래 HNSW 저자와 관련이 있으며 생산 환경에서 널리 채택되었습니다.
여러 소프트웨어 프로젝트가 HNSW를 구현하거나 지원합니다. 라이브러리에는 HNSWLib 및 FAISS가 포함됩니다. HNSW 지원을 문서화한 데이터베이스 및 검색 시스템에는 Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant 및 Redis가 포함됩니다. 이러한 시스템은 대규모 언어 모델 검색에서 생성형 AI 파이프라인에 이르는 애플리케이션에서 빠른 근사 검색을 위해 HNSW를 활용합니다.
같이 보기
- 근사 최근접 이웃 검색
- 벡터 데이터베이스
- 지역성 기반 해싱
- 곱 양자화