Hierarchical navigable small world (HNSW) é um algoritmo para busca aproximada do vizinho mais próximo. Ele é usado para encontrar itens semelhantes a um item de consulta em uma grande coleção, sem comparar a consulta com cada item individualmente. O algoritmo é comumente usado para buscar dados vetoriais, onde itens como documentos, imagens, músicas ou perfis de usuário são representados como listas de números chamadas vetores. Itens com vetores semelhantes são tratados como semelhantes de acordo com o modelo que produziu os vetores, e o HNSW fornece uma maneira de buscar esses vetores rapidamente, especialmente em grandes conjuntos de dados.
O HNSW armazena vetores em um grafo. Cada vetor é um nó, e links o conectam a alguns vetores próximos. O grafo possui várias camadas: as camadas superiores contêm menos nós e funcionam como um mapa aproximado, enquanto a camada inferior contém todos os nós e oferece uma visão mais detalhada. Uma busca começa em uma camada superior, segue links em direção a nós que estão mais próximos da consulta e, em seguida, repete o processo nas camadas inferiores até encontrar um conjunto de prováveis vizinhos mais próximos.
Histórico
O problema de busca do vizinho mais próximo pergunta quais itens em um conjunto de dados estão mais próximos de um item de consulta. Uma busca direta pode comparar a consulta com todos os itens do conjunto, mas isso se torna lento quando o conjunto é grande. Métodos de busca exata baseados em árvores espaciais, como a k-d tree e a R-tree, também podem se tornar menos eficazes para dados de alta dimensionalidade, um problema frequentemente associado à maldição da dimensionalidade.
Métodos aproximados de vizinho mais próximo trocam alguma exatidão por velocidade ou menor uso de recursos. Em vez de sempre garantir o item exato mais próximo, eles tentam retornar itens próximos rapidamente. Outros métodos aproximados incluem hashing sensível à localidade e quantização de produto.
O HNSW baseia-se em pesquisas sobre redes de mundo pequeno e grafos navegáveis. Em um grafo de mundo pequeno, a maioria dos nós pode ser alcançada a partir de outros nós por meio de uma cadeia curta de links. Em um grafo navegável, um procedimento de busca pode usar informações locais para se mover em direção a um alvo. O trabalho de Jon Kleinberg sobre navegação em redes de mundo pequeno é um exemplo importante dessa área de pesquisa. Trabalhos posteriores estudaram maneiras de adicionar links que tornam os grafos mais fáceis de navegar de forma gulosa.
O algoritmo HNSW estende métodos anteriores de mundo pequeno navegável para busca por similaridade, adicionando uma hierarquia de camadas de grafo. Essa hierarquia ajuda o algoritmo a encontrar uma boa região do grafo antes de realizar uma busca mais detalhada na camada inferior.
Algoritmo
O HNSW é baseado em um grafo de proximidade. Nesse grafo, vetores próximos são conectados por arestas. O algoritmo usa essas arestas para se mover pelo conjunto de dados, em vez de escanear cada vetor.
O grafo é hierárquico. Cada vetor aparece na camada inferior. Alguns vetores também são colocados em camadas superiores, com menos vetores aparecendo conforme as camadas sobem. As camadas superiores permitem movimento de longo alcance pelo conjunto de dados, enquanto as camadas inferiores permitem uma busca mais detalhada perto de candidatos promissores.
Uma busca típica procede da seguinte forma:
- A busca começa a partir de um ponto de entrada na camada mais alta.
- Em cada etapa, o algoritmo examina nós vizinhos e se move para um vizinho que está mais próximo da consulta.
- Quando não consegue encontrar um vizinho mais próximo nessa camada, ele desce para a próxima camada.
- Na camada inferior, ele explora um conjunto mais amplo de nós candidatos e retorna os candidatos mais próximos encontrados.
Essa estratégia de busca é frequentemente descrita como navegação gulosa. O algoritmo escolhe repetidamente nós localmente melhores, usando a estrutura do grafo para se aproximar do ponto de consulta.
Construção e parâmetros
O grafo HNSW é construído incrementalmente. Quando um novo vetor é inserido, o algoritmo atribui a ele uma camada máxima, busca nós existentes próximos e conecta o novo nó a vizinhos selecionados em cada camada onde ele aparece.
Implementações geralmente expõem parâmetros que controlam o equilíbrio entre velocidade, precisão, uso de memória e tempo de construção. Um número maior de conexões no grafo pode melhorar a revocação, mas requer mais memória. Uma lista maior de candidatos de busca pode melhorar a precisão, mas torna as consultas mais lentas. Uma lista maior de candidatos de construção pode melhorar a qualidade do grafo, mas torna a construção do índice mais lenta.
Como o HNSW é aproximado, seus resultados nem sempre são idênticos a uma busca exata completa. Seu desempenho prático depende do conjunto de dados, da medida de distância, da implementação e das configurações de parâmetros. Estudos de benchmarking descobriram que bibliotecas baseadas em HNSW são fortes desempenhos entre métodos aproximados de vizinho mais próximo, embora o desempenho no pior caso possa diferir do desempenho em conjuntos de dados de benchmark comuns.
Uso em sistemas de busca vetorial
O HNSW é usado como um índice em sistemas que armazenam e buscam vetores de alta dimensionalidade. Esses sistemas incluem bancos de dados vetoriais, mecanismos de busca e extensões de banco de dados. Usos típicos incluem busca semântica, sistemas de recomendação, busca por similaridade de imagens e geração aumentada por recuperação, que é frequentemente aplicada em pipelines de IA generativa e modelos de linguagem grandes.
Vários projetos de software implementam ou suportam o HNSW. Bibliotecas incluem hnswlib, que é associada aos autores originais do HNSW, e FAISS. Sistemas de banco de dados e busca que documentam suporte ao HNSW incluem Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant e Redis. Essas ferramentas são comumente implantadas em plataformas de nuvem como Amazon Web Services, Microsoft Azure e Google Cloud para cargas de trabalho de produção em aprendizado de máquina.
Ver também
- Busca aproximada do vizinho mais próximo
- Banco de dados vetorial
- Hashing sensível à localidade
- Quantização de produto