Annoy (Approximate Nearest Neighbors Oh Yeah) est une bibliothèque C++ open source avec des liaisons Python pour la recherche approximative des plus proches voisins. Elle a été créée par Erik Bernhardsson alors qu'il travaillait chez Spotify pour alimenter les recommandations musicales, où elle trouve des morceaux ou des artistes similaires en fonction de vecteurs d'embedding. Annoy est conçue pour des ensembles de données à grande échelle et en lecture seule, et est connue pour sa simplicité, sa rapidité et son efficacité mémoire, ce qui en fait un choix populaire pour les applications de apprentissage automatique nécessitant une recherche de similarité rapide.
La bibliothèque construit une forêt d'arbres de projection aléatoire, où chaque arbre partitionne l'espace de données à l'aide d'hyperplans. Au moment de la requête, Annoy traverse plusieurs arbres pour collecter des points candidats, puis les évalue pour renvoyer les plus proches voisins approximatifs. Cette approche échange une petite quantité de précision contre des gains significatifs en vitesse et en évolutivité, en particulier pour les vecteurs à haute dimension. Annoy prend en charge plusieurs métriques de distance, notamment la distance euclidienne, la distance de Manhattan, la similarité cosinus et le produit scalaire, et peut être utilisée depuis C++, Python et d'autres langages via des liaisons.
Historique et développement
Annoy a été publiée pour la première fois en 2013 par Erik Bernhardsson, qui était alors ingénieur chez Spotify. Le projet est né du besoin de gérer des millions de pistes audio et de fournir des recommandations en temps réel. Bernhardsson a open-sourcé la bibliothèque en 2014, et elle a rapidement gagné en popularité dans la communauté de l'intelligence artificielle. Le nom « Annoy » est un acronyme ludique pour « Approximate Nearest Neighbors Oh Yeah ». La bibliothèque a été maintenue par Bernhardsson et d'autres contributeurs, avec sa dernière version stable étant 1.17.3 en 2023. Elle est hébergée sur GitHub et est disponible sous la licence Apache 2.0.
Approche technique
L'algorithme principal d'Annoy est basé sur des arbres de projection aléatoire. Pendant la phase de construction, la bibliothèque crée plusieurs arbres en divisant récursivement les données à la médiane le long d'un hyperplan choisi aléatoirement. Chaque division est déterminée par deux points sélectionnés aléatoirement dans le sous-ensemble actuel, et l'hyperplan est la médiatrice du segment de ligne les reliant. Ce processus se poursuit jusqu'à ce que chaque feuille contienne au plus un nombre spécifié de points (10 par défaut). La forêt d'arbres résultante est stockée sur disque, permettant un chargement par mappage mémoire, ce qui permet à plusieurs processus de partager le même index sans dupliquer la mémoire.
Au moment de la requête, Annoy traverse chaque arbre de la racine à une feuille, collectant les points dans la feuille comme candidats. Elle calcule ensuite les distances exactes entre le point de requête et tous les candidats, puis renvoie les k plus proches voisins. Le nombre d'arbres à rechercher est un paramètre qui contrôle le compromis entre vitesse et précision : plus d'arbres donnent un meilleur rappel mais des requêtes plus lentes. Annoy prend également en charge un paramètre « search_k » qui limite le nombre de nœuds visités, offrant un contrôle plus fin sur les performances.
Utilisation et intégration
Annoy est largement utilisée dans les systèmes de production, en particulier dans les moteurs de recommandation et la recherche d'informations. Chez Spotify, elle a été utilisée pour alimenter la fonctionnalité de playlist « Discover Weekly », qui recommande de nouvelles musiques en fonction de l'historique d'écoute des utilisateurs. La bibliothèque est également employée dans divers pipelines de apprentissage profond pour des tâches telles que la recherche d'images, la similarité de documents et la recherche d'embeddings de réseaux de neurones. Sa simplicité et son absence de dépendances externes la rendent facile à intégrer dans des projets existants. Annoy fournit une API simple : vous construisez un index en ajoutant des éléments, puis appelez build(n_trees), et pour les requêtes, vous utilisez get_nns_by_vector ou get_nns_by_item. La bibliothèque prend également en charge l'ajout incrémental d'éléments, bien que l'index doive être reconstruit pour incorporer de nouvelles données.
Comparaison avec d'autres bibliothèques
Annoy est l'une des nombreuses bibliothèques de recherche approximative des plus proches voisins, chacune avec des forces différentes. Comparée à des bibliothèques comme FAISS (de Facebook AI Research) et HNSW (graphes hiérarchiques navigables à petits mondes), Annoy est souvent plus simple à utiliser et ne nécessite pas de phase d'entraînement. Cependant, elle peut avoir un rappel plus faible pour une vitesse donnée par rapport à HNSW, qui utilise une approche basée sur des graphes. FAISS offre une accélération GPU et des structures d'indexation plus avancées, mais elle est plus lourde et plus complexe. Les fichiers mappés en mémoire d'Annoy la rendent particulièrement adaptée aux grands ensembles de données qui dépassent la RAM, car elle peut charger l'index à la demande. Cette fonctionnalité est moins courante dans d'autres bibliothèques, ce qui fait d'Annoy un choix privilégié pour les déploiements à grande échelle en lecture seule.
Impact et héritage
Annoy a eu un impact significatif sur le domaine de la recherche de similarité et a été citée dans de nombreux articles de recherche. Elle a inspiré d'autres projets et a été utilisée comme référence dans des études de benchmarking. La conception de la bibliothèque a influencé les développements ultérieurs dans le IA générative et les applications de grands modèles de langage, où la récupération efficace de vecteurs pertinents est cruciale pour des tâches comme la recherche sémantique et l'augmentation de mémoire. Annoy reste un outil pertinent dans l'écosystème de l'intelligence artificielle, et son code source est une ressource précieuse pour apprendre les algorithmes de recherche approximative des plus proches voisins.