Skip to main content
Loading

Hierarchical Navigable Small World (HNSW)

Hierarchical Navigable Small World (HNSW) is a popular algorithm for searching across a large vector space. HNSW provides a performant and efficient approach that produces reasonably accurate results by creating unique "neighborhoods" of vectors based on the clustering of your data. This natural clustering means that a proximity search only needs to compare the distance between your search vector and a small subset of the vectors in your vector space. These neighborhoods are used to construct the index.

Parallel index construction

A unique aspect of the AVS system is the approach to constructing the HNSW index in parallel. This is done by constructing batches of neighborhoods before reconciling those updates with the existing index. Each node maintains its own batching queue independently.

image

Index healing

Since updating the HNSW indexes in parallel can result in index inaccuracies, a healing process reconciles index update conflicts. This same process handles vector updates and deletes.

This means that the index may return inaccurate results while related vectors are being updated AVS prioritizes up-to-date data over search accuracy.