seungjun.dev

벡터 검색 및 인덱싱

벡터DB에서 검색하고 인덱싱하는 방법들

#ANN #k-NN #데이터베이스 #벡터 #인덱싱

실제 서비스에서는 UX가 정말 중요하기 때문에, 약간의 정확도를 희생하더라도 사용자가 스트레스를 느끼지 않을 만큼의 빠른 속도를 보장해야 한다.

'유사도'를 어떻게 계산하는지 알았다면, 이제 '어떻게 빠르게 찾을 것인가'에 대한 답을 찾을 차례다.

k-NN(k-최근접 이웃) 쿼리 검색

  • 데이터베이스에 던질 질문의 형식
  • "k-NN 쿼리를 수행한다" == "내가 지금 준 이 벡터와 가장 유사한 이웃(데이터)을 k개 찾아줘"
  • 정확도가 100% 보장됨
  • 데이터 양이 많아지면 매우 느려지고 계산 비용이 기하급수적으로 증가

예시

  • 사용자가 "육즙이 풍부한 햄버거"라고 검색했다고 가정해본다.

  1. 사용자의 검색어도 벡터로 변환

    "육즙이 풍부한 햄버거" -> queryVector = [0.3, 0.5, 0.9]

  2. queryVector 와 k = 1 (가장 비슷한 맛집 1개)이라는 정보를 가지고 내부적으로 k-NN 쿼리를 수행하는 함수를 호출

k-NN 쿼리를 수행하는 함수도 내부적으로 아래 과정을 거친다.

  1. 모든 벡터와 '유사도' 계산

    DB에 저장된 모든 벡터들을 하나씩 꺼내서, 사용자의 검색어 벡터(queryVector)와 얼마나 비슷한지 코사인 유사도를 전부 계산한다.

    • queryVector vs. steak_burger -> 코사인 유사도 계산 -> 결과: 0.92
    • queryVector vs. brazil_tteokbokki -> 코사인 유사도 계산 -> 결과: -0.15
    • 만약 데이터가 100개라면 이 계산을 100번 반복한다.

  2. 계산 결과를 임시로 저장 계산한 유사도 점수를 각 데이터의 ID와 함께 임시로 저장한다.

  3. '유사도 점수' 기준으로 정렬 위에서 만든 임시 배열을 유사도 점수가 높은 순서대로 정렬한다. 점수가 높을수록 더 유사하다.

  4. 가장 높은 k개 선택해서 반환 위에서 정렬한 배열에서 가장 위에서부터 k 개 만큼 잘라내 반환한다.

export const cosineSimilarity = (vecA, vecB) => {
  // 두 벡터의 차원이 다르면 계산 불가
  if (vecA.length !== vecB.length) {
    throw new Error("Vectors must have the same dimension.");
  }

  let dotProduct = 0; // 내적
  let normA = 0; // 벡터 A의 크기
  let normB = 0; // 벡터 B의 크기

  for (let i = 0; i < vecA.length; i++) {
    dotProduct += vecA[i] * vecB[i];
    normA += vecA[i] ** 2;
    normB += vecB[i] ** 2;
  }

  if (normA === 0 || normB === 0) {
    // 벡터 중 하나라도 영벡터인 경우 유사도는 정의되지 않음
    return 0;
  }

  return dotProduct / (Math.sqrt(normA) * Math.sqrt(normB));
};
knnSearch(queryVector, k = 5) {
    const similarityScores = [];

    // 1. DB에 저장된 모든 벡터와 쿼리 벡터의 유사도 계산
    for (const [id, vector] of this.vectors.entries()) {
      const similarity = cosineSimilarity(queryVector, vector);
      similarityScores.push({ id, similarity });
    }

    // 2. 계산된 유사도 점수를 높은 순으로 정렬
    similarityScores.sort((a, b) => b.similarity - a.similarity);

    // 3. 상위 k개의 결과를 반환
    return similarityScores.slice(0, k);
}

인덱싱의 필요성

  • 가장 단순하게는 저장된 모든 벡터와 일일이 유사도를 계산(브루트포스)해볼 수 있다.
  • 하지만 데이터가 1억개로 넘어간다면 검색 한 번을 위해 1억 번의 복잡한 벡터 계산을 해야 한다.
  • 인덱싱은 데이터를 미리 특정 구조로 잘 정리해서 검색 대상을 획기적으로 줄여준다.
    • 책 전체를 다 읽어서 찾는 게 아니라, 책 앞의 '목차'를 보고 필요한 부분만 펼쳐보는 것과 같다.

주요 ANN 인덱싱 기법

전문적인 벡터 DB들은 100%의 정확도를 약간 포기하는 대신, 속도를 비약적으로 높이는 ANN(근사 최근접 이웃) 알고리즘을 사용하며, 이를 위해 다음과 같은 인덱싱 기법들을 활용한다.

  • 그래프 기반 (HNSW - Hierarchical Navigable Small World): 가장 널리 쓰이고 성능이 좋은 방식 중 하나

    • 모든 벡터를 노드로 생각하고, 가까운 벡터들끼리 선으로 연결해 '고속도로망' 같은 다층의 그래프를 만들어 둠
    • 검색 시에는 출발점에서 가장 가까운 노드로 이동하고, 또 거기서 가장 가까운 노드로 이동하는 식으로 고속도로를 타듯 목표 지점까지 빠르게 찾아감
    • 모든 데이터를 다 둘러볼 필요가 없음

  • 해싱 기반 (LSH - Locality-Sensitive Hashing):

    • 해시 함수를 사용해서, 비슷한 벡터들은 높은 확률로 같은 버킷에 담기도록 분류
    • 검색어 벡터가 들어오면, 그 벡터가 속한 버킷과 그 주변 버킷에 있는 데이터들만 비교하면 되므로 검색 범위가 엄청나게 줄어듦

LSH 기법

서로 가까운 벡터들은 높은 확률로 같은 해시 값을 가질 것

  • "비슷한 놈들은 비슷한 곳에 모아두자"라는 아주 간단한 아이디어에서 출발한다.

  • 비유: 학생(벡터)들을 기숙사 방(버킷)에 배정하는 '마법의 모자'가 있다고 가정

  • 동작 원리:

    1. 마법의 모자는 여러 개의 **질문(Plane)**을 준비한다. 예를 들면, "키가 170cm 이상인가?", "몸무게가 60kg 이상인가?" 같은 질문들이다.
    2. 새로운 학생(쿼리 벡터)가 오면, 이 질문들에 답하게 한다. (예/아니오)
    3. 그 답들의 조합 (예, 아니오, 아니오, ...)이 바로 그 학생이 들어갈 **기숙사 방 번호(해시값)**가 된다.
    4. 키, 몸무게 등이 비슷한 학생들은 질문에 대한 답도 비슷할 것이고, 결국 같은 방에 배정될 확률이 매우 높을 것이다.

  • 검색 과정:

    1. 사용자가 찾고 싶은 벡터(새로운 학생, 쿼리 벡터)가 오면, 마법의 모자에게 보내 방 번호를 받는다.
    2. 그리고 도서관 전체를 뒤지는 대신, 그 방 안에 있는 학생들 하고만 서로 비교해서 가장 비슷한 학생을 찾는다.
    3. 100만 명 전체가 아닌, 한 방에 있는 100명하고만 비교하면 되니 속도가 엄청 빨라지는 것이다.