HNSWLib é uma biblioteca C++ somente de cabeçalho que implementa o algoritmo Hierarchical Navigable Small World (HNSW) para busca aproximada do vizinho mais próximo. A biblioteca é projetada para encontrar itens semelhantes a um item de consulta em grandes coleções de dados vetoriais sem comparar a consulta com cada item individualmente. Ela é comumente usada em sistemas de aprendizado de máquina, aplicações de inteligência artificial e bancos de dados vetoriais onde velocidade e escalabilidade são críticas.
O algoritmo HNSW, que o HNSWLib implementa, armazena vetores em uma estrutura de grafo em múltiplas camadas. Cada vetor se torna um nó, e links o conectam a vetores próximos. As camadas superiores contêm menos nós e atuam como um mapa grosseiro, enquanto a camada inferior contém todos os nós para busca detalhada. Uma busca começa em uma camada superior, segue links em direção a nós mais próximos da consulta e repete o processo em camadas inferiores até identificar um conjunto de prováveis vizinhos mais próximos.
Histórico
O problema da 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 compara a consulta com cada item, o que se torna lento para grandes conjuntos de dados. Métodos exatos que usam árvores espaciais como a k-d tree ou a R-tree perdem eficácia em dados de alta dimensionalidade devido à maldição da dimensionalidade. Métodos aproximados de vizinho mais próximo trocam exatidão por velocidade, retornando itens próximos rapidamente em vez de garantir o mais próximo absoluto.
O HNSW baseia-se em pesquisas sobre redes de mundo pequeno e grafos navegáveis. Em grafos de mundo pequeno, a maioria dos nós se conecta por cadeias curtas de links. O trabalho de Jon Kleinberg sobre navegação em redes de mundo pequeno influenciou pesquisas posteriores sobre a adição de 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 adicionando uma hierarquia de camadas de grafo, o que ajuda a encontrar uma boa região antes da busca detalhada.
Algoritmo
O HNSWLib usa um grafo de proximidade onde vetores próximos são conectados por arestas. O algoritmo se move pelo conjunto de dados usando essas arestas em vez de examinar cada vetor. O grafo é hierárquico: todo vetor aparece na camada inferior, enquanto alguns vetores também aparecem em camadas superiores com menos vetores conforme as camadas ascendem. As camadas superiores permitem movimento de longo alcance, enquanto as camadas inferiores permitem busca detalhada perto de candidatos promissores.
Uma busca típica começa a partir de um ponto de entrada na camada mais alta. A cada passo, o algoritmo examina nós vizinhos e se move para um mais próximo da consulta. Quando nenhum vizinho mais próximo existe nessa camada, ele desce para a próxima camada. Na camada inferior, ele explora um conjunto mais amplo de candidatos e retorna os candidatos mais próximos encontrados. Essa navegação gulosa repetidamente escolhe nós localmente melhores para se aproximar do ponto de consulta.
Construção e parâmetros
O grafo HNSW é construído incrementalmente. Ao inserir um novo vetor, 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. As implementações expõem parâmetros que controlam as compensações entre velocidade, precisão, uso de memória e tempo de construção. Conexões de grafo mais altas melhoram a revocação, mas exigem mais memória. Listas maiores de candidatos de busca melhoram a precisão, mas tornam as consultas mais lentas. Listas maiores de candidatos de construção melhoram a qualidade do grafo, mas tornam a construção do índice mais lenta.
Como o HNSW é aproximado, os resultados podem diferir de buscas exatas. O desempenho prático depende das características do conjunto de dados, da medida de distância, da qualidade 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 dos resultados comuns de benchmark.
Uso em sistemas de busca vetorial
O HNSWLib é usado como um índice em sistemas que armazenam e buscam vetores de alta dimensionalidade, incluindo bancos de dados vetoriais, mecanismos de busca e extensões de bancos de dados. Aplicações típicas incluem busca semântica, sistemas de recomendação, busca de similaridade de imagens e geração aumentada por recuperação. A biblioteca está associada aos autores originais do HNSW e é amplamente adotada em ambientes de produção.
Vários projetos de software implementam ou suportam HNSW. As bibliotecas incluem HNSWLib e FAISS. Sistemas de banco de dados e busca que documentam suporte a HNSW incluem Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant e Redis. Esses sistemas aproveitam o HNSW para busca aproximada rápida em aplicações que vão desde recuperação em modelos de linguagem grandes até pipelines de IA generativa.
Ver também
- Busca aproximada do vizinho mais próximo
- Banco de dados vetorial
- Hash sensível à localidade
- Quantização de produto