Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
This paper introduces the HNSW algorithm, which is widely adopted in vector databases and search engines for its efficient and robust performance on high-dimensional data. HNSW is foundational in powering modern vector search systems.
About this tool
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
- Authors: Yu. A. Malkov, D. A. Yashunin
- Category: Research Paper / Survey
- Source: arXiv:1603.09320
- Tags: hnsw, ann, vector-search, research
Description
This paper introduces HNSW (Hierarchical Navigable Small World graphs), a graph-based algorithm for efficient and robust approximate nearest neighbor (ANN) search in high-dimensional spaces. HNSW is widely adopted in vector databases and search engines and is foundational for modern vector search systems.
Features
- Graph-Based ANN Search: HNSW relies entirely on a multi-layer proximity graph structure, eliminating the need for additional coarse search structures.
- Hierarchical Multi-Layer Design: Elements are organized in a hierarchy of proximity graphs (layers), supporting nested subsets of the dataset.
- Randomized Layer Assignment: Each element's highest layer is chosen randomly with an exponentially decaying probability, leading to efficient, scale-separated graph construction.
- Logarithmic Complexity: Starting the search at the upper layers and utilizing scale separation enables logarithmic scaling of search complexity.
- Heuristic Neighbor Selection: Employs a heuristic for selecting neighbors in the proximity graph, improving performance at high recall and with highly clustered data.
- Superior Performance: Demonstrated to outperform previous open-source state-of-the-art vector-only approaches for ANN search in general metric spaces.
- Distributed Implementation: The structural similarity to skip lists allows for straightforward, balanced, distributed implementations.
References
Pricing
N/A (Research paper)
Loading more......
Information
Categories
Tags
Similar Products
6 result(s)BANG is a billion-scale approximate nearest neighbor search system optimized for single GPU execution, enabling high-performance vector search in vector database environments at massive scale.
A scalable system for approximate nearest neighbor search at web-scale, relevant for implementing and understanding vector database infrastructure for high-dimensional data.
An influential paper analyzing and improving approximate nearest neighbor search methods for high-dimensional data, highly relevant for developing and understanding vector databases.
HNSWLIB is a C++ library with Python bindings for fast approximate nearest neighbor search using Hierarchical Navigable Small World (HNSW) graphs, commonly used in vector database backends.
A curated GitHub repository of research papers and technical blogs focused on vector search, approximate nearest neighbor search (ANN Search), and vector databases. This resource serves as a comprehensive directory for foundational and cutting-edge research, making it highly relevant for anyone building or exploring vector database technologies.
SOAR is a set of improved algorithms on top of ScaNN that accelerate vector search by introducing controlled redundancy and multi-cluster assignment, enabling faster approximate nearest neighbor retrieval with smaller indexes in large‑scale vector databases and search systems.