Distributed computation of Approximate Nearest Neighbors

Cálculo distribuido de vecinos más cercanos

Este proyecto hace referencia a mi trabajo de tesis maestra "Computación distribuida de vecinos más cercanos más cercanos" para mi maestría en informática en colaboración externa con la Fundación Wikimedia. El trabajo se centra en hacer que el servicio de carga de imágenes en Wikipedia sea más eficiente, estudiando cómo distribuir el cálculo de vecinos más cercanos aproximados, desarrollando soluciones ad hoc, explorando las posibilidades existentes y adaptándolas para realizar búsquedas distribuidas de imágenes similares dentro del conjunto de datos de Wikimedia.

¿Qué es este repositorio?

Este repositorio está destinado a contener implementaciones de varias bibliotecas para realizar búsquedas de similitud (coseno) para encontrar la mejor para mi propósito. Las diversas implementaciones se basan en el caso de uso previamente expuesto.

Vecinos más cercanos

• KNN: Esta biblioteca no es aproximada y es muy ineficiente para mi caso de uso de investigación, su implementación, con Sklearn, se ha proporcionado solo para fines de comparación con bibliotecas aproximadas. Dentro de KNN también encontrará una versión de fuerza bruta que ejecute una comparación lineal entre un solo vector y el conjunto de datos completo, sin crear una estructura de datos.
• Molesto: esta biblioteca implementa una versión de Ann, escrita por Erik Bernhardsson en nombre de Spotify.
• FAISS: Esta biblioteca fue creada para búsquedas de similitud eficientes y agrupación de vectores densos por el equipo de investigación de Facebook (ahora Meta).
• SPTAG: Esta biblioteca está diseñada para la búsqueda de vecinos más cercanos de vector a gran escala, creada por Microsoft como una versión alternativa para su biblioteca anterior, llamada Diskann. A diferencia de otras tecnologías, esta solución implica el uso de la memoria RAM y el disco físico, administrando eficientemente cuál y cuánta información ahorra en ellas.

Distribuidos aproximados vecinos más cercanos

• Distributed-Faiss: esta biblioteca ya ha sido cubierta, pero no su versión distribuida. Este algoritmo, aunque muy eficiente, no agrega mucho nuevo a las propuestas analizadas previamente que se ejecuta en una sola máquina. Sin embargo, lo que hace que esta biblioteca sea especial es que se puede distribuir en múltiples máquinas de una manera muy simple.
• Distributed-Sptag: esta biblioteca ya ha sido cubierta, pero no su versión distribuida. Este algoritmo, aunque muy eficiente, no agrega mucho nuevo a las propuestas analizadas previamente que se ejecuta en una sola máquina. Sin embargo, lo que hace que esta biblioteca sea especial es que se puede distribuir en múltiples máquinas de una manera muy simple.
• MILVUS: esta biblioteca implementa la base de datos vectorial que se centra en proporcionar un sistema eficiente y una arquitectura para búsquedas de similitud y aplicaciones con AI. La necesidad de que Milvus intente satisfacer es proporcionar un sistema completo capaz de operar en grandes conjuntos de datos dinámicos, proporcionando soluciones que también pueden ejecutarse en GPU también de manera distribuida. Para hacer esto, Milvus se basó en bibliotecas que ya se han explicado como FAISS, haciendo los cambios necesarios para su caso de uso.

Cómo está estructurado

El proyecto ha sido estructurado de una manera precisa para garantizar la organización fácil de los archivos y simplificar la navegación dentro de él.

• Algoritmos: dentro de esta carpeta puede encontrar todas las implementaciones
  • para la biblioteca para cada uno:
    • config.py: este archivo contiene las configuraciones necesarias para el funcionamiento correcto de las bibliotecas
    • init.py: este archivo contiene el código para leer conjuntos de datos, estructuras de datos de capacitación y crear el índice
    • Search.py: este archivo contiene el código para realizar búsquedas y devolver los elementos resultantes
      • Otros archivos: chronometer.py, mocks.py
