Mundo pequeño navegable jerárquico

El algoritmo de 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 colección grande, sin comparar la consulta con cada elemento individualmente. ^{[ 1 ]}

Este algoritmo se utiliza habitualmente para la búsqueda en datos vectoriales . En estos sistemas, un elemento, como un documento, una imagen, una canción o un perfil de usuario, se representa mediante una lista de números denominada vector. Los elementos con vectores similares se tratan como tales según el modelo que los generó. HNSW proporciona una forma de buscar estos vectores rápidamente, especialmente en conjuntos de datos extensos.

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 general, mientras que la capa inferior contiene todos los nodos y proporciona una vista más detallada. Una búsqueda comienza en una capa superior, sigue los enlaces hacia los nodos más cercanos a la consulta y luego repite el proceso en las capas inferiores hasta encontrar un conjunto de vecinos más probables. ^{[ 1 ]}

El problema de búsqueda del vecino más cercano consiste en determinar 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 kd y el árbol R , también pueden volverse menos efectivos para datos de alta dimensionalidad, un problema frecuentemente asociado con la maldición de la dimensionalidad .

Los métodos de vecinos más cercanos aproximados sacrifican algo de exactitud a cambio de velocidad o menor consumo de recursos. En lugar de garantizar siempre el elemento más cercano exacto, intentan devolver elementos cercanos rápidamente. Otros métodos aproximados incluyen el hash sensible a la localidad y la cuantización de productos . ^{[ 1 ]}

HNSW se basa en investigaciones sobre redes de mundo pequeño y grafos navegables. En un grafo de mundo pequeño, se puede acceder a la mayoría de los nodos desde otros nodos mediante una corta cadena de enlaces. En un grafo navegable, un procedimiento de búsqueda puede utilizar información local para avanzar hacia un objetivo. El trabajo de Jon Kleinberg sobre navegación en redes de mundo pequeño es un ejemplo importante de esta área de investigación. ^{[ 2 ]} Trabajos posteriores estudiaron formas de añadir enlaces que facilitan la navegación voraz en los grafos. ^{[ 3 ]}

El algoritmo HNSW extiende métodos anteriores de mundo pequeño navegable para la búsqueda de similitud mediante la adición de 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. ^{[ 4 ]}

HNSW se basa en un grafo de proximidad. En este grafo, los vectores cercanos están conectados por aristas. El algoritmo utiliza estas aristas para recorrer el conjunto de datos , en lugar de escanear cada vector individualmente.

El gráfico es jerárquico. Cada vector aparece en la capa inferior. Algunos vectores también se ubican en capas superiores, y la cantidad de vectores disminuye a medida que se asciende en las capas. 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 los candidatos prometedores. ^{[ 1 ]}

Una búsqueda típica se desarrolla de la siguiente manera:

1. La búsqueda comienza desde un punto de entrada en la capa más alta.
2. En cada paso, el algoritmo examina los nodos vecinos y se mueve hacia un vecino que esté más cerca de la consulta.
3. Cuando no encuentra un vecino más cercano en esa capa, se desplaza a la siguiente capa.
4. 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 se suele describir como navegación voraz. El algoritmo elige repetidamente nodos localmente mejores, utilizando la estructura del grafo para aproximarse al punto de consulta.

El grafo HNSW se construye de forma incremental. Cuando se inserta un nuevo vector, el algoritmo le asigna una capa máxima, busca nodos existentes cercanos y conecta el nuevo nodo con los vecinos seleccionados en cada capa donde aparece. ^{[ 1 ]}

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 en el grafo puede mejorar la recuperación, pero requiere más memoria. Una lista de candidatos de búsqueda más extensa puede mejorar la precisión, pero ralentiza las consultas. Una lista de candidatos de construcción más extensa puede mejorar la calidad del grafo, pero ralentiza la creación del índice.

Debido a que HNSW es ​​aproximado, sus resultados no siempre son idénticos a los de 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 demostrado que las bibliotecas basadas en HNSW ofrecen un rendimiento sólido entre los métodos de vecinos más cercanos aproximados, aunque el rendimiento en el peor de los casos puede diferir del rendimiento en conjuntos de datos de referencia comunes. ^{[ 5 ] [ 6 ]}

HNSW se utiliza como índice en sistemas que almacenan y buscan vectores de alta dimensión. Estos sistemas incluyen bases de datos vectoriales, motores de búsqueda y extensiones de bases de datos. Entre sus usos típicos se encuentran la búsqueda semántica , los sistemas de recomendación , la búsqueda de similitud de imágenes y la generación aumentada de recuperación .

Varios proyectos de software implementan o dan soporte a HNSW. Las bibliotecas incluyen hnswlib, que está asociada con los autores originales de HNSW, y FAISS . ^{[ 7 ]} Los sistemas de bases de datos y búsqueda que documentan el soporte para HNSW incluyen Apache Lucene , Chroma , ClickHouse , DuckDB , MariaDB , Milvus , pgvector , Qdrant y Redis . ^{[ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]}

• Búsqueda aproximada del vecino más cercano
• Base de datos vectorial
• Hashing sensible a la localidad
• Cuantificación del producto