milvus, weaviate 같은 벡터 데이터베이스가 내부 엔진의 하나로 hnswlib 을 쓰기도 한다. References
HNSW 알고리즘만 구현해 놓은 C++ 헤더 전용 라이브러리다. Python 바인딩을 제공하며, HNSW 논문 저자인 Yury Malkov 가 직접 만들었다.
IVF(Inverted File Index)는 vector space를 여러 centroid 또는 cluster로 나눈 뒤, query와 가까운 cluster 안에서만 후보를 찾는 ANN indexing 방식이다. faiss에서 자주 쓰이며, exhaustive search보다 빠르지만 nlist , nprobe...
페북 (현 메타) 에서 만든 ANN 라이브러리.
Hierarchical Navigable Small World (HNSW) graphs are among the top-performing indexes for vector similarity search (Approximate Nearest Neighbor).
ANN(Approximate Nearest Neighbor)은 정확한 nearest neighbor를 전수 계산하지 않고, 충분히 가까운 후보를 빠르게 찾는 검색 방식이다. Retrieval에서는 HNSW, IVF, faiss, scann, Vamana 같은 index가 dense embedding search의...
We can split ANN algorithms into three distinct categories; trees, hashes, and graphs. HNSW slots into the graph category.
데이터를 정의할 class object 를 정의해야한다.
구글에서 만든 ANN 라이브러리. 2022 년 기준 벤치마크 상으로 가장 좋은 성능을 내고 있다.
Vamana : Microsoft Research에서 개발한 Graph-based ANN 알고리즘 . DiskANN의 핵심 인덱싱 알고리즘으로, HNSW와 달리 Flat Graph 구조를 사용하여 디스크 기반 검색에 최적화됨. Billion-scale 벡터 검색에서 단일 노드로 5000+ QPS, 95%+...
비슷한 벡터일수록 같은 해시 버킷에 들어갈 확률이 높아지도록 설계한 해싱 기법이다. ANN 검색의 한 방법으로 쓴다.