SimilaritySearch.jl
v0.11.10
SimilitySearch.jl es una biblioteca para la búsqueda de vecinos más cercanos. En particular, contiene la implementación de SearchGraph, un índice de búsqueda rápido y flexible que utiliza cualquier función métrica. Está diseñado para admitir múltiples lectura en la mayoría de sus funciones y estructuras.
El paquete proporciona los siguientes índices:
ParallelExhaustiveSearch : un índice de búsqueda de fuerza bruta donde cada consulta se resuelve utilizando todos los hilos disponibles.ExhaustiveSearch : un índice de búsqueda de fuerza bruta, cada consulta se resuelve usando un solo hilo.SearchGraph : un índice de búsqueda aproximado con construcción paralela.El conjunto principal de funciones es:
search : resuelve una sola consulta.searchbatch : resuelve un conjunto de consultas.allknn : calcula el neardup : Elimina casi duplicados de un conjunto de datos métrico.closestpair : calcula el par más cercano en un conjunto de datos métrico.Las definiciones precisas de estas funciones y el conjunto completo de funciones y estructuras se pueden encontrar en la documentación.
Actualmente, existe varios paquetes dedicados a la búsqueda de vecinos más RegionTrees.jl , por JuliaNeighbors , tenemos NearestNeighbors.jl . Estas estructuras funcionan bastante bien para datos de baja dimensión, ya que están diseñadas para resolver consultas de similitud exacta.
Existen varios paquetes que realizan una búsqueda aproximada de similitud, como Rayuela.jl utilizando esquemas de cuantificación de productos, el envoltorio para la biblioteca FAISS Faiss.jl . La biblioteca FAISS proporciona implementaciones de alto rendimiento de los esquemas de cuantificación de productos y los esquemas de hash de la localidad, junto con una implementación de fuerza industrial del índice HNSW . El NearestNeighborDescent.jl implementa el algoritmo de búsqueda detrás de pynndescent .
El paquete SimilaritySearch.jl intenta enriquecer el ecosistema con estructuras de búsqueda y algoritmos diseñados para aprovechar los sistemas de lectura múltiple y una característica de autoengrama única que simplifica su uso para los profesionales. Estas características se implementan de manera sucinta y eficiente debido al dinamismo y el rendimiento del lenguaje de programación de Julia. Con respecto a las características de rendimiento, los tiempos de construcción se reducen enormemente en comparación con enfoques similares sin reducir el rendimiento de la búsqueda o la calidad de los resultados.
Puede instalar el paquete de la siguiente manera
] add SimilaritySearch . jlAdemás, puede ejecutar el conjunto de pruebas de la siguiente manera
] test SimilaritySearchConsulte ejemplos. Encontrará una lista de cuadernos Jupyter y Plutón, y algunos scripts que ejemplifican su uso.
Las contribuciones son bienvenidas. Complete una solicitud de extracción de documentos e contribuciones de implementación. Para los problemas, llene un problema con la información necesaria (consulte a continuación). Si ya tiene una solución, también proporcione una solicitud de extracción.
Informe los problemas en el paquete que proporciona un ejemplo mínimo reproducible. Si el problema depende de los datos, no olvide proporcionar los datos necesarios para reproducirlo.
SearchGraph La estructura de búsqueda principal, SearchGraph, es un gráfico con varias características, muchas de ellas inducidas por el conjunto de datos que se está indexando. Algunas de sus limitaciones conocidas están relacionadas con estas características. Por ejemplo:
El siguiente manuscrito describe y compare el índice SearchGraph (Versión del paquete 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}
}
El algoritmo actual (versión 0.8 y 0.9 ) se describe y compare en el siguiente manuscrito:
@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 paquete también se describe en el documento de Joss:
Eric S. Tellez y Guillermo Ruiz.
SimilaritySearch.jl: índices vecinos más cercanos de autotoned para Julia . Revista de software de código abierto https://doi.org/10.21105/Joss.04442.
Los algoritmos de esta versión son los mismos que V0.8 pero Break API Compatibilidad:
Polyester para manejar múltiples lecturas en lugar de hilos.@Hilosallknn ahora preserva las autorreferencias para simplificar los algoritmos y mejorar la eficiencia ( allknn en V0.8 elimina las autorreferencias automáticamente)Otros:
SearchGraphtimedsearchbatch Facilita ajustar la estructura SearchGraph a diferentes cargas y aplicaciones de trabajo. Por ejemplo,
Consulte https://github.com/sadit/similaritysearchdemos y https://github.com/sadit/similaritysearch.jl/blob/main/test/testsearchgraph.jl para ejemplos de trabajo.
Presenta una refactorización importante. En particular, hace un uso explícito de los objetos de contexto para la mayoría de las funciones. También introduce procedimientos de registro simples. Sin embargo, preservamos la compatibilidad en muchas funciones públicas utilizando el uso implícito de objetos de contexto predeterminados.