• Conjuntos de datos: los conjuntos de datos y estructuras de datos guardadas en la memoria se insertarán dentro de esta carpeta
  • Comprimido: en esta carpeta es posible insertar los conjuntos de datos comprimidos, como se puede ver en el ejemplo insertado. También puede notar un archivo llamado links.txt que contiene todos los conjuntos de datos de Wikimedia
  • Descomprimido: en esta carpeta es posible insertar los conjuntos de datos descomprimidos, desde aquí se filtrarán y descomputarán para un funcionamiento correcto de las bibliotecas
  • Imágenes: dentro de esta carpeta es posible encontrar las imágenes correspondientes a los vectores extraídos del conjunto de datos
  • Vectores: dentro de esta carpeta es posible encontrar los vectores correspondientes a las imágenes extraídas del conjunto de datos
  • FormatDataSets.Bash: este archivo, ejecutable después de este readme.md, contiene el código para descomponer todos los conjuntos de datos de la carpeta descomprimida que mueve los vectores dentro de los vectores/ carpeta y las imágenes correspondientes dentro de las imágenes/ carpeta. Este archivo utiliza formatDataSets.py para convertir el archivo .csv en formato binario para acelerar todo el proyecto.
• Docs: Documentos obtenidos durante la escritura de la tesis

Cómo ejecutar

Descargar algunos conjuntos de datos

1. Vaya a la carpeta comprimida y ejecute wget -i links.txt para descargar el conjunto de datos Wikimedia (imágenes, vectores)
2. Descomprime archivos en descomprimido, en el conjunto de datos de Wikimedia, gunzip *.gz
3. Vaya a la carpeta de conjuntos de datos y siga el readme.md

Importar / instalar / compilar las bibliotecas

Primero ingrese a la carpeta de algoritmos e instale los requisitos generales con pip install -r requirements.txt .

• KNN: pip install scikit-learn o no instale nada si prefiere usar la versión Brute-Force
• Molesto: pip install annoy
• FAISS: Sigue el tutorial de conda
• SPTAG: puede compilar esta biblioteca a través del código fuente o usar Docker. Personalmente recomiendo la última solución, ejecutando estos comandos:

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

• Distributed -Faiss: Clone el repositorio (si desea usar mi PR para agregar precisión a la fase de búsqueda con set_index_parameter o set_index_parameters clon este repositorio), ingrese la carpeta y luego ejecute pip install -e .
• Distributed-SpTAg: siga las instrucciones de SPTAG
• MILVUS: pip install pymilvus y luego Milvus se puede instalar con Docker Compose o Kubernetes (Milvus independiente para la prueba) o con Helm + Kubernetes (clúster de Milvus para la producción)

Ejecutar las bibliotecas ANN

Antes de ejecutar las bibliotecas, personalice los diversos archivos config.py

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

Ejecutar las bibliotecas de ANN distribuidas

Antes de ejecutar las bibliotecas, personalice los diversos archivos config.py

• Faiss distribuido:
  1. Personalice el archivo Discovery_Config.txt.
  2. Ejecutar en cada servidor python init_server.py
  3. Ejecutar en el cliente python init_client.py
  4. Ejecutar en el cliente python search.py
• Sptag distribuido:
  1. Vaya a cada servidor, personalice el archivo config.py (atención a start_metadata_offset) y ejecute python init.py
  2. Vaya a los servidores alojando el índice creado anteriormente. En la carpeta de lanzamiento de la biblioteca, importe y personalice el archivo Service.ini y ejecute el comando ./server -m socket -c service.ini
  3. Vaya a la máquina que se identifica como agregador. En la carpeta de lanzamiento de la biblioteca, importe y personalice el archivo agregador.ini y ejecute el comando ./aggregator
  4. Vaya al cliente, personalice el archivo config.py y ejecute python search.py
• Milvus:
  1. python init.py
  2. python search.py

---

Hecho por Christian Stingone