ANNOY(아노이)

Approximate Nearest Neighbors Oh-Yeah

Introduce to ANNOY

• Spotify에서 개발한 ANN(Approximate Nearest Neighbor) 인덱싱 기법
• Tree-based 공간 분할 기법
• 기존 K-D Tree에 비해 개선된 빌드 및 탐색 속도 보장
• 기존 K-D Tree에 비해 재현율은 확실히 저하

ANNOY Build Algorithm

1. Vector Space에서 임의의 두 점을 선택
2. 두 점 사이의 hyper plane을 생성하여 vector space를 나눔
   • 이때, hyper plane에서는 n차원에 대해서 정의 가능
3. 각 subspace에 있는 점들의 개수를 node로 하여 binary tree를 생성 혹은 갱신
4. Subspace 내 점이 K개를 초과하면 해당 subspace에 대해 1~3을 진행
5. 위 1~4를 정해진 트리의 개수만큼 반복하여 여러개의 트리를 생성

ANNOY Search Algorithm

1. 각 트리에서 최근접 이웃 k개 탐색
2. 최종적으로 종합된 후보군 중에서 다시 k개 탐색(brute-force)

ANNOY hyperparameter

• n_trees: 생성하는 트리의 개수
  • 설정된 수 만큼 트리를 생성하여 여러 후보군을 생성
  • 각 트리는 각자 랜덤하게 hyperplane을 생성하여 공간을 분리
  • 후보군 중에서 다시 top k개 선택
• search_k: Nearest Neighbors를 구할 때 탐색하는 노드의 개수

Refernces

• 오늘 할 일. 2022.11.13. “[annoy] annoy 사용방법: 추천시스템에서 유사 아이템 찾기”. https://abluesnake.tistory.com/148.