Improving approximate nearest neighbor search in HNSW graphs with data clustering

Abstract

Exhaustive strategies for search and information retrieval tasks over vector databases do not meet the runtime efficiency expectations of modern applications. Approximate Near- est Neighbor Search (ANNS) algorithms use different indexing and searching techniques to perform an approximate similarity search, drastically reducing runtime in exchange for the lack of an optimality guarantee. A usual strategy involves the construction of a Proximity Graph (PG), which can be nav- igated through a greedy search. The state-of-the-art Hierarchical Navigable Small World (HNSW) algorithm improves this strategy, organizing data in a single-entry-point hier- archical graph to reduce the number of hops during search. However, the algorithm for building the hierarchy relies on a pseudo-randomly chosen distribution of data, which does not account dataset’s geometric properties. Furthermore, the single-entry-point strat- egy blocks the possibility of exploring the graph more than once, limiting results diversity. In this work, we propose two novel approaches to increase the robustness of the hier- archical graph approach: (i) HCNSW, a cluster-based approach to construct the search graph hierarchy, and (ii) iHNSW, an iterative search approach that uses data clusters to bring more diverse results. This iterative approach can be used with other data indexing strategies or leverage the same clusters constructed by HCNSW, resulting in iHCNSW. We implemented and empirically tested our two approaches over four well-known image- sourced vector datasets: SIFT1M, GIST, MNIST and Fashion-MNIST. These empirical experiments showed that our approaches can lead to interesting trade-offs over search efficiency and recall metrics. While our HCNSW index consistently drops query latency metrics in comparison to HNSW without significantly compromising (or even improving) recall, our iterative indexes (iHNSW and iHCNSW) can further add to recall metrics by extending the search process. Additionally, we implemented our HCNSW approach on top of the NMSLIB library to test it against a fast and complete HNSW implementation. Our tests show that our solution can not only improve overall performance stability, but can also do it consistently. However, our approaches add more complexity to the indexing process and also limits its capacity of progressively inserting new data.

Estratégias exaustivas para tarefas de busca e recuperação de informações em bancos de dados vetoriais não atendem às expectativas de eficiência de tempo de execução de aplicações modernas. Algoritmos de ANNS (Approximate Nearest Neighbor Search) usam diferentes técnicas de indexação e busca para executar uma busca de similaridade aproximada, reduzindo drasticamente o tempo de execução em troca da falta de garantia de otimalidade. Uma estratégia comum envolve a construção de um PG (Proximity Graph), que pode ser explorado utilizando uma busca gulosa. O algoritmo estado-da-arte HNSW (Hierarchical Navigable Small World) aprimora essa estratégia, organizando os dados em um grafo hi- erárquico de ponto de entrada único para reduzir o número de saltos durante a busca. No entanto, o algoritmo de construção da hierarquia depende de uma distribuição de dados escolhida pseudo aleatoriamente, que não leva em conta as propriedades geométricas do conjunto de dados. Além disso, a estratégia de ponto de entrada único impede a exploração do grafo mais de uma vez, limitando a variedade dos resultados. Neste trabalho, propomos duas novas abordagens para aumentar a robustez da abordagem de grafo hierárquico: (i) HCNSW, uma abordagem baseada em clustering para construir a hierarquia do grafo de busca, e (ii) iHNSW, uma abordagem de busca iterativa que utiliza clustering de dados para trazer resultados mais diversos. Essa abordagem iterativa pode ser utilizada com outras estratégias de indexação de dados ou aproveitar os mesmos clusters construídos pelo algoritmo HCNSW, resultando no índice iHCNSW. Implementamos e testamos empiricamente nossas duas abordagens em quatro conjuntos de dados vetoriais de imagens bem conhecidos: SIFT1M, GIST, MNIST e Fashion- MNIST. Esses experimentos empíricos mostraram que nossas abordagens levam a trade-offs interessantes entre a latência de busca e métricas de recall. Enquanto nosso índice HCNSW reduz consistentemente as métricas de latência de consulta em comparação ao HNSW sem comprometer significativamente (ou até mesmo melhorando) o recall, nossos índices iterativos (iHNSW e iHCNSW) podem adicionar ainda mais às métricas de recall ao estender o processo de busca. Além disso, implementamos nossa abordagem HCNSW sobre a biblioteca NMSLIB, para testá-la em uma implementação HNSW rápida e completa. Nossos testes mostram que nossa solução pode não apenas melhorar a estabilidade geral do desempenho, mas também pode fazê-lo de forma consistente. Entretanto, nossas abordagens adicionam mais complexidade ao processo de indexação e também limitam sua capacidade de inserir progressivamente novos dados.