HNSW
An approximate vector index built as a layered graph of links between nearby vectors, searched by walking from a coarse top layer down to a dense bottom one.
In more detail
Malkov and Yashunin published it in 2016, and it is the default index in many vector stores. Three settings matter: m, the links per node; ef construction, how hard the build searches for good links; and ef search, how many candidates a query keeps.
Related terms
- ef search — The HNSW query setting for how many candidate vectors the search keeps while walking the graph; higher finds more true neighbours but runs slower.
- approximate nearest neighbour search — Vector search that skips most comparisons using an index, trading a little recall for much faster queries.
- vector index — A data structure that makes nearest-neighbour search over many vectors fast, usually by giving up exactness.
Taught in
- Vector Indexes And Databases — AI Engineering: LLM Apps, RAG & Agents
References
- Malkov and Yashunin: Hierarchical Navigable Small World graphs (arXiv 1603.09320)
- Qdrant documentation: Indexing (HNSW and payload indexes)