1 min read
hashing trick salt locality sensitive hashing
...g. Euclidean distance). 데이터 차원이 커질수록 curse of dimensionality 에 의해 성능 저하가 발생한다. 이에 대한 이슈를 해소하기 위해 locality sensitive hashing 을 이용하기도 한다. KNN 은 학습 과정에서 Lazy learning 방법을 사용한다.
...서 내적이 큰 쌍일수록 새로운 공간에서도 거리가 가깝도록 설계합니다. 이러한 방식은 HNSW 같은 그래프 기반 알고리즘에도 적용 가능합니다. A.1.3.2) 지역 민감 해싱(Locality Sensitive Hashing, LSH) LSH는 서로 비슷한(유사도가 높은) 벡터들이 동일 해시 버킷에 저장될 확률이 높아지도록 설계된 해싱 기법입니다. 특히 비대칭 LSH(Asymmetric LSH)...
Approximate Nearest Neighbor We can split ANN algorithms into three distinct categories; trees, hashes, and graphs.
Hnswlib HNSW 기반 C++ 라이브러리 B) References.
ANN ANN(Approximate Nearest Neighbor)은 정확한 nearest neighbor를 전수 계산하지 않고, 충분히 가까운 후보를 빠르게 찾는 검색 방식이다.
(1) Scann 구글에서 만든 ANN 라이브러리. 2022 년 기준 벤치마크 상으로 가장 좋은 성능을 내고 있다. B) (2) 튜닝하기 데이터가 100k 개 이상일 경우, AH 로 점수를 계산하고 rescore 절차를 거쳐야 한다.
최대 내적 검색(Maximum Inner Product Search, MIPS)은 주어진 쿼리 벡터와 데이터베이스 내의 수많은 데이터 벡터들 사이에서, 내적(inner product) 값이 가장 큰 벡터를 찾는 문제를 의미합니다.
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.
What is Annoy spotify 에서 만든 라이브러리로 유사한 벡터들을 빠르게 찾아주는 ANN 라이브러리.
Milvus Milvus는 대규모 vector search를 위한 vector database다.
HNSW Hierarchical Navigable Small World (HNSW) graphs are among the top-performing indexes for vector similarity search (Approximate Nearest Neighbor).
Faiss 페북 (현 메타) 에서 만든 ANN 라이브러리. ColBERT 논문에서 빠른 retrieval 을 위해 faiss IVFPQ 버전을 사용했다고 한다. 네이버에서는 4ms 도 느리다고 판단하고, 보다 빠른 검색을 위해 Hnswlib 을 사용하는 것 같다.