SimilaritySearch.jl

SimilaritySearch.jl

SimilaritySearch.jl é uma biblioteca para a pesquisa de vizinhos mais próxima. Em particular, ele contém a implementação do SearchGraph, um índice de pesquisa rápido e flexível usando qualquer função métrica. Ele foi projetado para suportar multithreading na maioria de suas funções e estruturas.

O pacote fornece os seguintes índices:

• ParallelExhaustiveSearch : Um índice de pesquisa de força bruta, onde cada consulta é resolvida usando todos os threads disponíveis.
• ExhaustiveSearch : um índice de pesquisa de força bruta, cada consulta é resolvida usando um único thread.
• SearchGraph : um índice de pesquisa aproximado com construção paralela.

O principal conjunto de funções são:

• search : resolve uma única consulta.
• searchbatch : resolve um conjunto de consultas.
• allknn : calcula o $ k $ Vizinhos mais próximos para todos os elementos em um índice.
• neardup : remove quase duplicatos de um conjunto de dados métricos.
• closestpair : calcula o par mais próximo em um conjunto de dados métricos.

As definições precisas dessas funções e o conjunto completo de funções e estruturas podem ser encontradas na documentação.

Ecossistema de busca de similaridade em Julia

Atualmente, existem vários pacotes dedicados à pesquisa de vizinhos mais próximos, por exemplo, temos RegionTrees.jl NearestNeighbors.jl JuliaNeighbors estruturas de pesquisa como árvores de KD, árvores de bola, quadtrees, octrees, BK-árvores, VP-Tree e outras estruturas multidimensionais e métricas. Essas estruturas funcionam muito bem para dados de baixa dimensão, pois foram projetados para resolver consultas exatas de similaridade.

Existem vários pacotes que realizam pesquisas aproximadas de similaridade, como Rayuela.jl usando esquemas de quantização de produtos, o invólucro da biblioteca FAISS Faiss.jl . A Biblioteca FAISS fornece implementações de alto desempenho dos esquemas de quantização de produtos e esquemas de hash sensíveis à localidade, juntamente com uma implementação de resistência industrial do índice HNSW . O NearestNeighborDescent.jl algodescentes e implementos do algoritmo de pesquisa atrás pynndescent .

O pacote SimilaritySearch.jl tenta enriquecer o ecossistema com estruturas e algoritmos de pesquisa projetados para aproveitar os sistemas de leitura multith e um recurso exclusivo de autotuning que simplifica seu uso para os profissionais. Esses recursos são implementados de maneira sucinta e eficiente devido ao dinamismo e desempenho da linguagem de programação Julia. Em relação às características de desempenho, os tempos de construção são muito reduzidos em comparação com abordagens semelhantes sem reduzir o desempenho da pesquisa ou a qualidade dos resultados.

Instalando o similaritySearch

Você pode instalar o pacote da seguinte maneira

] add SimilaritySearch . jl

Além disso, você pode executar o conjunto de testes da seguinte forma

] test SimilaritySearch

Usando a biblioteca

Por favor, veja exemplos. Você encontrará uma lista de notebooks Jupyter e Plutão e alguns scripts que exemplificam seu uso.

Contribuir

Contribuições são bem -vindas. Por favor, preencha uma solicitação de tração para documentar e implementar contribuições. Para problemas, preencha um problema com as informações necessárias (veja abaixo). Se você já possui uma solução, forneça uma solicitação de tração.

Problemas

Relatar problemas no pacote, fornecendo um exemplo reprodutível mínimo. Se o problema depender de dados, não se esqueça de fornecer os dados necessários para reproduzi -lo.

Limitações do SearchGraph

A estrutura de pesquisa principal, o SearchGraph, é um gráfico com várias características, muitas delas induzidas pelo conjunto de dados sendo indexadas. Algumas de suas limitações conhecidas estão relacionadas a essas características. Por exemplo:

• As distâncias métricas funcionam bem; Por outro lado, a semi-métrica deve funcionar, mas os recursos de roteamento ainda não estão caracterizados.
• Mesmo quando funciona muito bem em comparação às alternativas, métricas discretas como a distância de Levenshtein e outras que tomam poucos valores possíveis também podem obter desempenho baixo.
• Algo semelhante acontecerá quando houver muitos quase duplicatos (elementos bem próximos). Nesse caso, é necessário remover quase duplicatos e colocá-los em sacos associados a alguns de seus objetos próximos.
• Os conjuntos de dados dimensionais muito altos produzirão distribuições de cauda longa do número de arestas por vértice. Em casos extremos, você deve podar grandes bairros e enriquecer caminhos de ponta única.

Sobre as estruturas e algoritmos

O manuscrito a seguir descreve e os benchmarks do índice SearchGraph (versão do pacote 0.6 ):

 @article{tellezscalable,
  title={A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs},
  author={Tellez, Eric S and Ruiz, Guillermo and Chavez, Edgar and Graff, Mario},
  journal={Pattern Analysis and Applications},
  pages={1--15},
  publisher={Springer}
}

O algoritmo atual (versão 0.8 e 0.9 ) é descrito e comparado no manuscrito a seguir:

@misc{tellez2022similarity,
      title={Similarity search on neighbor's graphs with automatic Pareto optimal performance and minimum expected quality setups based on hyperparameter optimization}, 
      author={Eric S. Tellez and Guillermo Ruiz},
      year={2022},
      eprint={2201.07917},
      archivePrefix={arXiv},
      primaryClass={cs.IR}
}

Este pacote também é descrito no Joss Paper:

Eric S. Tellez e Guillermo Ruiz. SimilaritySearch.jl : índices de vizinhos mais próximos para Julia . Journal of Open Source Software https://doi.org/10.21105/joss.04442.

Sobre a série v0.9.x

Os algoritmos desta versão são os mesmos que v0.8, mas a compatibilidade da API de interrupção:

• Agora, ele usa o pacote Polyester para lidar com o multithreading em vez de threads.@Threads
• Os métodos multithreading são ativados por padrão se o processo for iniciado com vários threads; na v0.8 era o contrário
• allknn agora preserva as auto-referências para simplificar os algoritmos e melhorar a eficiência ( allknn na v0.8 remove as auto-referências automaticamente)

Outros:

• Adiciona documentos de função e benchmarks
• Adiciona métodos de poda de gráfico SearchGraph
• Remove a função timedsearchbatch

Sobre a série v0.10.x

Isso facilita o ajuste da estrutura SearchGraph para diferentes cargas de trabalho e aplicativos. Por exemplo,

• Mais controle para parâmetros de construção
• Carregando e salvando
• Refactores API de pesquisa para serem consistentes entre estruturas

Consulte https://github.com/sadit/similaritysearchdemos e https://github.com/sadit/similaritysearch.jl/blob/main/test/testsearchgraph.jl para exemplos de trabalho.

Sobre a série V0.11

Introduz uma grande refatoração. Em particular, faz uso explícito de objetos de contexto para a maioria das funções. Ele também apresenta procedimentos simples de registro. No entanto, preservamos a compatibilidade em muitas funções públicas usando o uso implícito de objetos de contexto padrão.