HNSW-Index
Definition
An HNSW index organizes data in multiple graph layers for approximate nearest neighbor search.
HNSW uses a hierarchy of neighborhood graphs over subsets of stored elements. The search starts in an upper layer. The approach serves approximate neighbor search and is therefore not equivalent to guaranteed exact search.
Simply explained
Imagine a map with coarse long-distance connections and finer local roads. You first approach an area roughly. The comparison explains the layers, not a guaranteed optimal route.
Why it matters in practice
When selecting a search index, result quality and technical requirements must be evaluated together. A closer examination of the actually found neighbors remains necessary.
Example from business
Possible example: An internal document search tests an HNSW index on vector representations of their released texts.
Limits and pitfalls
- Approximation must not be confused with guaranteed completeness. Good neighbors according to a distance function are also not automatically professionally relevant documents.
Origin & history
Malkov and Yashunin provided the here cited first arXiv version of their hierarchical graph approach in 2016. The abstract describes the layered structure and the search start in the upper level.
Use in mid-sized companies
- A comparison of the index with an exact neighbor search on a small operational test set is conceivable. Deviations should be evaluated based on the search task.
Frequently asked questions
Is HNSW an exact search guarantee?
No. The cited work describes approximate neighbor search.
Are all layers structured the same?
They contain neighborhood graphs for nested subsets of the elements.
Sources
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs · Malkov und Yashunin (2016): Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
Editorially reviewed on: