aNN(Approximate Nearest Neighbor)

 

kNN이란 ?

kNN이란 ? ( k-Nearest Neighbors )

 

 

위의 글에서 kNN에 대한 내용을 다뤘었다. 이번에는 kNN과 비슷하지만 '완벽'한 이웃보다는 '훌륭한' 이웃정도를  찾는 aNN에 대한 내용을 다룰까한다. 

하지만 많은 VectorDB 및 Search에 관련된 서비스들이 검색 내용이 너무 방대해지면서 속도가 느려지기 시작하였다.

따라서 Faiss, Annoy, Elasticsearch 등을 기반으로 aNN 의 개념으로 속도와 정확도를 트레이드오프 하기 시작하였다.

 

 

aNN은 이름과 같이 '근사 kNN'정도로 생각하면 된다. 약간의 손실이 있지만 앞서 kNN의 단점으로 꼽혔던 차원의 저주, 그리고 속도, 용량 면에서도 더 높은 개선을 보인다. 그리고 대표적으로 2가지의 알고리즘을 사용한다.

 

 

1.  HNSW(Hierarchical Navigable Small World)

 

벡터간의 연결을 그래프화하고, 위에서부터 아래로 내려오면서 근접 탐색을 시행한다. 이때 계층은 high-levl 노드는 연결이 많으며 멀리 떨어진 노드와도 빈번하게 연결되는 노드가 선택되어 전역적 탐색을 시행하고, low-level 노드들은 가까운 노드들만 연결되어 지역적 탐색을 시행한다.  

 

즉 전역적으로는 BFS 기반의 탐색을 하다가, 알맞은 노드가 보이면 해당 노드부터 시작해서 계층적으로 내려간다. 계층적으로 내려갈 때는 Greedy DFS 로 score 값이 높은 곳만 탐색하여 가다가 더 가까운 후보군이 없으면 종료한다. ef_search ( exploration factor_search ) 를 기반 마지막 선정되는 k의 탐색범위를 설정할 수 있다.  

 

일반적으로 kNN의 복잡도는 O(n x d)로 표현된다. 즉  모든 벡터에 대한 거리 계산을 해야한다. 하지만 HNSW는 high-level 노드를 이미 선택하여 진행되므로 평균적으로 O(log(n)) 정도로 귀결된다.

 

 

HNSW 논문 : https://arxiv.org/abs/1603.09320

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

 

 

 

 

 

 

 

2. IVF + PQ (Inverted File Index + Product Quantization)

 

IVF = 전체 벡터 공간을 대략적으로 K개의 클러스터로 나뉘어짐 (K-means 사용)

-> 해당 중심점들이 coarse centroid로 명명

-> K-means를 사용했기 때문에 대략적인 글의 카테고리 등 ( 실제로는 latent pattern )  나눠졌을 것으로 판단

-> 해당 카테고리 기반으로 질문에 알맞는 카테고리(클러스터)만 검색 ( nprobe 만큼 ) 

 

 

 

특정 클러스터로 검색량이 줄긴 헀지만 IVF만 썼을 때 여전히 float 32의 full precision vector이기 때문에 2KB 차지하여 용량이 점점 커진다. ( ex 천만개의 벡터면 20GB ) 따라서 용량을 줄이는 양자화가 필요하다. 그래서 사용하는 것이 PQ이다.

 

 

 

PQ =  고차원 벡터를 여러 개의 하위 벡터로 쪼개고, 각 부분을 대표 코드북(codebook)으로 압축. 1개의 벡터가 2KB(2,048 byte) 에서 16byte까지  128배 작아짐.

 

양자화는 결국 '목차' 혹은 '대표' 정도로 생각하면 직관적일 것 같다. k-means와도 유사한데 예를들어 512차원의 float 32 벡터를 16개의 벡터로 나눠 subvector로 나눠진다. 그 후 해당 벡터들에서 대표자(centroids)를 뽑는다. sub-vector의 centroids는 각각 1byte로 표현된다.

 

다만 정확도 이슈가 있을 수 있으므로 m(분할수, 많이 나누면 정밀 ), nbits(코드북크기, 오를 수록 정밀) 등을 사용하여 적절한 파라미터를 찾는다. 또한 Residual PQ(잔차 벡터 양자화), Optimized PQ(PCA 적용) 등을 사용하여 정밀도를 올리기도 한다.

 

 

즉, 둘을 같이 사용하는 것은 IVF로 클러스터들을 나누고 ( centorids 는 최소한의 정확도를 위해 유지한다 ) 

해당 클러스터들 내의 벡터들 경량화를 위해 PQ는 sub-vector로 나누고 압축(quantize)하는것이다. 

 

 

 

 

아래는 위의 aNN과 정규 kNN의 평균적인 검색속도와 정확도 등을 표로 정리하였다. 논문이나 휴리스틱한 기준이며, 데이터셋이나 환경 등에 의해서 많이 차이날 수도 있을 것 같다.

알고리즘	평균 검색 속도 (ms/query)	정확도 (Recall@10)	요약
정확한 KNN (Brute-force)	>800~1000ms	100%	모든 벡터 거리 계산
HNSW (ef=64)	5~20ms	95~99%	정확도 매우 높음, 실시간 탐색 가능
IVF + PQ	5~10ms	90~97%	빠르고 메모리 효율적, 압축

 

 

 

 

 

 

참고 : https://www.elastic.co/kr/blog/ann-vs-knn

aNN vs kNN: Understand their differences and roles in vector search