Annoy(Approximate Nearest Neighbors Oh Yeah)는 근사 최근접 이웃 검색을 위한 Python 바인딩을 갖춘 오픈소스 C++ 라이브러리이다. Spotify에서 근무하던 Erik Bernhardsson이 음악 추천을 지원하기 위해 만들었으며, 임베딩 벡터를 기반으로 유사한 트랙이나 아티스트를 찾는 데 사용된다. Annoy는 대규모 읽기 전용 데이터셋을 위해 설계되었으며, 단순성, 속도, 메모리 효율성으로 잘 알려져 있어 빠른 유사도 검색이 필요한 머신러닝 애플리케이션에서 인기 있는 선택지이다.
이 라이브러리는 무작위 투영 트리(random projection tree)의 포리스트를 구축하며, 각 트리는 초평면을 사용하여 데이터 공간을 분할한다. 쿼리 시점에 Annoy는 여러 트리를 탐색하여 후보 점을 수집한 다음 점수를 매겨 근사 최근접 이웃을 반환한다. 이 접근 방식은 특히 고차원 벡터에서 약간의 정확도를 희생하는 대신 속도와 확장성에서 상당한 이점을 얻는다. Annoy는 유클리드 거리, 맨해튼 거리, 코사인 유사도, 내적을 포함한 여러 거리 측정 기준을 지원하며, C++, Python 및 바인딩을 통한 다른 언어에서 사용할 수 있다.
History and Development
Annoy는 2013년 당시 Spotify의 엔지니어였던 Erik Bernhardsson에 의해 처음 출시되었다. 이 프로젝트는 수백만 개의 오디오 트랙을 처리하고 실시간 추천을 제공해야 하는 필요성에서 시작되었다. Bernhardsson은 2014년에 이 라이브러리를 오픈소스로 공개했으며, 인공지능 커뮤니티에서 빠르게 주목을 받았다. "Annoy"라는 이름은 "Approximate Nearest Neighbors Oh Yeah"의 장난스러운 약어이다. 이 라이브러리는 Bernhardsson과 다른 기여자들에 의해 유지 관리되었으며, 최신 안정 버전은 2023년의 1.17.3이다. GitHub에 호스팅되어 있으며 Apache 2.0 라이선스로 제공된다.
Technical Approach
Annoy의 핵심 알고리즘은 무작위 투영 트리를 기반으로 한다. 구축 단계에서 라이브러리는 무작위로 선택된 초평면을 따라 데이터를 중앙값에서 재귀적으로 분할하여 여러 트리를 생성한다. 각 분할은 현재 하위 집합에서 무작위로 선택된 두 점에 의해 결정되며, 초평면은 두 점을 연결하는 선분의 수직 이등분선이다. 이 과정은 각 리프가 최대 지정된 수의 점(기본값 10)을 포함할 때까지 계속된다. 결과로 생성된 트리 포리스트는 디스크에 저장되어 메모리 매핑 로딩을 가능하게 하며, 이를 통해 여러 프로세스가 메모리를 중복하지 않고 동일한 인덱스를 공유할 수 있다.
쿼리 시점에 Annoy는 각 트리를 루트에서 리프까지 탐색하여 리프의 점을 후보로 수집한다. 그런 다음 쿼리 점에서 모든 후보까지의 정확한 거리를 계산하고 상위 k개의 최근접 이웃을 반환한다. 검색할 트리 수는 속도와 정확도 사이의 균형을 제어하는 매개변수로, 더 많은 트리는 더 나은 재현율을 제공하지만 쿼리가 느려진다. Annoy는 또한 방문하는 노드 수를 제한하는 "search_k" 매개변수를 지원하여 성능을 더 세밀하게 제어할 수 있다.
Usage and Integration
Annoy는 프로덕션 시스템, 특히 추천 엔진과 정보 검색에서 널리 사용된다. Spotify에서는 사용자 청취 기록을 기반으로 새 음악을 추천하는 "Discover Weekly" 플레이리스트 기능을 지원하는 데 사용되었다. 이 라이브러리는 또한 이미지 검색, 문서 유사도, 신경망 임베딩 검색과 같은 작업을 위한 다양한 딥러닝 파이프라인에서도 사용된다. 단순성과 외부 종속성 부재로 인해 기존 프로젝트에 쉽게 통합할 수 있다. Annoy는 간단한 API를 제공한다. 항목을 추가하여 인덱스를 구축한 다음 build(n_trees)를 호출하고, 쿼리에는 get_nns_by_vector 또는 get_nns_by_item을 사용한다. 라이브러리는 항목의 증분 추가도 지원하지만, 새 데이터를 통합하려면 인덱스를 다시 구축해야 한다.
Comparison with Other Libraries
Annoy는 각각 다른 강점을 가진 여러 근사 최근접 이웃 라이브러리 중 하나이다. FAISS(Facebook AI Research) 및 HNSW(계층적 Navigable Small World 그래프)와 같은 라이브러리와 비교할 때, Annoy는 종종 사용하기 더 간단하고 훈련 단계가 필요 없다. 그러나 그래프 기반 접근 방식을 사용하는 HNSW에 비해 주어진 속도에서 재현율이 낮을 수 있다. FAISS는 GPU 가속과 더 고급 인덱싱 구조를 제공하지만 더 무겁고 복잡하다. Annoy의 메모리 매핑 파일은 RAM을 초과하는 대규모 데이터셋에 특히 적합하며, 필요 시 인덱스를 로드할 수 있다. 이 기능은 다른 라이브러리에서는 덜 일반적이므로, Annoy는 읽기 전용 대규모 배포에서 선호되는 선택지이다.
Impact and Legacy
Annoy는 유사도 검색 분야에 상당한 영향을 미쳤으며 수많은 연구 논문에서 인용되었다. 다른 프로젝트에 영감을 주었고 벤치마킹 연구에서 기준선으로 사용되었다. 이 라이브러리의 설계는 생성형 AI 및 대규모 언어 모델 애플리케이션의 후속 개발에 영향을 주었으며, 여기서 관련 벡터의 효율적인 검색은 의미 검색 및 메모리 증강과 같은 작업에 중요하다. Annoy는 인공지능 생태계에서 여전히 관련성 있는 도구로 남아 있으며, 그 코드베이스는 근사 최근접 이웃 알고리즘을 배우기 위한 귀중한 자원이다.