stringtranslate.com

Pequeño mundo navegable jerárquico

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]

Uso en bases de datos vectoriales

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:

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

Referencias

  1. ^ Malkov, Yu A.; Yashunin, DA (2016). "Búsqueda eficiente y robusta de vecino más cercano aproximado mediante gráficos de mundo pequeño navegables jerárquicos". arXiv : 1603.09320 [cs.DS].
  2. ^ ab Malkov, Yury A; Yashunin, Dmitry A (1 de abril de 2020). "Búsqueda eficiente y robusta de vecino más cercano aproximado utilizando gráficos de mundo pequeño navegables jerárquicos". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 42 (4): 824–836. arXiv : 1603.09320 . doi :10.1109/TPAMI.2018.2889473. PMID  30602420.
  3. ^ Malkov, Yury; Ponomarenko, Alexander; Logvinov, Andrey; Krylov, Vladimir (2012). "Algoritmo distribuido escalable para el problema de búsqueda aproximada del vecino más próximo en espacios métricos generales de alta dimensión". En Navarro, Gonzalo; Pestov, Vladimir (eds.). Búsqueda de similitud y aplicaciones . Apuntes de clase en informática. Vol. 7404. Berlín, Heidelberg: Springer. págs. 132–147. doi :10.1007/978-3-642-32153-5_10. ISBN 978-3-642-32153-5.
  4. ^ Aumüller, Martin; Bernhardsson, Erik; Faithfull, Alexander (2017). "ANN-Benchmarks: una herramienta de evaluación comparativa para algoritmos de vecino más cercano aproximado". En Beecks, Christian; Borutta, Felix; Kröger, Peer; Seidl, Thomas (eds.). Búsqueda de similitud y aplicaciones . Apuntes de clase en informática. Vol. 10609. Cham: Springer International Publishing. págs. 34–49. arXiv : 1807.05614 . doi :10.1007/978-3-319-68474-1_3. ISBN . 978-3-319-68474-1.
  5. ^ Aumüller, Martin; Bernhardsson, Erik; Faithfull, Alexander (2020). "ANN-Benchmarks: una herramienta de evaluación comparativa para algoritmos de vecino más cercano aproximado". Sistemas de información . 87 : 101374. arXiv : 1807.05614 . doi :10.1016/j.is.2019.02.006.
  6. ^ "ANN-Benchmarks". ann-benchmarks.com . Consultado el 19 de marzo de 2024 .
  7. ^ "Vector MariaDB". MariaDB.org . Consultado el 30 de julio de 2024 .
  8. ^ "Búsqueda de vectores en MongoDB Atlas". mongodb.com . Consultado el 17 de septiembre de 2024 .
  9. ^ nmslib/hnswlib, nmslib, 18 de marzo de 2024 , consultado el 19 de marzo de 2024


  • v
  • t
  • e
  • v
  • t
  • e