벡터 인덱싱과 탐색

만약 벡터 DB에 수천만개의 벡터가 있다면 각각의 벡터간 유사도 비교를 빠르게 하기 위해선 벡터를 적절한 자료구조화하는 벡터 인덱싱이 필요합니다.

KNN(K-Nearest Neighbors)

쿼리 벡터 q 에 대해 전체 벡터 중 가장 유사한(가까운) k 개를 찾는 알고리즘

인덱싱 없이 KNN만 진행하면 사실상 Brute-force KNN이 됩니다. 따라서 아래의 인덱스를 이용한 KNN, ANN을 주로 이용합니다.

ANN(Approximate KNN)

정확도를 조금 희생하더라도 속도를 높이기 위한 방법입니다. 수백만, 수십억개의 데이터를 다룰때는 완벽히 일치하는 결과 대신 충분히 가까운 근사치를 찾는 것이 더 효율적입니다.

HNSW(Hierarchical Navigable Small World)

• 대부분의 벡터 DB에서 기본 알고리즘으로 사용.
• 벡터를 그래프 구조로 저장하는 기법입니다.
• 각 벡터는 그래프의 노드가 되고, 노드마다 근접한 이웃 벡터들과 간선이 연결됩니다.
• 간선 개수는 보통 16개 이내로 제한합니다.
• 각 노드들은 랜덤하게 여러 레벨에 할당됩니다.
• 높은 레벨일 수록 적은 수의 노드가 할당되고, 최하 레벨인 레벨 0에는 전체 노드가 있습니다.
• 검색은 다음의 과정을 거쳐 이뤄집니다.
  • 사용자가 벡터 q를 쿼리
  • 가장 높은 레벨에서 시작해 현재 노드 v에서 연결된 이웃 중 q에 더 가까운 노드가 있다면 이동.
  • 더 이상 가까운 이웃이 없으면 한 단계 아래 레벨로 내려감.
  • 이 과정을 레벨 0까지 반복
  • 마지막엔 레벨 0에서 근접 벡터들을 모아 정렬 후 상위 N개 반환

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

• 인덱싱(IVF) + 압축(PQ)조합입니다.
• 정확도는 떨어지지만, 메모리 절약하면서도 빠르게 검색 가능한 특징이 있습니다.