Distributed computation of Approximate Nearest Neighbors

Verteilte Berechnung von ungefähr nächsten Nachbarn

Dieses Projekt bezieht sich auf meine Masterarbeit "Verteilte Berechnung der ungefähren Nachbarn" für meinen Master -Abschluss in Informatik in externer Zusammenarbeit mit der Wikimedia Foundation. Die Arbeit konzentriert sich darauf, den Image -Upload -Service für Wikipedia effizienter zu gestalten, zu untersuchen, wie die Berechnung der ungefähren Nachbarn der nächsten Nachbarn verteilt, Ad -hoc -Lösungen entwickelt, vorhandene Möglichkeiten untersucht und sie an die Durchführung verteilter Suchanfragen ähnlicher Bilder innerhalb des Wikimedia -Datensatzes angepasst werden.

Was ist dieses Repository?

Dieses Repository soll Implementierungen mehrerer Bibliotheken zur Durchführung von Ähnlichkeitssuche (Cosinus) enthalten, um das Beste für meinen Zweck zu finden. Die verschiedenen Implementierungen basieren auf dem zuvor exponierten Anwendungsfall.

Ungefähr nächste Nachbarn

• KNN: Diese Bibliothek ist nicht angenähert und ist für meinen Forschungsnutzungsfall sehr ineffizient, und ihre Implementierung mit Sklearn wurde nur zu Vergleichszwecken mit annähten Bibliotheken bereitgestellt. In KNN finden Sie auch eine Brute-Force-Version, die einen linearen Vergleich zwischen einem einzelnen Vektor und dem gesamten Datensatz ausführt, ohne eine Datenstruktur zu erstellen.
• Ärgern: Diese Bibliothek implementiert eine Version von Ann, die von Erik Bernhardsson im Namen von Spotify geschrieben wurde.
• FAISS: Diese Bibliothek wurde durch das Facebook -Forschungsteam (Now Meta) für effiziente Ähnlichkeitssuche und Clustering dichter Vektoren erstellt.
• SPTAG: Diese Bibliothek ist für die von Microsoft als alternative Version zu ihrer vorherigen Bibliothek namens Diskann erstellte Bibliothek für große Vektor -Vektor -Annäherungen aus der nächsten Nachbarn. Im Gegensatz zu anderen Technologien beinhaltet diese Lösung die Verwendung des RAM -Speichers und der physischen Festplatte, die effizient verwaltet, welche und wie viele Informationen sie sparen.

Verbreitung von ungefähr nächsten Nachbarn

• Distributed-Faiss: Diese Bibliothek wurde bereits abgedeckt, aber nicht ihre verteilte Version. Dieser Algorithmus fügt den zuvor analysierten Vorschlägen, die auf einer einzelnen Maschine ausgeführt wurden, nicht viel neu hinzu. Was diese Bibliothek jedoch zu etwas Besonderem macht, ist, dass sie auf sehr einfache Weise auf mehreren Maschinen verteilt werden kann.
• Distributed-SPTAG: Diese Bibliothek wurde bereits abgedeckt, aber nicht ihre verteilte Version. Dieser Algorithmus fügt den zuvor analysierten Vorschlägen, die auf einer einzelnen Maschine ausgeführt wurden, nicht viel neu hinzu. Was diese Bibliothek jedoch zu etwas Besonderem macht, ist, dass sie auf sehr einfache Weise auf mehreren Maschinen verteilt werden kann.
• MILVUS: Diese Bibliothek implementiert die Vektor-Datenbank, die sich auf die Bereitstellung eines effizienten Systems und einer effizienten Architektur für Ähnlichkeitssuche und AI-betriebene Anwendungen konzentriert. Das Bedürfnis, dass Milvus versucht, ein vollständiges System zu erfüllen, das auf riesigen dynamischen Datensätzen arbeiten kann, und Lösungen bereitstellen, die auch auf GPUs auch verteilt ausgeführt werden können. Um dies zu tun, wurde Milvus auf Bibliotheken aufgebaut, die bereits als FAISS erklärt wurden, wodurch die erforderlichen Änderungen für den Anwendungsfall vorgenommen wurden.

Wie es strukturiert ist

Das Projekt wurde auf genaue Weise strukturiert, um eine einfache Organisation von Dateien zu gewährleisten und die Navigation einfach zu gestalten.

• Algorithmen: In diesem Ordner finden Sie alle Implementierungen
  • For-Each-Bibliothek:
    • config.py: Diese Datei enthält die Konfigurationen, die für den richtigen Betrieb der Bibliotheken erforderlich sind
    • Init.py: Diese Datei enthält den Code zum Lesen von Datensätzen, Schulungsdatenstrukturen und Erstellen des Index
    • Search.py: Diese Datei enthält den Code zum Ausführen von Suchanfragen und zur Rückgabe der resultierenden Elemente
      • Andere Dateien: chronometer.py, motions.py
