hierarchical navigable small-world graph (HNSW)

Tags: ml, algorithms, approximate nearest neighbor

• https://arxiv.org/abs/1603.09320

• One of the fastest ANN’s

• uses a search index with multiple layers in a proximity graph

  • each node in the graph corresponds to a query vector

• Uses a zooming in approach

  • start at entrypoint at the top layer and recursively perform a greedy search graph traversal until it reaches the local minimum