HNSW
A layered proximity-graph index for approximate nearest-neighbor search, designed to trade memory and construction cost for low-latency high-recall retrieval.
Search Structure
HNSW stores vectors in a layered proximity graph. Sparse upper layers provide long navigation steps toward a promising region, while denser lower layers expand local candidates in more detail.
The method performs approximate rather than exhaustive nearest-neighbor search, trading a small amount of exactness for much lower search cost.
Main Parameters
M controls graph connectivity. efConstruction influences candidate exploration during index building, while efSearch controls the search candidate set at query time. Larger values can improve recall but increase memory, build time or query work.
System-Level Boundary
HNSW performance is not only the graph algorithm. Large indexes can consume substantial memory, and filtering, deletion and update behavior depends on the implementation. Parameters therefore need measurement on the real data distribution and target recall.
Related Concepts
Source
- https://arxiv.org/abs/1603.09320
Related technical articles: FAISS Index Architecture for Vector Similarity Search, Artificial Intelligence: Philosophy, Theory and Practice.