O algoritmo Hierarchical Navigable Small World (HNSW) em tradução livre "Mundo pequeno hierárquico navegável" é uma técnica de busca aproximada de vizinhos mais próximos baseada em grafos, usada em muitos bancos de dados vetoriais.
A busca de vizinhos mais próximos sem um índice envolve o cálculo da distância da consulta a cada ponto no banco de dados, o que é computacionalmente proibitivo para grandes conjuntos de dados. Para dados de alta dimensão, técnicas de busca vetorial exata baseadas em árvore, como a árvore k-d e a árvore R, não apresentam bom desempenho devido à maldição da dimensionalidade. Para remediar isso, buscas aproximadas de k-vizinhos mais próximos foram propostas, como hashing sensível à localidade (LSH) e quantização de produto (PQ), que trocam desempenho por precisão. O grafo HNSW oferece uma busca aproximada de k-vizinhos mais próximos que escala logaritmicamente mesmo em dados de alta dimensão.
É uma extensão do trabalho anterior sobre grafos navegáveis de pequenos mundos, apresentado na conferência Similarity Search and Applications (SISAP) em 2012, com uma navegação hierárquica adicional para encontrar pontos de entrada no grafo principal mais rapidamente. As bibliotecas baseadas em HNSW estão entre as de melhor desempenho no benchmark de vizinhos mais próximos aproximados. Uma técnica relacionada é IVFFlat.
Categoria:Grafos Categoria:Mineração de dados