DataTerminology.comNEW
Also known as: Hierarchical Navigable Small World
A multi-layer small‐world graph index enabling fast, high‐recall approximate nearest neighbor search with logarithmic-like query scaling.
DESCRIPTION
HNSW builds a hierarchy of proximity graphs where upper layers provide coarse routing and lower layers refine nearest neighbors. It exploits small-world properties to achieve efficient greedy search with high recall. Insertions are incremental, making it suitable for dynamic datasets. HNSW often outperforms many alternatives on recall–latency trade-offs, at the cost of higher memory usage. Implementations exist in hnswlib, FAISS, and vector databases like Milvus.
ALTERNATIVE DEFINITIONS
Malkov, Yashunin (arXiv)
We present a new algorithm for approximate nearest neighbor search based on Hierarchical Navigable Small World graphs that provides efficient and robust performance on real-world datasets.
Introduces the hierarchical small-world graph approach.
hnswlib
hnswlib is a C++ library with Python bindings for fast approximate nearest neighbor search using Hierarchical Navigable Small World graphs.
Implementation-focused definition with performance emphasis.
FAISS
IndexHNSW implements HNSW graphs for approximate nearest neighbor search within Faiss.
Integration context within a broader ANN library.
RELATED TERMS
Approximate Nearest Neighbor Search Small-world Network Graph-Based Index HNSWlib FAISS Milvus Vector Index NSG
COMPETING TERMS
KNOWLEDGE AREAS
AI Data Engineering Data Storage & Operations
TARGET AUDIENCE
AI Engineer Data Engineer Software Developer MLOps Engineer
EXTERNAL SOURCES
- arXiv - Original HNSW paper
- hnswlib - Reference implementation repository
- FAISS - FAISS HNSW API reference
TOP QUESTIONS
How does HNSW achieve fast search?
It navigates a hierarchy of small-world graphs, using greedy search from coarse to fine layers to quickly reach close neighbors.
Category: How-to
What are HNSW’s memory trade-offs?
High recall often requires larger neighbor lists and thus higher memory compared to quantization-based indexes.
Category: Trade-off
Is HNSW good for dynamic data?
Yes. It supports incremental insertions, suitable for evolving corpora with frequent updates.
Category: Application
When would IVF-PQ be preferable to HNSW?
When memory constraints dominate and slightly lower recall is acceptable, IVF-PQ can be more efficient.
Category: Comparison
Which libraries implement HNSW?
hnswlib, FAISS, and several vector databases like Milvus provide HNSW indexes.
Category: Overview
What distance metrics work with HNSW?
Commonly inner product, cosine, and Euclidean; support depends on the implementation.
Category: Requirements
How to tune HNSW performance?
Adjust M, efConstruction, and efSearch to balance recall, build time, and query latency.
Category: Best practices
What are risks of misconfiguring HNSW?
Too small efSearch harms recall, while large values inflate latency and memory usage.
Category: Risk
Is HNSW deterministic?
Index building often involves randomness; set seeds and parameters to improve reproducibility.
Category: Limitation