[Algorithm] ANN: ANNoy 알고리즘
도입: 한 벡터(Query)에 대한 가장 유사한 벡터를 고를 때, 벡터 검색이 필요하다. 대표적으로 추천 알고리즘, RAG, 벡터 DB 등이 있다. 이 때, 모든 벡터와의 거리를 비교해가며 전역 탐색을 해나가는 것이 옳을까? 벡터 차원이 100이라고 할 때, 100개의 벡터 포인트가 기존에 있다면 10000번의 연산이지만, 1만 개라면, 혹은 그 이상인 100만 개라면 엄청난 연산량이 필요하게 된다.즉, 적어도 벡터 차원 d * 벡터 포인트의 갯수 N이면 d * N인 것이다.만약 가장 근접한 벡터 k개를 찾는 k-NN이라면, 그 중에 또 상위 k개를 더 뽑아야 한다. 즉, 막대한 연산량이 필요하고, 이는 시간 문제와 직결된다.ANNoy:이를 해결하기 위하여 ANN이 소개되었다.ANN(Approximate..
