Hnsw (hierarchical Navigable Small World)

HNSW (Hierarchical Navigable Small World) is a graph-based algorithm for fast approximate nearest neighbor search. Core idea: Build multi-layer graph where higher layers have fewer nodes (long-range connections), lower layers are denser (local connections). Search from top, greedy descent. Algorithm: Start at top layer entry point, greedily move toward query, drop to lower layer, repeat until bottom layer. Returns approximate nearest neighbors. Construction: Insert nodes bottom-up, connect to closest neighbors at each layer. Probabilistic layer assignment. Parameters: M: Max connections per node. Higher = more accurate, more memory. ef_construction: Build-time search depth. ef_search: Query-time search depth (accuracy/speed trade-off). Advantages: Excellent recall/speed trade-off, no training required, supports incremental inserts. Disadvantages: High memory (stores graph), slower construction than some alternatives. Comparison: Generally outperforms IVF on accuracy at same speed. Standard choice for many vector databases. Use by: Pinecone, Weaviate, Qdrant, pgvector, Milvus all offer HNSW. Best for: When accuracy matters and memory is available. Most common choice for production similarity search.