Pequeño mundo navegable jerarquizado o estratificado
Los Pequeños Mundos Navegables Jerarquizados o Estratificados (Hierarchical Navigable Small World (HNSW)) es un algoritmo de tipo grafo basado en la búsqueda aproximada de los K-vecinos más próximos(Approximate K-nearest neighbor search (K-ANNS)) usada en muchas bases de datos de vectores o almacenes de vectores(Vector Databases o Vector Stores).[1]
El cálculo del vecino más cercano sin el uso de un índice requiere calcular las distancias entre todos y cada uno de los puntos(nodos) existentes en la base de datos con respecto a un nuevo punto(nodo). En el contexto de los conjuntos de vectores de muchas dimensiones, las soluciones previamente existentes para realizar búsquedas de vecinos son desde el punto de vista computacional prohibitivos.
Los Pequeños Mundos Navegables Jerarquizados o Estratificados (Hierarchical Navigable Small World (HNSW)) aparecen con la intención de eliminar estas limitaciones.
Los Pequeños Mundos Navegables Jerarquizados o Estratificados (Hierarchical Navigable Small World (HNSW)) combinan dos ideas previamente existentes: los Pequeños Mundos Navegables (Navigable Small World (NSW)) y los Probability Skip Lists o Listas por Saltos Probabilísticos (estructura de datos probabilística) pero en una nueva versión en la que las listas son sustituidas por grafos.
El algoritmo de los Pequeños Mundos Navegables Jerarquizados o Estratificados es una solución que alcanza una complejidad temporal de tipo logarítmica, O(log n), lo que le hace que tengan un rendimiento superior.
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 jerárquica adicional para encontrar puntos de entrada al grafo principal más rápidos. Las bibliotecas basadas en HNSW se encuentran entre las más eficientes en las búsqueda aproximada de los K-vecinos más cercanos(Approximate K-nearest neighbor search (K-ANNS))en las pruebas de rendimiento o comparativas (benchmark).
Uso en bases de datos vectoriales[editar]
HNSW es un algoritmo clave para la búsqueda aproximada del vecino más cercano en bases de datos vectoriales de alta dimensión o bases de datos de embeddings (almacenes de embeddings), por ejemplo, en el contexto de los modelos de los lenguajes de gran tamaño(LLMs: Large Language Models). Las bases de datos de vectores o bases de datos de embeddings(almacén de embeddings) que utilizan HNSW como índice 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 proporcionada por los autores originales.
Referencias[editar]
- ↑ Malkov, Yu A.; Yashunin, D. A. (2016). «Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs». .