Conceitos
Busca aproximada de vizinhos com grafos hierárquicos (HNSW)
Intuição
Imagine que você precisa achar, entre milhões de itens, os mais parecidos com um item que tem em mãos, e comparar com todos um por um levaria tempo demais. Um atalho é aceitar uma resposta quase perfeita: você viaja de avião até a região certa, depois segue de carro até o bairro e só então anda a pé, olhando poucos candidatos em cada etapa. Em vez de garantir o melhor resultado sempre, o método troca um pouco de exatidão por muita velocidade, e você escolhe quanto de esforço extra quer gastar para errar menos.
Como funciona
A busca dos K vizinhos mais próximos exige uma função de distância, e a abordagem ingênua compara a consulta com todos os elementos, com custo linear no tamanho da base; a busca aproximada aceita alguns erros, medidos pelo recall (a razão entre os vizinhos verdadeiros encontrados e K). Em grafos de proximidade, a busca é um roteamento guloso: parte de um ponto de entrada e salta, a cada passo, para o vizinho do nó atual mais próximo da consulta. O HNSW distribui os vínculos em camadas: cada elemento sorteia um nível máximo com probabilidade que decai exponencialmente, então as camadas altas guardam subconjuntos cada vez menores e têm os vínculos mais longos, e o número esperado de camadas cresce de forma logarítmica. A consulta faz roteamento guloso na camada mais alta até um mínimo local, desce uma camada reiniciando desse elemento e repete até a camada zero, onde estão todos os elementos, de modo semelhante a uma skip list probabilística. Na inserção, o novo elemento sorteia seu nível, desce com busca gulosa simples pelas camadas acima dele e, a partir do seu nível, procura e liga vizinhos em cada camada; como o sorteio de níveis já traz a aleatoriedade, não é preciso embaralhar os elementos, e a indexação é incremental. Os parâmetros têm papéis distintos: M é o número de conexões na inserção e é proporcional à memória; mL normaliza a geração dos níveis (1/ln(M) é a sugestão do paper); Mmax0 limita as conexões na camada zero (a sugestão é 2·M); efConstruction é o tamanho da lista de candidatos na construção; e ef é o tamanho da lista de candidatos na consulta. Uma heurística de seleção de vizinhos que escolhe conexões diversas, em vez de só as mais próximas, teve desempenho igual ou maior em todos os casos testados.
Na prática
Na consulta, o botão é o ef: uma lista maior examina mais vizinhança e eleva o recall, ao custo de mais cálculos de distância e mais tempo por consulta. Na construção, efConstruction troca tempo de indexação por qualidade (para 10 milhões de vetores SIFT, efConstruction=100 produziu um índice de qualidade razoável em cerca de 3 minutos no servidor do experimento, e valores maiores trouxeram pouco ganho com tempo bem maior), e M, com faixa razoável de 5 a 48, define a memória: com M entre 6 e 48 e links de 4 bytes, o paper estima cerca de 60 a 450 bytes por objeto, sem contar os dados. Nas simulações do paper, M menor tende a servir melhor para recall baixo ou dados de baixa dimensão, e M maior para recall alto ou dados de alta dimensão. Em comparações com uma thread, o HNSW superou com folga NSW, FLANN, Annoy, VP-tree e FALCONN em SIFT, GloVe, DEEP e CoPhIR, mas em dados de baixa dimensão (d=4) foi só um pouco mais rápido que o Annoy em recall alto.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.