임베딩 공간을 여러개로 쪼갠 후, Query Vector가 포함되는 공간 내에 존재하는 벡터만 유사도를 계산하자.

• spotify에서 개발

• Tree — based ANN기법

  Query Vector가 포함된 공간에 빠르게 접근하기 위해 Tree 구조를 활용한다.

  1. 무작위로 두 점을 선택한 뒤, 두 점의 사이의 hyperplane로 Vector Space를 나눈다.
  2. Subspace에 있는 점들의 개수를 node로 하여 binary tree 생성 혹은 갱신
  3. 모든 Subspace 내에 점이 K개 이하로 존재할 때까지 위의 과정 반복

문제점

가장 근접한 점이 tree의 다른 node에 있는 경우 해당 점은 후보 subset에 포함되지 못한다.

해결 방안

1. priority queue를 사용하여 가까운 다른 node를 탐색
2. binary tree를 여러 개 생성하여 병렬적으로 탐색

Annoy parameter

1. number_of_trees: 생성하는 binary tree의 개수
2. search_k: NN을 구할 때 탐색하는 node의 개수

두 값을 조정하여 Accuracy vs Speed trade-off 조정이 가능하다.

특징

• Search Index를 생성하는 것이 다른 ANN 기법에 비해 간단하다.
• 아이템 개수가 많지 않고 벡터의 차원(d < 100)이 낮은 경우 사용하기에 적합하다.
• GPU 연산은 지원하지 않는다.
• Search 해야 할 이웃의 개수를 알고리즘이 보장한다.
• 기존 생성된 binary tree에 새로운 데이터를 추가할 수 없다.