Hierarchical Navigable Small World

The Hierarchical navigable small world (HNSW) algorithm is a graph-based approximate nearest neighbor search technique used in many vector databases. Nearest neighbor search without an index involves computing the distance from the query to each point in the database, which for large datasets is computationally prohibitive. For high-dimensional data, tree-based exact vector search techniques such as the k-d tree and R-tree do not perform well enough because of the curse of dimensionality. To remedy this, ''approximate'' k-nearest neighbor searches have been proposed, such as locality-sensitive hashing (LSH) and product quantization (PQ) that trade performance for accuracy. The HNSW graph offers an approximate k-nearest neighbor search which scales logarithmically even in high-dimensional data.

It is an extension of the earlier work on navigable small world graphs presented at the Similarity Search and Applications (SISAP) conference in 2012 with an additional hierarchical navigation to find entry points to the main graph faster. HNSW-based libraries are among the best performers in the approximate nearest neighbors benchmark.

A related technique is IVFFlat.

Use in vector databases

HNSW is a key method for approximate nearest neighbor search in high-dimensional vector databases, for example in the context of embeddings from neural networks in large language models. Databases that use HNSW as search index include:

* Apache Lucene Vector Search
* Chroma
* Qdrant
* Vespa
* Vearch Gamma
* Weaviate
* pgvector
* MariaDB
* MongoDB Atlas
* ClickHouse
* Milvus
* DuckDB
* Kuzu
* Cozo

Several of these use either the hnswlib library provided by the original authors, or the FAISS library. libvictor is another high-performance library that implements HNSW and other indexing structures, designed for flexibility and integration in custom vector database solutions.

References

Graphs
Network science
Search algorithms
Database index techniques
Data mining
Machine learning

{{Compu-stub