Algorithms also: Hierarchical Navigable Small World

HNSW

Multi-layer graph index for approximate nearest-neighbour search.

In plain terms

Malkov & Yashunin, 2016. Default ANN index in pgvector, Qdrant, Weaviate, Milvus. State-of-the-art recall; high memory cost.

Origin

Yury Malkov and Dmitry Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs," 2016. Combined the small-world graph idea (Watts & Strogatz, 1998) with hierarchical layers. Took five years to displace LSH and IVF as the default ANN index.

Where it shows up in production

pgvector PostgreSQL extension — HNSW is the default high-recall index since v0.5 (2023).
Qdrant, Weaviate, Milvus All three vector databases use HNSW by default; differentiate on filtering, sharding, and operations.
OpenAI embeddings The retrieval examples in their cookbook use HNSW via Pinecone/Weaviate/Qdrant.

On Semicolony

Simulator vector embedding Paper papers

Sources & further reading

Found this useful?