Distributed computation of Approximate Nearest Neighbors

Calcul distribué des voisins les plus proches approximatifs

Ce projet fait référence à mon travail de thèse de maîtrise "Le calcul distribué des voisins les plus proches" pour ma maîtrise en informatique en collaboration externe avec la Wikimedia Foundation. Le travail se concentre sur la rendez-vous plus efficace sur le service de téléchargement d'images sur Wikipedia, en étudiant comment distribuer le calcul des voisins les plus proches approximatifs, en développant des solutions ad hoc, en explorant les possibilités existantes et en les adaptant pour effectuer des recherches distribuées d'images similaires dans l'ensemble de données Wikimedia.

Quel est ce référentiel

Ce référentiel est destiné à contenir des implémentations de plusieurs bibliothèques pour effectuer des recherches de similitude (cosinus) afin de trouver le meilleur à mon objectif. Les différentes implémentations sont basées sur le cas d'utilisation précédemment exposé.

Voisins les plus proches

• KNN: Cette bibliothèque n'est pas approximée et est très inefficace pour mon cas d'utilisation de la recherche, sa mise en œuvre, avec Sklearn, n'a été fournie qu'à des fins de comparaison avec des bibliothèques approximées. À l'intérieur de KNN, vous trouverez également une version brute-force qui exécute une comparaison linéaire entre un seul vecteur et l'ensemble de données, sans créer de structure de données.
• ENAGE: Cette bibliothèque implémente une version d'Ann, écrite par Erik Bernhardsson au nom de Spotify.
• FAISS: Cette bibliothèque a été créée pour des recherches de similitudes efficaces et un regroupement de vecteurs denses par l'équipe de recherche Facebook (maintenant Meta).
• SPTAG: Cette bibliothèque est conçue pour la recherche Vector Vector à grande échelle approximative, créée par Microsoft en tant que version alternative à leur bibliothèque précédente, appelée Diskann. Contrairement à d'autres technologies, cette solution implique l'utilisation de la mémoire de RAM et du disque physique, gérant efficacement lequel et la quantité d'informations économisent sur eux.

Distribution des voisins les plus proches

• Distributed-Faiss: cette bibliothèque a déjà été couverte, mais pas sa version distribuée. Cet algorithme, bien que très efficace, n'ajoute pas beaucoup de nouvelles aux propositions précédemment analysées qui s'exécutent sur une seule machine. Ce qui rend cette bibliothèque spéciale, cependant, c'est qu'elle peut être distribuée sur plusieurs machines de manière très simple.
• Distributed-Sptag: cette bibliothèque a déjà été couverte, mais pas sa version distribuée. Cet algorithme, bien que très efficace, n'ajoute pas beaucoup de nouvelles aux propositions précédemment analysées qui s'exécutent sur une seule machine. Ce qui rend cette bibliothèque spéciale, cependant, c'est qu'elle peut être distribuée sur plusieurs machines de manière très simple.
• Milvus: Cette bibliothèque implémente la base de données vectorielle qui se concentre sur la fourniture d'un système et d'une architecture efficaces pour les recherches de similitude et les applications alimentées par AI. Le besoin que Milvus essaie de satisfaire est de fournir un système complet capable de fonctionner sur d'énormes ensembles de données dynamiques, fournissant des solutions qui peuvent également fonctionner sur des GPU de manière distribuée. Pour ce faire, Milvus a été construit sur des bibliothèques qui ont déjà été expliquées comme Faish, apportant les modifications nécessaires pour son cas d'utilisation.

Comment il est structuré

Le projet a été structuré de manière précise pour assurer une organisation facile des fichiers et pour que la navigation soit simple.

• Algorithmes: à l'intérieur de ce dossier, vous pouvez trouver toutes les implémentations
  • For-out-bibliothèque:
    • config.py: ce fichier contient les configurations nécessaires pour le bon fonctionnement des bibliothèques
    • init.py: ce fichier contient le code pour la lecture des ensembles de données, la formation des structures de données et la création de l'index
    • search.py: ce fichier contient le code pour effectuer des recherches et renvoyer les éléments résultants
      • Autres fichiers: chronomètre.py, mocks.py
