IVF(Inverted File Index)는 vector space를 여러 centroid 또는 cluster로 나눈 뒤, query와 가까운 cluster 안에서만 후보를 찾는 ANN indexing 방식이다. faiss에서 자주 쓰이며, exhaustive search보다 빠르지만 nlist, nprobe 설정에 따라 recall과 latency가 크게 달라진다.
1 min read
IVF(Inverted File Index)는 vector space를 여러 centroid 또는 cluster로 나눈 뒤, query와 가까운 cluster 안에서만 후보를 찾는 ANN indexing 방식이다. faiss에서 자주 쓰이며, exhaustive search보다 빠르지만 nlist, nprobe 설정에 따라 recall과 latency가 크게 달라진다.
...oximate Nearest Neighbor)은 정확한 nearest neighbor를 전수 계산하지 않고, 충분히 가까운 후보를 빠르게 찾는 검색 방식이다. Retrieval에서는 HNSW, IVF, faiss, scann, Vamana 같은 index가 dense embedding search의 latency와 recall을 결정한다.
...은 라이브러리와 달리, 한 알고리즘만 다루는 대신 그 경로를 얇게 유지한 것이 특징이다. 의존성이 거의 없어 빌드가 간단하고, 질의당 오버헤드가 작다. 언제 faiss 대신 쓰나 faiss 는 IVF, PQ 압축, GPU 실행, 여러 인덱스 조합 등 선택지가 넓다. 데이터가 아주 크거나 메모리를 줄여야 하면 그쪽이 맞다. 반대로 다음 조건에서는 hnswlib 이 유리하다.
Milvus는 대규모 vector search를 위한 vector database다. 내부적으로 HNSW, IVF, quantization 계열 index를 선택해 사용할 수 있고, retrieval system에서는 faiss 같은 라이브러리보다 운영 기능이 더 필요한 경우 비교 대상이 된다.
...2Vec, Gemini Embedding - Generalizable Embeddings from Gemini 같은 embedding model로 확장된다. 실제 serving에서는 HNSW, IVF, faiss, scann, Vamana 같은 indexing 전략이 품질과 latency를 좌우한다. Multi-vector retrieval은 single-vector embedding의 정...
ANN(Approximate Nearest Neighbor)은 정확한 nearest neighbor를 전수 계산하지 않고, 충분히 가까운 후보를 빠르게 찾는 검색 방식이다.
페북 (현 메타) 에서 만든 ANN 라이브러리. ColBERT 논문에서 빠른 retrieval 을 위해 faiss IVFPQ 버전을 사용했다고 한다. 네이버에서는 4ms 도 느리다고 판단하고, 보다 빠른 검색을 위해 Hnswlib 을 사용하는 것 같다.
Milvus는 대규모 vector search를 위한 vector database다.
HNSW 알고리즘만 구현해 놓은 C++ 헤더 전용 라이브러리다. Python 바인딩을 제공하며, HNSW 논문 저자인 Yury Malkov 가 직접 만들었다.
We can split ANN algorithms into three distinct categories; trees, hashes, and graphs. HNSW slots into the graph category.
Hierarchical Navigable Small World (HNSW) graphs are among the top-performing indexes for vector similarity search (Approximate Nearest Neighbor).
(1) Scann 구글에서 만든 ANN 라이브러리. 2022 년 기준 벤치마크 상으로 가장 좋은 성능을 내고 있다. (2) 튜닝하기 데이터가 100k 개 이상일 경우, AH 로 점수를 계산하고 rescore 절차를 거쳐야 한다.
What is Annoy spotify 에서 만든 라이브러리로 유사한 벡터들을 빠르게 찾아주는 ANN 라이브러리.
Non-Metric Space Library (NMSLIB) is an efficient cross-platform similarity search library and a toolkit for evaluation of similarity search methods.
비슷한 벡터일수록 같은 해시 버킷에 들어갈 확률이 높아지도록 설계한 해싱 기법이다. ANN 검색의 한 방법으로 쓴다. 일반적인 해시 함수는 입력이 조금만 달라도 결과가 완전히 달라지도록 설계된다. 충돌을 피하는 것이 목적이기 때문이다.