11. Approximate Nearest Neighbor(ANN)

Nearest Neighbor(NN)

- vector space model에서 내가 원하는 query vector와 가장 유사한 vector를 찾는 알고리즘

- accurate와 response time의 tradeoff관계를 고려해야한다. 빠른 서비스 제공이 중요할 수도!

 

ANNOY : spotify가 개발한 tree-based ANN기법

- 주어진 벡터들을 여러 개의 subset으로 나누고 tree형태의 자료 구조로 구성 후 탐색 진행.

tree로 구성할 경우 원하는 query를 O(N) 시간복잡도로 탐색 가능하다.

 

query에 해당하는 영역에 존재하는 vector들을 추천.

 

문제점 : 가장 근접한 점이 다른 tree(영역)에 있을 경우 추천하지 않음.

해결방법 :

    1. query에 해당하는 영역과 닿아있는 인근 지역까지 탐색범위로 추가 (but response time 증가)

    2. binary tree를 여러 개 생성하여 ensemble 진행(정확도 향상 but response time 증가)

 

특징

- 다른 ANN 기법에 비해 간단하고 가벼움(GPU연산은 x)

- search해야할 이웃의 개수를 알고리즘이 보장하고, 파라미터 조정을 통해 trade off관계의 변수(정확도, 응답시간) 조절 가능

- 단 새로운 데이터가 추가될 경우 binary tree를 다시 구축해야함.

 

 

다른 ANN

- Hierarchical Navigable Small World Graphs(HNSW)

- Inverted File Index(IVF) : query vector에 대한 cluster를 찾고 해당 군집 내에서 search

- Product Quantization - Compression(subset이 아닌 모든 데이터를 압축하여 탐색 시간을 줄임)