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)
At a scale of 1 million vectors, PRISM achieves 99% recall and 15 milliseconds median latency on a 2GB c8g.medium; HNSW on a 4GB c8g.large is 392 milliseconds, with building taking about 21.7 hours and exhibiting memory thrashing.
Official benchmarks show that at a scale of 100 million vectors, PRISM's median latency is 6 milliseconds, while pgvector's HNSW failed to complete building on the same machine.
OpenAI's text-embedding-3-large returns 3072-dimensional vectors by default, while pgvector's HNSW can index halfvec up to 4000 dimensions.
Increasing HNSW's m and ef_construction can improve recall, but significantly increases build time and memory usage.
pgvector provides two index types, IVFFlat and HNSW, respectively aimed at different recall and speed trade-off scenarios.
HNSW uses m to control the number of neighbors each node keeps in the graph (default 16), ef_construction determines the candidate queue size during construction (default 64), and ef_search controls the search breadth during queries.
According to benchmark data provided by the project, Pg_vectorsearch surpasses pgvector's IVFFlat and HNSW in query throughput.
For write-intensive applications, HNSW is often not an ideal choice, because its maintenance cost under frequently updated workloads is significant.
The core trade-off of ANN indexes (such as HNSW, IVF-PQ) lies in the triangular relationship among recall, memory and build time.
ANN indexes (especially graph-structured HNSW) are difficult to delete from in place efficiently, so a compromise of 'soft delete + periodic merge' is usually adopted.
35 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 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%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%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%UnverifiedThe HNSW algorithm enables approximate nearest-neighbor search over hundred-million-scale vectors to complete within 10 milliseconds with a recall rate of over 98%, and is the standard index algorithm in mainstream vector databases.
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%UnverifiedThe vector database index algorithms HNSW (graph structure) and IVF (clustering structure) present different engineering trade-offs between retrieval speed and recall rate
60%UnverifiedHNSW (Hierarchical Navigable Small World) builds a multi-layer graph structure with a query time complexity of approximately O(log n), and is the default index for mainstream vector libraries such as Qdrant and Weaviate
60%UnverifiedDuring retrieval, approximate nearest neighbor algorithms (ANN, such as HNSW and IVF) complete similarity searches at the millisecond level, with commonly used metrics including cosine similarity and Euclidean distance.
60%UnverifiedMainstream vector databases such as Pinecone, Weaviate, Qdrant, and pgvector generally adopt the HNSW approximate nearest neighbor indexing algorithm at their core.
60%