• Datensätze: Die im Speicher gespeicherten Datensätze und Datenstrukturen werden in diesen Ordner eingefügt
  • Komprimiert: In diesem Ordner können die komprimierten Datensätze eingefügt werden, wie aus dem Beispiel eingeliefert wird. Sie können auch eine Datei namens Links.txt mit allen Wikimedia -Datensätzen bemerken
  • Dekomprimiert: In diesem Ordner können die dekomprimierten Datensätze eingefügt werden. Von hier aus werden sie gefiltert und für eine korrekte Funktion der Bibliotheken zerlegt
  • Bilder: In diesem Ordner ist es möglich, die Bilder zu finden, die den aus dem Datensatz extrahierten Vektoren entsprechen
  • Vektoren: In diesem Ordner ist es möglich, die Vektoren zu finden, die den aus dem Datensatz extrahierten Bilder entsprechen
  • formatDatasets.bash: Diese Datei, die nach diesem ReadMe.md ausführte, enthält den Code, um alle Datensätze aus dem dekomprimierten Ordner zu zerlegen, das die Vektoren in den Vektoren/ den Ordner und die entsprechenden Bilder in den Bildern/ Ordner bewegt. Diese Datei verwendet formatDatasets.py, um die .csv -Datei in ein Binärformat umzuwandeln, um das gesamte Projekt zu beschleunigen.
• Dokumente: Dokumente, die während des Schreibens der These erhalten wurden

Wie man ausführt

Laden Sie einige Datensätze herunter

1. Gehen Sie zum komprimierten Ordner und führen Sie wget -i links.txt aus, um das Wikimedia -Datensatz (Bilder, Vektoren) herunterzuladen, um das Wikimedia -Datensatz herunterzuladen.
2. Dekomprimieren Archive in dekomprimiert, in Wikimedia Dataset Case gunzip *.gz
3. Gehen Sie in den Datasets -Ordner und folgen Sie dem Readme.md

Importieren / Installieren / Kompilieren der Bibliotheken

Gehen Sie zunächst in den Ordner des Algorithmen und installieren Sie die allgemeinen Anforderungen mit pip install -r requirements.txt .

• KNN: pip install scikit-learn oder installieren Sie nichts, wenn Sie es vorziehen, die Brute-Force-Version zu verwenden
• Ärgern: pip install annoy
• FAISS: Folgen Sie dem Conda -Tutorial
• SPTAG: Sie können diese Bibliothek über Quellcode kompilieren oder Docker verwenden. Ich persönlich empfehle die letztere Lösung, indem ich diese Befehle ausführe:

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

• Distributed -Faiss: Klonen Sie das Repository (Wenn Sie meine PR zum Hinzufügen einer Genauigkeit der Suche mit set_index_parameter oder set_index_parameters Methoden klonen möchten, klonen Sie mit set_index_parameter oder set_index_parameters methods klon dieses repository), geben Sie den Ordner ein und führen Sie dann pip install -e .
• Distributed-SPTAG: Befolgen Sie die Anweisung für SPTAG
• Milvus: pip install pymilvus und dann können Milvus mit Docker Compose oder Kubernetes (Milvus Standalone zum Testen) oder mit Helm + Kubernetes (Milvus -Cluster für die Produktion) installiert werden.

Führen Sie die Ann -Bibliotheken aus

Bevor Sie die Bibliotheken ausführen, passen Sie die verschiedenen config.py -Dateien an

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

Führen Sie die verteilten Bibliotheken aus

Bevor Sie die Bibliotheken ausführen, passen Sie die verschiedenen config.py -Dateien an

• Verteilt-faiss:
  1. Passen Sie die Datei Discovery_Config.txt an.
  2. Führen Sie auf jedem Server python init_server.py aus
  3. Führen Sie auf dem Client python init_client.py aus
  4. Führen Sie auf der Client python search.py ​​aus
• Verteilt-SPTAG:
  1. Gehen Sie zu jedem Server, passen Sie die Datei config.py an (Aufmerksamkeit auf start_metadata_offset) und führen Sie python init.py aus
  2. Gehen Sie zu den Servern, die den zuvor erstellten Index hosten. Importieren und passen Sie die Datei von service.ini importieren und passen Sie im Release -Ordner der Bibliothek an und führen Sie den Befehl aus ./server -m socket -c service.ini
  3. Gehen Sie zu der Maschine, die Sie als Aggregator identifizieren. Importieren und passen Sie die Aggregator.ini -Datei importieren und passen Sie den Befehl ./aggregator aus.
  4. Gehen Sie zum Client, passen Sie die Datei config.py an und führen Sie python search.py ​​aus
• Milvus:
  1. python init.py
  2. python search.py

---

Von Christian Stingone gemacht