Performing an exact search (k-NN) on a vector database requires comparing the user's query against every single document vector in the system. This 'brute force' approach does not scale. Hierarchical Navigable Small World (HNSW) is the algorithmic engine that powers almost every modern vector database (Pinecone, Weaviate, Qdrant). It builds a multi-layered graph where the bottom layer contains every single vector connected to its nearest neighbors. The higher layers contain progressively fewer vectors with longer links—acting like an express highway system. When a query is made, HNSW starts at the sparse top layer, quickly zooms into the general neighborhood of the query, and then drops down to the dense bottom layer to find the exact nearest neighbors.
How It Works
- Graph Construction: Vectors are inserted into a multi-layered graph. Short connections reside at the bottom (local roads), and long connections reside at the top (highways).
- Routing Phase: A search begins at the top layer. The algorithm traverses the graph to find the node closest to the query vector.
- Descent: Once it can no longer get closer on the top layer, it drops down to the next layer and repeats the process.
- Local Search: At the bottom layer, a localized search occurs among the dense neighborhood to return the final 'Approximate' Nearest Neighbors.
Common Use Cases
- Powering low-latency semantic search in production RAG systems.
- Real-time recommendation engines for e-commerce and streaming platforms.