1 min read
What is Annoy spotify 에서 만든 라이브러리로 유사한 벡터들을 빠르게 찾아주는 ANN 라이브러리
Query encoder가 query embedding을 만든다. Document/item encoder가 corpus embedding을 만든다. ANN index에서 query embedding과 가까운 후보를 찾는다. ranking 단계에서 lexical, behavioral, business feature와 함께 다시 정렬한다.
IVF(Inverted File Index)는 vector space를 여러 centroid 또는 cluster로 나눈 뒤, query와 가까운 cluster 안에서만 후보를 찾는 ANN indexing 방식이다.
(1) Scann 구글에서 만든 ANN 라이브러리. 2022 년 기준 벤치마크 상으로 가장 좋은 성능을 내고 있다. (2) 튜닝하기 데이터가 100k 개 이상일 경우, AH 로 점수를 계산하고 rescore 절차를 거쳐야 한다.
페북 (현 메타) 에서 만든 ANN 라이브러리. ColBERT 논문에서 빠른 retrieval 을 위해 faiss IVFPQ 버전을 사용했다고 한다. 네이버에서는 4ms 도 느리다고 판단하고, 보다 빠른 검색을 위해 Hnswlib 을 사용하는 것 같다.
What is Annoy spotify 에서 만든 라이브러리로 유사한 벡터들을 빠르게 찾아주는 ANN 라이브러리.
핵심 요약 Vamana: Microsoft Research에서 개발한 Graph-based ANN 알고리즘. DiskANN의 핵심 인덱싱 알고리즘으로, HNSW와 달리 Flat Graph 구조를 사용하여 디스크 기반 검색에 최적화됨.
Hierarchical Navigable Small World (HNSW) graphs are among the top-performing indexes for vector similarity search (Approximate Nearest Neighbor).
We can split ANN algorithms into three distinct categories; trees, hashes, and graphs. HNSW slots into the graph category.
Milvus는 대규모 vector search를 위한 vector database다.
HNSW 알고리즘만 구현해 놓은 C++ 헤더 전용 라이브러리다. Python 바인딩을 제공하며, HNSW 논문 저자인 Yury Malkov 가 직접 만들었다.
Non-Metric Space Library (NMSLIB) is an efficient cross-platform similarity search library and a toolkit for evaluation of similarity search methods.