• Ensembles de données: les ensembles de données et les structures de données enregistrées en mémoire seront insérées dans ce dossier
  • Compressé: dans ce dossier, il est possible d'insérer les ensembles de données compressés, comme on peut le voir à partir de l'exemple inséré. Vous pouvez également remarquer un fichier appelé links.txt contenant tous les ensembles de données wikimedia
  • Décompressée: Dans ce dossier, il est possible d'insérer les ensembles de données décompressés, à partir d'ici, ils seront filtrés et décomposés pour un bon fonctionnement des bibliothèques
  • Images: À l'intérieur de ce dossier, il est possible de trouver les images correspondant aux vecteurs extraits de l'ensemble de données
  • Vecteurs: Dans ce dossier, il est possible de trouver les vecteurs correspondant aux images extraites de l'ensemble de données
  • FormatDatasets.Bash: Ce fichier, exécutable suivant ce Readme.md, contient le code pour décomposer tous les ensembles de données du dossier décompressé en déplaçant les vecteurs à l'intérieur du dossier / dossier et des images correspondantes à l'intérieur du dossier / dossier. Ce fichier utilise FormatDatasets.py pour convertir le fichier .csv en format binaire pour accélérer tout le projet.
• Docs: documents obtenus lors de la rédaction de la thèse

Comment exécuter

Télécharger quelques ensembles de données

1. Allez dans un dossier compressé et exécutez wget -i links.txt pour télécharger l'ensemble de données Wikimedia (images, vecteurs)
2. Décompressez les archives en décompressée, dans Wikimedia Dataset Case gunzip *.gz
3. Allez dans le dossier des ensembles de données et suivez le Readme.md

Importer / installer / compiler les bibliothèques

Entrez d'abord dans le dossier des algorithmes et installez les exigences générales avec pip install -r requirements.txt .

• KNN: pip install scikit-learn ou n'installez rien si vous préférez utiliser la version brute-force
• Ennaginaire: pip install annoy
• FAISS: Suivez le tutoriel Conda
• SPTAG: Vous pouvez compiler cette bibliothèque via le code source ou utiliser Docker. Je recommande personnellement cette dernière solution, en exécutant ces commandes:

   set GIT_LFS_SKIP_SMUDGE=1 
  git clone --recurse-submodules https://github.com/microsoft/SPTAG
  cd SPTAG
  docker build -t sptag .

• Distributed-Faisiss: clone le référentiel (si vous souhaitez utiliser mon PR pour ajouter de la précision à la phase de recherche avec set_index_parameter ou set_index_parameters méthodes clone ce référentiel), entrez dans le dossier, puis exécutez pip install -e .
• SPTAG DISTRIBUTED: Suivez les instructions pour SPTAG
• Milvus: pip install pymilvus , puis Milvus peut être installé avec Docker Compose ou Kubernetes (Milvus autonome pour les tests) ou avec Helm + Kubernetes (grappe Milvus pour la production)

Exécuter les bibliothèques Ann

Avant d'exécuter les bibliothèques personnaliser les différents fichiers config.py

1. python init.py
2. python search.py

Exécuter les bibliothèques distribuées-Ann

Avant d'exécuter les bibliothèques personnaliser les différents fichiers config.py

• Distributed-Faiss:
  1. Personnalisez le fichier Discovery_Config.txt.
  2. Exécuter sur chaque serveur python init_server.py
  3. Exécuter sur le client python init_client.py
  4. Exécuter sur le client python search.py
• Sptag distribué:
  1. Accédez à chaque serveur, personnalisez le fichier config.py (attention à start_metadata_offset) et exécutez python init.py
  2. Accédez aux serveurs hébergeant l'index précédemment créé. Dans le dossier de version de la bibliothèque, importez et personnalisez le fichier Service.ini et exécutez la commande ./server -m socket -c service.ini
  3. Accédez à la machine que vous identifiez comme agrégateur. Dans le dossier de version de la bibliothèque, importez et personnalisez le fichier agrégator.ini et exécutez la commande ./aggregator
  4. Accédez au client, personnalisez le fichier config.py et exécutez python search.py
• Milvus:
  1. python init.py
  2. python search.py

---

Fabriqué par Christian Stingone