Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

Understand

We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW).

• The proposed solution is fully graph-based, without any need for additional search structures, which are typically used at the coarse search stage of the most proximity graph techniques.
• Hierarchical NSW incrementally builds a multi-layer structure consisting from hierarchical set of proximity graphs (layers) for nested subsets of the stored elements.
• The maximum layer in which an element is present is selected randomly with an exponentially decaying probability distribution.