Pequeño mundo navegable jerarquizado o estratificado

Ciencia de redes

Pequeño mundo navegable jerarquizado o estratificado (en inglés Hierarchical Navigable Small World(HNSW))

El Pequeño mundo navegable jerarquizado o estratificado (Hierarchical navigable small world (HNSW) en inglés) es un algoritmo de tipo grafo basado en la búsqueda aproximativa de los K-vecinos más cercanos (en inglés Approximate k-nearest neighbor search (ANNS)) usada en muchas bases de datos de vectores o almacenes de vectores (Vector databases o vector stores en inglés ).[1]​[2]​

La búsqueda aproximativa del vecino más cercano sin utilizar un índice de vectores, implica calcular las distancias entre la consulta (query en inglés) hasta cada punto de la base de datos, lo que para conjuntos de datos muy numerosos es desde el punto de vista computacional prohibitivo.Para datos de múltiples y numerosas dimensiones, las técnicas de búsqueda de vectores exactos basadas en árboles, como el Árbol k-dimensional o Árbol kd (k-d tree en inglés ) y el Árbol-R (R-tree en inglés ), no funcionan suficientemente bien debido a la maldición de la dimensión. Para remediar esto, se han propuesto búsquedas aproximativas de los k-vecinos más cercanos, como el Hashing sensible al entorno (en inglés locality-sensitive hashing (LSH)) y la cuantificación del producto (PQ), que priorizan el rendimiento sobre la precisión.[2]​ El Pequeño mundo navegable jerarquizado o estratificado ofrece una búsqueda aproximativa de los k-vecinos más cercanos que se escala de forma logarítmica incluso con datos de múltiples y numerosas dimensiones.

Es una extensión del trabajo anterior sobre grafos de mundos pequeños navegables presentado en la conferencia Similarity Search and Applications (SISAP) en 2012 con una navegación jerarquizada adicional para encontrar puntos de entrada al grafo principal más rápidos.[3]​ Las soluciones basadas en este algoritmo se encuentran entre las más eficientes en la búsqueda aproximativa de los k-vecinos más próximos en las pruebas de rendimiento o comparativas (benchmark).[4]​[5]​[6]​

Uso en bases de datos vectoriales

El Pequeño mundo navegable jerarquizado o estratificado es un algoritmo clave para la búsqueda aproximativa del vecino más cercano en bases de datos vectoriales de múltiples dimensiones; en los casos, por ejemplo, de las bases de datos de vectores (en inglés embeddings) en el contexto de los modelos de los lenguajes de gran tamaño (en inglés Large Language Models (LLMs). Las bases de datos de vectores o bases de datos de embeddings (almacén de embeddings) que utiliza el Pequeño mundo navegable jerarquizado o estratificado como índice de vectores de búsqueda incluyen:

• Búsqueda de vectores de Apache Lucene
• Chroma
• FAISS
• Qdrant
• Vespa
• Vearch Gamma
• Weaviate

Varios de ellos utilizan la biblioteca hnswlib [7]​ proporcionada por los autores originales.

Referencias

1. Malkov, Yu A.; Yashunin, D. A. (2016). «Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs». arXiv:1603.09320  [cs.DS]. 
2. Malkov, Yury A; Yashunin, Dmitry A (1 de abril de 2020). «Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs». IEEE Transactions on Pattern Analysis and Machine Intelligence 42 (4): 824-836. PMID 30602420. arXiv:1603.09320. doi:10.1109/TPAMI.2018.2889473. 
3. Malkov, Yury; Ponomarenko, Alexander; Logvinov, Andrey; Krylov, Vladimir (2012). «Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces». En Navarro, Gonzalo; Pestov, Vladimir, eds. Similarity Search and Applications. Lecture Notes in Computer Science (en inglés) 7404. Berlin, Heidelberg: Springer. pp. 132-147. ISBN 978-3-642-32153-5. doi:10.1007/978-3-642-32153-5_10. 
4. Aumüller, Martin; Bernhardsson, Erik; Faithfull, Alexander (2017). «ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms». En Beecks, Christian; Borutta, Felix; Kröger, Peer et al., eds. Similarity Search and Applications. Lecture Notes in Computer Science (en inglés) 10609. Cham: Springer International Publishing. pp. 34-49. ISBN 978-3-319-68474-1. arXiv:1807.05614. doi:10.1007/978-3-319-68474-1_3.  Se sugiere usar |número-editores= (ayuda)
5. Aumüller, Martin; Bernhardsson, Erik; Faithfull, Alexander (2020). «ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms». Information Systems (en inglés) 87: 101374. arXiv:1807.05614. doi:10.1016/j.is.2019.02.006. 
6. «ANN-Benchmarks». ann-benchmarks.com. Consultado el 19 de marzo de 2024. 
7. nmslib/hnswlib, nmslib, 18 de marzo de 2024, consultado el 19 de marzo de 2024 .