HNSWLib es una biblioteca de C++ de solo cabecera que implementa el algoritmo de Mundo Pequeño Navegable Jerárquico (HNSW) para la búsqueda aproximada del vecino más cercano. La biblioteca está diseñada para encontrar elementos similares a un elemento de consulta en grandes colecciones de datos vectoriales sin comparar la consulta contra cada elemento individualmente. Se utiliza comúnmente en sistemas de aprendizaje automático, aplicaciones de inteligencia artificial y bases de datos vectoriales donde la velocidad y la escalabilidad son críticas.
El algoritmo HNSW, que HNSWLib implementa, almacena vectores en una estructura de grafo de múltiples capas. Cada vector se convierte en un nodo, y los enlaces lo conectan con vectores cercanos. Las capas superiores contienen menos nodos y actúan como un mapa grueso, mientras que la capa inferior contiene todos los nodos para una búsqueda detallada. Una búsqueda comienza en una capa superior, sigue enlaces hacia nodos más cercanos a la consulta, y luego repite el proceso en capas inferiores hasta identificar un conjunto de vecinos más cercanos probables.
Antecedentes
El problema de la búsqueda del vecino más cercano pregunta qué elementos de un conjunto de datos están más cerca de un elemento de consulta. Una búsqueda directa compara la consulta con cada elemento, lo que se vuelve lento para conjuntos de datos grandes. Los métodos exactos que utilizan árboles espaciales como el árbol k-d o el árbol R pierden efectividad en datos de alta dimensión debido a la maldición de la dimensionalidad. Los métodos aproximados de vecino más cercano intercambian exactitud por velocidad, devolviendo elementos cercanos rápidamente en lugar de garantizar el más cercano absoluto.
HNSW se basa en investigaciones sobre redes de mundo pequeño y grafos navegables. En los grafos de mundo pequeño, la mayoría de los nodos se conectan a través de cadenas cortas de enlaces. El trabajo de Jon Kleinberg sobre navegación en redes de mundo pequeño influyó en investigaciones posteriores sobre añadir enlaces que facilitan la navegación codiciosa en grafos. El algoritmo HNSW extiende métodos anteriores de mundo pequeño navegable añadiendo una jerarquía de capas de grafo, lo que ayuda a encontrar una buena región antes de la búsqueda detallada.
Algoritmo
HNSWLib utiliza un grafo de proximidad donde los vectores cercanos están conectados por aristas. El algoritmo se mueve a través del conjunto de datos utilizando estas aristas en lugar de escanear cada vector. El grafo es jerárquico: cada vector aparece en la capa inferior, mientras que algunos vectores también aparecen en capas superiores con menos vectores a medida que las capas ascienden. Las capas superiores permiten movimiento de largo alcance, mientras que las capas inferiores permiten una búsqueda detallada cerca de candidatos prometedores.
Una búsqueda típica comienza desde un punto de entrada en la capa más alta. En cada paso, el algoritmo examina los nodos vecinos y se mueve hacia uno más cercano a la consulta. Cuando no existe un vecino más cercano en esa capa, desciende a la siguiente capa. En la capa inferior, explora un conjunto de candidatos más amplio y devuelve los candidatos más cercanos encontrados. Esta navegación codiciosa elige repetidamente nodos localmente mejores para acercarse al punto de consulta.
Construcción y parámetros
El grafo HNSW se construye incrementalmente. Al insertar un nuevo vector, el algoritmo le asigna una capa máxima, busca nodos existentes cercanos y conecta el nuevo nodo con vecinos seleccionados en cada capa donde aparece. Las implementaciones exponen parámetros que controlan los intercambios entre velocidad, precisión, uso de memoria y tiempo de construcción. Conexiones de grafo más altas mejoran el recuerdo pero requieren más memoria. Listas de candidatos de búsqueda más grandes mejoran la precisión pero ralentizan las consultas. Listas de candidatos de construcción más grandes mejoran la calidad del grafo pero ralentizan la construcción del índice.
Debido a que HNSW es aproximado, los resultados pueden diferir de las búsquedas exactas. El rendimiento práctico depende de las características del conjunto de datos, la medida de distancia, la calidad de la implementación y la configuración de parámetros. Estudios de evaluación comparativa han encontrado que las bibliotecas basadas en HNSW son fuertes competidores entre los métodos aproximados de vecino más cercano, aunque el rendimiento en el peor caso puede diferir de los resultados comunes de evaluación comparativa.
Uso en sistemas de búsqueda vectorial
HNSWLib se utiliza como índice en sistemas que almacenan y buscan vectores de alta dimensión, incluyendo bases de datos vectoriales, motores de búsqueda y extensiones de bases de datos. Las aplicaciones típicas incluyen búsqueda semántica, sistemas de recomendación, búsqueda de similitud de imágenes y generación aumentada por recuperación. La biblioteca está asociada con los autores originales de HNSW y es ampliamente adoptada en entornos de producción.
Varios proyectos de software implementan o soportan HNSW. Las bibliotecas incluyen HNSWLib y FAISS. Los sistemas de bases de datos y búsqueda que documentan soporte para HNSW incluyen Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant y Redis. Estos sistemas aprovechan HNSW para búsqueda aproximada rápida en aplicaciones que van desde la recuperación de modelos de lenguaje grandes hasta pipelines de IA generativa.
Véase también
- Búsqueda aproximada del vecino más cercano
- Base de datos vectorial
- Hash sensible a la localidad
- Cuantización de productos