Zzong's Notes

Approximate Nearest Neighbor

1 min read

링크된 언급

4
faiss

페북 (현 메타) 에서 만든 ANN 라이브러리. ColBERT 논문에서 빠른 retrieval 을 위해 faiss IVFPQ 버전을 사용했다고 한다. 네이버에서는 4ms 도 느리다고 판단하고, 보다 빠른 검색을 위해 Hnswlib 을 사용하는 것 같다. Faiss의 핵심 동작 원리: IVF, PQ Indexing IVF (Inverted File Index): 검색 공간을 줄이는 ‘클러스터링...

HNSW

...le Small World (HNSW) graphs are among the top-performing indexes for vector similarity search (Approximate Nearest Neighbor). HNSW는 현재 가장 널리 쓰이는 ANN 알고리즘 중 하나로, 그래프 기반 알고리즘입니다.

locality sensitive hashing

비슷한 벡터일수록 같은 해시 버킷에 들어갈 확률이 높아지도록 설계한 해싱 기법이다. ANN 검색의 한 방법으로 쓴다. 일반적인 해시 함수는 입력이 조금만 달라도 결과가 완전히 달라지도록 설계된다. 충돌을 피하는 것이 목적이기 때문이다. LSH 는 정반대로, 가까운 것끼리 일부러 충돌시키는 것이 목적이다. 왜 필요한가 차원이 높아지면 모든 점 사이의 거리가 서로 비슷해져서 “가까운 이웃” 이라...

scann

(1) Scann 구글에서 만든 ANN 라이브러리. 2022 년 기준 벤치마크 상으로 가장 좋은 성능을 내고 있다. (2) 튜닝하기 데이터가 100k 개 이상일 경우, AH 로 점수를 계산하고 rescore 절차를 거쳐야 한다. AH 로 점수를 계산할 때, dimensions_per_block 은 2 로 설정하자. 파티셔닝 시에 num_leaves 는 데이터포인트 개수의 제곱근 수 (squa...

함께 보면 좋은 글

HNSW

Hierarchical Navigable Small World (HNSW) graphs are among the top-performing indexes for vector similarity search (Approximate Nearest Neighbor).

scann

(1) Scann 구글에서 만든 ANN 라이브러리. 2022 년 기준 벤치마크 상으로 가장 좋은 성능을 내고 있다. (2) 튜닝하기 데이터가 100k 개 이상일 경우, AH 로 점수를 계산하고 rescore 절차를 거쳐야 한다.

locality sensitive hashing

비슷한 벡터일수록 같은 해시 버킷에 들어갈 확률이 높아지도록 설계한 해싱 기법이다. ANN 검색의 한 방법으로 쓴다. 일반적인 해시 함수는 입력이 조금만 달라도 결과가 완전히 달라지도록 설계된다. 충돌을 피하는 것이 목적이기 때문이다.

faiss

페북 (현 메타) 에서 만든 ANN 라이브러리. ColBERT 논문에서 빠른 retrieval 을 위해 faiss IVFPQ 버전을 사용했다고 한다. 네이버에서는 4ms 도 느리다고 판단하고, 보다 빠른 검색을 위해 Hnswlib 을 사용하는 것 같다.

ANN

ANN(Approximate Nearest Neighbor)은 정확한 nearest neighbor를 전수 계산하지 않고, 충분히 가까운 후보를 빠르게 찾는 검색 방식이다.

milvus

Milvus는 대규모 vector search를 위한 vector database다.

Hnswlib

HNSW 알고리즘만 구현해 놓은 C++ 헤더 전용 라이브러리다. Python 바인딩을 제공하며, HNSW 논문 저자인 Yury Malkov 가 직접 만들었다.

Non-Metric Space Library

Non-Metric Space Library (NMSLIB) is an efficient cross-platform similarity search library and a toolkit for evaluation of similarity search methods.

IVF

IVF(Inverted File Index)는 vector space를 여러 centroid 또는 cluster로 나눈 뒤, query와 가까운 cluster 안에서만 후보를 찾는 ANN indexing 방식이다.