HNSW
HNSW (Hierarchical Navigable Small World) is an approximate nearest neighbor search algorithm for high-dimensional vector spaces, constructing its index on a multi-layer navigable small-world graph structure. The algorithm performs greedy routing searches across layers at different levels of granularity, achieving logarithmic query time complexity. It maintains high recall rates while significantly reducing search latency, and is widely used in vector databases and semantic retrieval systems.
Core Facts
Vector databases (such as ChromaDB, Milvus, and Pinecone) use indexing algorithms such as HNSW and IVF to achieve millisecond-level retrieval among millions or even hundreds of millions of vectors.
向量数据库的核心操作是近似最近邻搜索（ANN），通过HNSW、IVF等索引算法将相似度计算加速到毫秒级响应
Mainstream ANN search implementations include HNSW and IVF, which reduce retrieval time complexity from linear to logarithmic by constructing index structures.
Timeline (last 90 days)
HNSW constructs a multi-layer navigable small-world graph and, at query time, searches downward layer by layer from the coarse-grained upper layers, achieving logarithmic retrieval complexity.
HNSW's advantage lies in high recall and low latency, but the cost is that each vector node must persist a complete high-dimensional embedding, and the graph structure itself must also store adjacency relationships.
According to a report by MarkTechPost, LEANN achieves accuracy comparable to HNSW at 90% recall, with memory usage of 4 GB versus 188 GB.
In practice, vector retrieval often uses approximate nearest neighbor algorithms such as HNSW and IVF to trade off between recall and speed, rather than brute-force computing all vectors.
pgvector's default HNSW settings cause insert stalls of more than 2 seconds during batch memory writes.
The HNSW index locks the table during batch inserts, causing write stalls of more than 5 seconds; the solution is to write in batches with INSERT ... ON CONFLICT DO NOTHING and a 50ms debounce window.
In pgvector's HNSW index, the parameter m is the number of neighbor edges kept per node, and ef_construction is the size of the candidate queue during construction; together they determine the recall-latency trade-off at query time.
In pgvector's HNSW index, setting m to 16 and ef_construction to 64 achieves a p99 latency of 12ms under 500 concurrent inserts.
Approximate nearest neighbor search (ANN) uses algorithms such as HNSW or IVF, trading a small loss in recall for millisecond-level response, returning the semantically nearest candidate set rather than the factually most relevant documents.
ANN builds special index structures (such as HNSW's hierarchical navigable small world graph, IVF's inverted clustering, and PQ's product quantization compression) to sacrifice a small amount of recall accuracy in exchange for order-of-magnitude speedups.
40 more timeline events
All Facts (20)
Vector databases (such as ChromaDB, Milvus, and Pinecone) use indexing algorithms such as HNSW and IVF to achieve millisecond-level retrieval among millions or even hundreds of millions of vectors.
80%Verified向量数据库的核心操作是近似最近邻搜索（ANN），通过HNSW、IVF等索引算法将相似度计算加速到毫秒级响应
80%VerifiedMainstream ANN search implementations include HNSW and IVF, which reduce retrieval time complexity from linear to logarithmic by constructing index structures.
80%VerifiedThe vector database index algorithms HNSW (graph structure) and IVF (clustering structure) present different engineering trade-offs between retrieval speed and recall rate
75%VerifiedThe HNSW algorithm was proposed by Yury Malkov and others in 2016, reducing search complexity from O(n) to O(log n) through a multi-layer graph structure.
75%Verifiedpgvector is an open-source extension for PostgreSQL that natively adds vector data types and similarity search capabilities to the relational database, supporting both exact nearest-neighbor and approximate nearest-neighbor (HNSW, IVFFlat index) retrieval modes.
70%VerifiedVector databases convert text into high-dimensional vectors typically of 768 to 3072 dimensions and use ANN algorithms for retrieval, with mainstream ANN algorithms including HNSW and IVF-PQ.
70%VerifiedThe HNSW algorithm achieves millisecond-level retrieval among billion-scale vectors by constructing a multi-layer graph index while maintaining a recall rate of over 95%.
65%VerifiedHNSW (Hierarchical Navigable Small World graph) is the most mainstream ANN solution in the industry, reducing query complexity to O(log N).
65%VerifiedApproximate nearest neighbor (ANN) algorithms such as HNSW and IVF achieve order-of-magnitude speed improvements by sacrificing a small amount of precision.
65%VerifiedVector databases typically employ approximate nearest neighbor algorithms such as HNSW or IVF at their core, with retrieval latency generally below 10 milliseconds.
65%VerifiedThe HNSW algorithm achieves hierarchical search by constructing a multi-layer graph structure, approximately reducing the exponential complexity of exact nearest-neighbor search to logarithmic complexity, making it the most mainstream index structure in current vector databases.
65%VerifiedText is encoded by an Embedding model into floating-point vectors of 768 to 3072 dimensions, stored in a vector database, and similarity retrieval is completed at millisecond speed via approximate nearest neighbor algorithms (HNSW, IVF, etc.).
65%VerifiedThe RAG mechanism relies on the approximate nearest neighbor (ANN) search capability of vector databases (such as Pinecone, Weaviate, and Milvus) to achieve millisecond-level retrieval.
65%VerifiedMilvus adopts a storage-compute separation architecture and supports multiple vector indexing algorithms including HNSW, IVF_FLAT, and DiskANN.
65%UnverifiedPinecone、Milvus、Weaviate等主流向量数据库均采用HNSW作为核心索引算法
85%Partially VerifiedHNSW (Hierarchical Navigable Small World graph) is an approximate nearest neighbor search algorithm proposed by Russian scholar Yuri Malkov and others in 2016.
65%UnverifiedVector stores locate semantically similar document chunks in high-dimensional space through approximate nearest neighbor algorithms such as HNSW (Hierarchical Navigable Small World graphs) or IVF (Inverted File Index).
60%UnverifiedVector databases typically rely on approximate nearest neighbor algorithms (ANN) at their core, such as HNSW and IVF.
60%UnverifiedThe Pinecone vector database uses the HNSW (Hierarchical Navigable Small World) graph algorithm for approximate nearest neighbor search.
60%