El mundo pequeño navegable jerárquico (HNSW) es un algoritmo para la búsqueda aproximada del vecino más cercano. Se utiliza para encontrar elementos similares a un elemento de consulta en una gran colección, sin comparar la consulta con cada elemento uno por uno. El algoritmo se utiliza comúnmente para buscar datos vectoriales, donde elementos como documentos, imágenes, canciones o perfiles de usuario se representan como listas de números llamadas vectores. Los elementos con vectores similares se tratan como similares según el modelo que produjo los vectores, y HNSW proporciona una forma de buscar estos vectores rápidamente, especialmente en conjuntos de datos grandes.
HNSW almacena vectores en un grafo. Cada vector es un nodo, y los enlaces lo conectan con algunos vectores cercanos. El grafo tiene varias capas: las capas superiores contienen menos nodos y actúan como un mapa aproximado, mientras que la capa inferior contiene todos los nodos y ofrece una vista más detallada. Una búsqueda comienza en una capa superior, sigue los enlaces hacia nodos que están más cerca de la consulta, y luego repite el proceso en capas inferiores hasta encontrar 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 puede comparar la consulta con cada elemento del conjunto de datos, pero esto se vuelve lento cuando el conjunto de datos es grande. Los métodos de búsqueda exacta basados en árboles espaciales, como el árbol k-d y el árbol R, también pueden volverse menos efectivos para datos de alta dimensionalidad, un problema a menudo asociado con la maldición de la dimensionalidad.
Los métodos aproximados de vecino más cercano intercambian algo de exactitud por velocidad o menor uso de recursos. En lugar de garantizar siempre el elemento exacto más cercano, intentan devolver elementos cercanos rápidamente. Otros métodos aproximados incluyen el hashing sensible a la localidad y la cuantificación de productos.
HNSW se basa en la investigación sobre redes de mundo pequeño y grafos navegables. En un grafo de mundo pequeño, la mayoría de los nodos se pueden alcanzar desde otros nodos a través de una cadena corta de enlaces. En un grafo navegable, un procedimiento de búsqueda puede usar información local para moverse hacia un objetivo. El trabajo de Jon Kleinberg sobre la navegación en redes de mundo pequeño es un ejemplo importante de esta área de investigación. Trabajos posteriores estudiaron formas de agregar enlaces que faciliten la navegación codiciosa en los grafos.
El algoritmo HNSW extiende los métodos anteriores de mundo pequeño navegable para la búsqueda de similitud añadiendo una jerarquía de capas de grafo. Esta jerarquía ayuda al algoritmo a encontrar una buena región del grafo antes de realizar una búsqueda más detallada en la capa inferior.
Algoritmo
HNSW se basa en un grafo de proximidad. En este grafo, los vectores cercanos están conectados por aristas. El algoritmo usa estas aristas para moverse a través del conjunto de datos, en lugar de escanear cada vector.
El grafo es jerárquico. Cada vector aparece en la capa inferior. Algunos vectores también se colocan en capas superiores, con menos vectores apareciendo a medida que las capas suben. Las capas superiores permiten un movimiento de largo alcance a través del conjunto de datos, mientras que las capas inferiores permiten una búsqueda más detallada cerca de candidatos prometedores.
Una búsqueda típica procede de la siguiente manera:
- La búsqueda comienza desde un punto de entrada en la capa más alta.
- En cada paso, el algoritmo examina los nodos vecinos y se mueve a un vecino que esté más cerca de la consulta.
- Cuando no puede encontrar un vecino más cercano en esa capa, baja a la siguiente capa.
- En la capa inferior, explora un conjunto más amplio de nodos candidatos y devuelve los candidatos más cercanos encontrados.
Esta estrategia de búsqueda a menudo se describe como navegación codiciosa. El algoritmo elige repetidamente nodos localmente mejores, usando la estructura del grafo para acercarse al punto de consulta.
Construcción y parámetros
El grafo HNSW se construye incrementalmente. Cuando se inserta un nuevo vector, el algoritmo le asigna una capa máxima, busca nodos cercanos existentes y conecta el nuevo nodo a vecinos seleccionados en cada capa donde aparece.
Las implementaciones suelen exponer parámetros que controlan el equilibrio entre velocidad, precisión, uso de memoria y tiempo de construcción. Un mayor número de conexiones de grafo puede mejorar el recall pero requiere más memoria. Una lista de candidatos de búsqueda más grande puede mejorar la precisión pero hace que las consultas sean más lentas. Una lista de candidatos de construcción más grande puede mejorar la calidad del grafo pero hace que la construcción del índice sea más lenta.
Debido a que HNSW es aproximado, sus resultados no siempre son idénticos a una búsqueda exacta completa. Su rendimiento práctico depende del conjunto de datos, la medida de distancia, la implementación y la configuración de parámetros. Los estudios de evaluación comparativa han encontrado que las bibliotecas basadas en HNSW son fuertes competidoras entre los métodos aproximados de vecino más cercano, aunque el rendimiento en el peor caso puede diferir del rendimiento en conjuntos de datos de referencia comunes.
Uso en sistemas de búsqueda vectorial
HNSW se utiliza como índice en sistemas que almacenan y buscan vectores de alta dimensionalidad. Estos sistemas incluyen bases de datos vectoriales, motores de búsqueda y extensiones de bases de datos. Los usos típicos incluyen búsqueda semántica, sistemas de recomendación, búsqueda de similitud de imágenes y generación aumentada por recuperación, que a menudo se aplica en pipelines de IA generativa y modelos de lenguaje grandes.
Varios proyectos de software implementan o admiten HNSW. Las bibliotecas incluyen hnswlib, que está asociada con los autores originales de HNSW, 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. Estas herramientas se implementan comúnmente en plataformas en la nube como Amazon Web Services, Microsoft Azure y Google Cloud para cargas de trabajo de aprendizaje automático en producción.
Véase también
- Búsqueda aproximada del vecino más cercano
- Base de datos vectorial
- Hashing sensible a la localidad
- Cuantificación de productos