Pequeño mundo navegable jerárquico

Este artículo puede resultar demasiado técnico para que la mayoría de los lectores lo comprendan . Ayúdenos a mejorarlo para que sea comprensible para los no expertos , sin eliminar los detalles técnicos. ( Febrero de 2024 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Parte de una serie sobre
Ciencia de redes
Teoría
Gráfico Red compleja Contagio Mundo pequeño Sin escala Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Optimization Reciprocity Closure Homophily Transitivity Preferential attachment Balance theory Network effect Social influence
Network types
Informational (computing) Telecommunication Transport Social Scientific collaboration Biological Artificial neural Interdependent Semantic Spatial Dependency Flow on-Chip
Graphs
Features Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix Types Bipartite Complete Directed Hyper Labeled Multi Random Weighted
Metrics Algorithms
Centrality Degree Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Bianconi–Barabási Fitness model Watts–Strogatz Exponential random (ERGM) Random geometric (RGG) Hyperbolic (HGN) Hierarchical Stochastic block Blockmodeling Maximum entropy Soft configuration LFR Benchmark Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory
v t e

El algoritmo Hierarchical navigable small world ( HNSW ) es una técnica de búsqueda aproximada del vecino más cercano basada en gráficos que se utiliza en muchas bases de datos vectoriales . ^{[1] [2]} La búsqueda del vecino más cercano sin un índice implica calcular la distancia desde la consulta hasta cada punto de la base de datos, lo que para conjuntos de datos grandes es computacionalmente prohibitivo. Para datos de alta dimensión, las técnicas de búsqueda vectorial exacta basadas en árboles, como el árbol kd y el árbol R, no funcionan lo suficientemente bien debido a la maldición de la dimensionalidad . Para remediar esto, se han propuesto búsquedas aproximadas de vecinos k más cercanos, como el hashing sensible a la localidad (LSH) y la cuantificación del producto (PQ) que intercambian rendimiento por precisión. ^[2] El gráfico HNSW ofrece una búsqueda aproximada de vecinos k más cercanos que escala logarítmicamente incluso en datos de alta dimensión.

Es una extensión del trabajo anterior sobre gráficos navegables de mundos pequeños presentado en la conferencia Similarity Search and Applications (SISAP) en 2012 con una navegación jerárquica adicional para encontrar puntos de entrada al gráfico principal más rápido. ^[3] Las bibliotecas basadas en HNSW se encuentran entre las que tienen mejor desempeño en el punto de referencia de vecinos más cercanos aproximados. ^{[4] [5] [6]}

HNSW es ​​un método clave para la búsqueda aproximada del vecino más próximo en bases de datos vectoriales de alta dimensión, por ejemplo, en el contexto de incrustaciones de redes neuronales en modelos de lenguaje de gran tamaño. Las bases de datos que utilizan HNSW como índice de búsqueda incluyen:

• Búsqueda de vectores de Apache Lucene
• Croma
• FAISS
• Qdrante
• Vespa
• Búsqueda Gamma
• Tejer
• vectorpg
• MariaDB ^[7]
• Atlas de MongoDB ^[8]
• Milvus ^[9]

Varios de estos utilizan la biblioteca hnswlib ^[10] proporcionada por los autores originales.

Este artículo relacionado con algoritmos o estructuras de datos es un esbozo . Puedes ayudar a Wikipedia expandiéndolo.

• v
• t
• e

Este artículo sobre informática es un esbozo . Puedes ayudar a Wikipedia ampliándolo.

• v
• t
• e