Distributed computation of Approximate Nearest Neighbors

Computação distribuída de vizinhos aproximados mais próximos

Este projeto faz referência ao meu trabalho de tese de mestrado "Computação distribuída de vizinhos aproximados mais próximos" para meu mestrado em ciência da computação em colaboração externa com a Wikimedia Foundation. O trabalho concentra -se em tornar o serviço de upload de imagens na Wikipedia mais eficiente, estudando como distribuir o cálculo de vizinhos aproximados mais próximos, desenvolvendo soluções ad hoc, explorando as possibilidades existentes e adaptando -as a executar pesquisas distribuídas de imagens semelhantes no conjunto de dados da Wikimedia.

O que é este repositório

Este repositório pretende conter implementações de várias bibliotecas para realizar pesquisas de similaridade (Cosine) para encontrar a melhor para minha finalidade. As várias implementações são baseadas no caso de uso exposto anteriormente.

Aproximam -se vizinhos mais próximos

• KNN: Esta biblioteca não é aproximada e é altamente ineficiente para o meu caso de uso de pesquisa, sua implementação, com a Sklearn, foi fornecida apenas para fins de comparação com bibliotecas aproximadas. Dentro do KNN, você também encontrará uma versão de força bruta que execute uma comparação linear entre um único vetor e todo o conjunto de dados, sem criar uma estrutura de dados.
• Irrita: Esta biblioteca implementa uma versão da Ann, escrita por Erik Bernhardsson em nome do Spotify.
• FAISS: Esta biblioteca foi criada para pesquisas eficientes de similaridade e agrupamento de vetores densos pela equipe de pesquisa do Facebook (agora meta).
• SPTAG: Esta biblioteca foi projetada para a pesquisa de vizinhos mais próxima do vetor em larga escala, criado pela Microsoft como uma versão alternativa à sua biblioteca anterior, chamada Diskann. Ao contrário de outras tecnologias, essa solução envolve o uso da memória RAM e do disco físico, gerenciando com eficiência qual e quanta informação economiza nelas.

Distribuiu vizinhos aproximados aproximados

• Distribuído-FAISS: Esta biblioteca já foi coberta, mas não sua versão distribuída. Esse algoritmo, embora muito eficiente, não adiciona muito novo às propostas analisadas anteriormente que são executadas em uma única máquina. O que torna essa biblioteca especial, no entanto, é que ela pode ser distribuída em várias máquinas de uma maneira muito simples.
• Distribuído-SPTAG: Esta biblioteca já foi coberta, mas não sua versão distribuída. Esse algoritmo, embora muito eficiente, não adiciona muito novo às propostas analisadas anteriormente que são executadas em uma única máquina. O que torna essa biblioteca especial, no entanto, é que ela pode ser distribuída em várias máquinas de uma maneira muito simples.
• MILVUS: Esta biblioteca implementa o banco de dados vetorial que se concentra no fornecimento de um sistema e arquitetura eficientes para pesquisas de similaridade e aplicativos movidos a IA. A necessidade que o Milvus tenta satisfazer é fornecer um sistema completo capaz de operar em enormes conjuntos de dados dinâmicos, fornecendo soluções que também podem ser executadas nas GPUs também de maneira distribuída. Para fazer isso, o Milvus foi construído em bibliotecas que já foram explicadas como FAISS, fazendo as alterações necessárias para seu caso de uso.

Como é estruturado

O projeto foi estruturado de maneira precisa para garantir uma organização fácil de arquivos e simplificar a navegação.

• Algoritmos: dentro desta pasta, você pode encontrar todas as implementações
  • for-ECH-ECH-Library:
    • config.py: este arquivo contém as configurações necessárias para a operação correta das bibliotecas
    • init.py: Este arquivo contém o código para leitura de conjuntos de dados, treinamento de dados e criação do índice
    • pesquisa.py: Este arquivo contém o código para executar pesquisas e retornar os itens resultantes
      • Outros arquivos: Chronometer.py, zombares.py
• Conjuntos de dados: os conjuntos de dados e estruturas de dados salvos na memória serão inseridos dentro desta pasta
  • Comprimido: Nesta pasta, é possível inserir os conjuntos de dados compactados, como pode ser visto no exemplo inserido. Você também pode notar um arquivo chamado links.txt contendo todos os conjuntos de dados da Wikimedia
  • Desenhado: Nesta pasta, é possível inserir os conjuntos de dados descompactados, daqui eles serão filtrados e decompostos para um funcionamento correto das bibliotecas
  • Imagens: dentro desta pasta, é possível encontrar as imagens correspondentes aos vetores extraídos do conjunto de dados
  • Vetores: dentro desta pasta, é possível encontrar os vetores correspondentes às imagens extraídas do conjunto de dados
  • formatDatasets.bash: este arquivo, executável seguindo este readme.md, contém o código para decompor todos os conjuntos de dados da pasta descompactada que move os vetores dentro dos vetores/ pasta e as imagens correspondentes dentro das imagens/ pasta. Este arquivo usa o formatDatasets.py para converter o arquivo .csv em formato binário para acelerar todo o projeto.
• Documentos: documentos obtidos durante a redação da tese

Como executar

Baixe alguns conjuntos de dados

1. Vá para a pasta compactada e execute wget -i links.txt para baixar o conjunto de dados da Wikimedia (imagens, vetores)
2. Descompacte arquivos em descompactos, no caso de dados da Wikimedia gunzip *.gz
3. Entre na pasta DataSets e siga o readme.md

Importar / instalar / compilar as bibliotecas

Primeiro, vá na pasta de algoritmos e instale requisitos gerais com pip install -r requirements.txt .

• KNN: pip install scikit-learn ou não instale nada se preferir usar a versão da força bruta
• Irrita: pip install annoy
• FAISS: Siga o tutorial do CONDA
• SPTAG: Você pode compilar esta biblioteca por meio do código -fonte ou usar o Docker. Pessoalmente, recomendo a última solução, executando estes comandos:

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

• Distribuído -FAISS: clone o repositório (se você deseja usar meu PR para adicionar precisão à fase de pesquisa com os métodos set_index_parameter ou set_index_parameters clone este repositório), digite a pasta e execute pip install -e .
• Distribuído-SPTAG: Siga as instruções para o SPTAG
• Milvus: pip install pymilvus e, em seguida, Milvus podem ser instalados com o Docker Compose ou Kubernetes (Milvus Standalone for Testing) ou com Helm + Kubernetes (Milvus Cluster for Production)

Executar as bibliotecas da Ann

Antes de executar as bibliotecas, personalize os vários arquivos config.py

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

Executar as bibliotecas distribuídas

Antes de executar as bibliotecas, personalize os vários arquivos config.py

• Distribuído-faiss:
  1. Personalize o arquivo Discovery_config.txt.
  2. Execute em cada servidor python init_server.py
  3. Execute no cliente python init_client.py
  4. Execute no cliente python search.py
• SPTAG distribuído:
  1. Vá para cada servidor, personalize o arquivo config.py (atenção para start_metadata_offset) e execute python init.py
  2. Vá para os servidores que hospedam o índice criado anteriormente. Na pasta de liberação da biblioteca, importe e personalize o arquivo service.ini e execute o comando ./server -m socket -c service.ini
  3. Vá para a máquina que você identifica como o agregador. Na pasta de liberação da biblioteca, importe e personalize o arquivo agregator.ini e execute o comando ./aggregator
  4. Vá para o cliente, personalize o arquivo config.py e execute python search.py
• Milvus:
  1. python init.py
  2. python search.py

---

Feito por Christian Stingone