Zzong's Notes

Approximate Nearest Neighbor

최초 작성 마지막 수정 읽는 데 1분

노트 편집 ↗

링크된 언급

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

구글에서 만든 ANN 라이브러리. 2022 년 기준 벤치마크 상으로 가장 좋은 성능을 내고 있다.

locality sensitive hashing

비슷한 벡터일수록 같은 해시 버킷에 들어갈 확률이 높아지도록 설계한 해싱 기법이다. ANN 검색의 한 방법으로 쓴다.

faiss

페북 (현 메타) 에서 만든 ANN 라이브러리.

ANN

ANN(Approximate Nearest Neighbor)은 정확한 nearest neighbor를 전수 계산하지 않고, 충분히 가까운 후보를 빠르게 찾는 검색 방식이다. Retrieval에서는 HNSW, IVF, faiss, scann, Vamana 같은 index가 dense embedding search의...

milvus

Milvus는 대규모 vector search를 위한 vector database다. 내부적으로 HNSW, IVF, quantization 계열 index를 선택해 사용할 수 있고, retrieval system에서는 faiss 같은 라이브러리보다 운영 기능이 더 필요한 경우 비교 대상이 된다.

Hnswlib

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

IVF

IVF(Inverted File Index)는 vector space를 여러 centroid 또는 cluster로 나눈 뒤, query와 가까운 cluster 안에서만 후보를 찾는 ANN indexing 방식이다. faiss에서 자주 쓰이며, exhaustive search보다 빠르지만 nlist , nprobe...

Vamana

Vamana : Microsoft Research에서 개발한 Graph-based ANN 알고리즘 . DiskANN의 핵심 인덱싱 알고리즘으로, HNSW와 달리 Flat Graph 구조를 사용하여 디스크 기반 검색에 최적화됨. Billion-scale 벡터 검색에서 단일 노드로 5000+ QPS, 95%+...

maximum inner product search

최대 내적 검색(Maximum Inner Product Search, MIPS)은 주어진 쿼리 벡터와 데이터베이스 내의 수많은 데이터 벡터들 사이에서, 내적(inner product) 값이 가장 큰 벡터를 찾는 문제를 의미합니다. 이 기술은 단순한 유사도 측정을 넘어 추천 시스템, 자연어 처리(NLP), 컴퓨터...