SimilaritySearch.jl
v0.11.10
SimilitySearch.jl est une bibliothèque pour la recherche voisine la plus proche. En particulier, il contient l'implémentation de SearchGraph, un index de recherche rapide et flexible à l'aide de n'importe quelle fonction métrique. Il est conçu pour prendre en charge le multithreading dans la plupart de ses fonctions et structures.
Le package fournit les index suivants:
ParallelExhaustiveSearch : Un index de recherche de force brute où chaque requête est résolue à l'aide de tous les threads disponibles.ExhaustiveSearch : Un index de recherche de force brute, chaque requête est résolue à l'aide d'un seul thread.SearchGraph : Un index de recherche approximatif avec construction parallèle.L'ensemble principal des fonctions est:
search : résout une seule requête.searchbatch : résout un ensemble de requêtes.allknn : calcule le neardup : supprime les proches-dupliques d'un ensemble de données métrique.closestpair : calcule la paire la plus proche d'un ensemble de données métrique.Les définitions précises de ces fonctions et l'ensemble complet des fonctions et des structures peuvent être trouvés dans la documentation.
Actuellement, il existe plusieurs paquets dédiés à la recherche de voisin le plus proche, par exemple, nous avons NearestNeighbors.jl , la recherche de recherche, les KD-Trees, les arbres de balle, les quadtremes, RegionTrees.jl Octrees, les BK-Trees JuliaNeighbors les KD-Trees, les Trees, les Quadtrees, les Octrees, les BK-Trees, le VP-Tree et les autres structures multidimensionnelles et métriques. Ces structures fonctionnent assez bien pour les données de faible dimension car elles sont conçues pour résoudre les requêtes de similitude exactes.
Il existe plusieurs packages effectuant une recherche de similitude approximative, comme Rayuela.jl en utilisant des schémas de quantification de produit, le wrapper pour la bibliothèque FAISS Faiss.jl . La bibliothèque FAISS fournit des implémentations à haute performance des schémas de quantification des produits et des schémas de hachage sensibles à la localité, ainsi qu'une mise en œuvre de la force industrielle de l'indice HNSW . Le NearestNeighborDescent.jl le borderscent.jl implémente l'algorithme de recherche derrière pynndescent .
Le package de SimilaritySearch.jl essaie d'enrichir l'écosystème avec des structures de recherche et des algorithmes conçus pour profiter des systèmes multithreading et une fonction de mise à jour unique qui simplifie son utilisation pour les praticiens. Ces fonctionnalités sont implémentées succinctement et efficacement en raison du dynamisme et des performances du langage de programmation Julia. En ce qui concerne les caractéristiques de performance, les temps de construction sont considérablement réduits par rapport à des approches similaires sans réduire les performances de recherche ou la qualité des résultats.
Vous pouvez installer le package comme suit
] add SimilaritySearch . jlVous pouvez également exécuter l'ensemble des tests comme suit
] test SimilaritySearchVeuillez consulter des exemples. Vous trouverez une liste de cahiers Jupyter et Pluton, et certains scripts qui illustrent son utilisation.
Les contributions sont les bienvenues. Veuillez remplir une demande de traction de documentation et de contributions de mise en œuvre. Pour les problèmes, veuillez remplir un problème avec les informations nécessaires (voir ci-dessous.) Si vous avez déjà une solution, veuillez également fournir une demande de traction.
RAPPORT Les problèmes dans le package fournissant un exemple reproductible minimal. Si le problème dépend des données, n'oubliez pas de fournir les données nécessaires pour les reproduire.
SearchGraph La structure de recherche principale, le SearchGraph, est un graphique avec plusieurs caractéristiques, dont beaucoup induites par l'ensemble de données indexé. Certaines de ses limitations connues sont liées à ces caractéristiques. Par exemple:
Le manuscrit suivant décrit et repose l'index SearchGraph (version du package 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}
}
L'algorithme actuel (version 0.8 et 0.9 ) est décrit et comparé dans le manuscrit suivant:
@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}
}
Ce package est également décrit dans le journal Joss:
Eric S. Tellez et Guillermo Ruiz.
SimilaritySearch.jl: Index du voisin le plus proche autotuné pour Julia . Journal of Open Source Software https://doi.org/10.21105/joss.04442.
Les algorithmes de cette version sont les mêmes que V0.8 mais cassez la compatibilité de l'API:
Polyester pour gérer le multithreading au lieu de threads. @ Threadsallknn préserve désormais les auto-références pour simplifier les algorithmes et améliorer l'efficacité ( allknn en V0.8 supprime automatiquement les auto-références)Autres:
SearchGraphtimedsearchbatch Il est facile d'ajuster la structure SearchGraph à différentes charges de travail et applications. Par exemple,
Veuillez vous référer à https://github.com/sadit/similaritysearchdemos et https://github.com/sadit/similaritysearch.jl/blob/main/test/testsearchgraph.jl pour les exemples de travail.
Il introduit un refactorisation majeure. En particulier, il utilise explicite des objets de contexte pour la plupart des fonctions. Il introduit également des procédures de journalisation simples. Cependant, nous préservons la compatibilité dans de nombreuses fonctions publiques en utilisant une utilisation implicite d'objets de contexte par défaut.
