Hierarchical navigable small world

The Hierarchical navigable small world (HNSW) algorithm is a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a>-based <a href="/facts/Nearest_neighbor_search/R6QTyAph">approximate nearest neighbor</a> search technique used in many <a href="/facts/Vector_database/aKotamhB">vector databases</a>. 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 <a href="/facts/K-d_tree/XuhcfKKq">k-d tree</a> and <a href="/facts/R-tree/9X5AQWln">R-tree</a> do not perform well enough because of the <a href="/facts/Curse_of_dimensionality/dk7SnY6L">curse of dimensionality</a>. To remedy this, approximate k-nearest neighbor searches have been proposed, such as <a href="/facts/Locality-sensitive_hashing/hj8UllQG">locality-sensitive hashing</a> (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 <a href="/facts/Small_world_graph/dALPpt9m">small world graphs</a> 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.

Hierarchical navigable small world open-in-new

Hierarchical navigable small world