HNSW

HNSW, or Hierarchical Navigable Small World graphs, is a graph-based algorithm for approximate nearest neighbor search in high-dimensional vector spaces. It builds a multi-layer, navigable graph where each node represents a data point and edges connect neighboring points. The graph exploits small-world properties to enable fast search for approximate nearest neighbors.

The construction process assigns each data point a random level, with higher levels containing fewer connections. The upper layers form a coarse backbone, guiding search, while the bottom layer provides a dense, local neighborhood structure. To search, the algorithm starts at an entry point on the top level and performs a greedy search to reach close to the query. It then descends through the layers, refining the candidate set at each level until the bottom layer is reached, where a local search yields the final result.

Key parameters control performance and resource use. M is the maximum number of connections per node per layer, shaping memory usage. efConstruction controls the size of the candidate set during index construction, affecting index quality and build time. efSearch governs the breadth of the search during queries, trading recall against latency. Nodes are pruned to maintain the degree bound M, ensuring memory efficiency. The structure also supports dynamic insertion, enabling incremental updates to the index.

Time complexity is data-dependent, but searches typically scale sublinearly with data size and often exhibit near-logarithmic behavior in practice, while memory usage grows roughly with O(N M). The approach tends to offer high recall with lower latency than exact methods on large datasets.

HNSW has become a widely used technique for approximate nearest neighbor search. It is implemented in several libraries, including hnswlib and NMSLIB, with variants in Faiss. It finds applications in search, recommendations, computer vision, and scientific data analysis.