# Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

**Authors:** Yu. A. Malkov, D. A. Yashunin  
**arXiv:** [1603.09320](https://arxiv.org/abs/1603.09320)  
**Date:** 2016-03-30  
**Summary page:** https://www.summarizepaper.com/en/paper/1603.09320v1/

## Key points

- Introduces a new algorithm called Hierarchical Navigable Small World (HNSW) for approximate nearest neighbor search
- HNSW is a fully graph-based approach using navigable small world graphs
- Constructs a layered structure of hierarchical sets of proximity graphs
- Maximum layer randomly selected using an exponentially decaying probability distribution
- Starting the search from the upper layer and utilizing scale separation improves performance and allows for logarithmic complexity scaling
- Simple heuristic employed to select proximity graph neighbors, improving performance at high recall and in cases of highly clustered data
- Outperforms previous state-of-the-art vector-only approaches such as FLANN, FALCONN, and Annoy in performance evaluation on various datasets
- Similarity to a well-known 1D skip list structure enables efficient and balanced distributed implementation
- Provides an efficient and robust solution for approximate nearest neighbor search in metric spaces without reliance on additional search structures

## Summary

, , , , 

The paper introduces a new algorithm called Hierarchical Navigable Small World (HNSW) for the approximate nearest neighbor search. HNSW is a fully graph-based approach that utilizes navigable small world graphs, allowing for simple insertion, deletion, and K-nearest neighbor queries. Unlike other proximity graph techniques that rely on additional search structures like kd-trees or Cartesian concatenation, HNSW constructs a layered structure consisting of hierarchical sets of proximity graphs (layers) for nested subsets of the stored elements. The maximum layer in which an element is present is randomly selected using an exponentially decaying probability distribution. This ensures that the resulting graphs are similar to Navigable Small World (NSW) structures while also having links separated by their characteristic distance scales. By starting the search from the upper layer instead of random seeds and utilizing scale separation, HNSW achieves better performance compared to NSW and allows for logarithmic complexity scaling. Additionally, a simple heuristic is employed to select proximity graph neighbors, further improving performance at high recall and in cases of highly clustered data. The proposed algorithm outperforms previous state-of-the-art vector-only approaches such as FLANN, FALCONN, and Annoy in terms of performance evaluation on various datasets. Its similarity to a well-known 1D skip list structure enables straightforward efficient and balanced distributed implementation. In summary, HNSW presents an efficient and robust solution for approximate nearest neighbor search in metric spaces. Its fully graph-based approach without reliance on additional search structures makes it versatile and applicable to various domains.