A Visual Guide to the Hierarchical Navigable Small World Algorithm
A Visual Guide to the Hierarchical Navigable Small World Algorithm<br>May 26, 2024<br>similarity-searchinteractive
This post is part two in this series about similarity search. To read the first part of this series, check out A Visual Guide to Vector Search and K-Nearest Neighbors.
░ NOTE<br>░ The text, code examples, and the visualizations in this article are works-in-progress.
We’ll dive into the inner workings of an approximate nearest neighbor (ANN) algorithm called Hierarchical Navigable Small Worlds (HNSW). HNSW is commonly used algorithm in vector databases to enhance the speed of similarity search. Throughout this article, we’ll use interactive visuals and demos to demonstrate the fundamental concepts of the HNSW algorithm.<br>Introduction to HNSW<br>Hierarchical NSW is one of several approximate nearest neighbor (ANN) algorithms developed to speed up similarity search. Initially proposed by Yu. A. Malkov and<br>D. A. Yashunin in 2016, HNSW builds on the concept of two other algorithms:
Navigable Small World (NSW) graphs - a type of graph that allows for fast approximate nearest neighbor search
Skip Lists - a data structure allowing fast insertion and search via a multi-layer linked list structure.
Combining both, HNSW generates a multi-layer NSW graph that enables a logarithmic time complexity for approximate nearest neighbor search. Its performance was significantly better compared to previous state-of-the-art ANN algorithms.<br>Mastering the concepts of skip lists and navigable small world data structures is a prerequisite for comprehending the inner workings of HNSW. This understanding will serve as a solid foundation for our exploration of HNSW.<br>Skip Lists<br>An example below demonstrates searching for a node valued 5 in a Skip List.
Skip Lists enhance singly linked lists by introducing multiple layers, with each node having a randomly assigned height. Unlike traditional linked lists where each node points to the next, Skip List nodes have multiple pointers for different layers. The node’s height, indicating its layer stack, ranges from a dense, fully connected, bottom layer to a sparse top layer.<br>This multi-layered approach allows for efficient element “skipping” during searches<br>Node heights in a skip list are probabilistically assigned on insertion of a node, with each additional layer usually having a halved chance of inclusion, with the probability p being set to a default value of 0.5. This means a node’s height is akin to flipping a coin: a head adds another layer, while a tail stops the process, making taller nodes less common as layers increase.<br>This results in a structure with multiple levels, with the top level containing the sparsest amount of nodes and the bottom level being the most dense.<br>The lowest level contains all the elements like a regular linked list, except ordered. Inserts and searches on a skip list have an average time complexity of O(log n), compared to O(n) linear time for a linked list.<br>This unique structure enables the “skipping” of elements during search, which is the property that gives skip lists performance advantages over traditional linked lists and a similar performance profile to balanced trees.<br>Play with the interactive demo below to see how this skipping works in practice to speed up search:
The animation above shows a Skip List search for a node with value 5.<br>The search starts at the top level, comparing the target value with adjacent nodes.<br>If the target matches or is less than the next node, the search moves to that node.<br>Otherwise, if the next node’s value is greater or it’s the end of the list, the search drops to the next lower level.<br>This process repeats until the desired node is found at the lowest level.<br>This method is significantly faster than a standard linear search in a linked list. The Hierarchical Navigable Small World (HNSW) algorithm applies a similar concept to gain performance improvements during search and insertion, but using a graph instead of a linked list.<br>Navigation Small World (NSW) Graphs<br>Navigable Small World (NSW) provides a method for constructing and traversing a graph that facilitates fast approximate nearest neighbor search. A greedy search of this graph has a polylogarithmic time complexity of O(logᵏn), which can be faster than the linear time complexity of a naive KNN search.<br>The NSW graph employs a strategy known as greedy routing during search and insertion. The search process in NSW commences by selecting an entry point.<br>Typically the entry point is the first node ever inserted. Early nodes typically remain a starting point because long-range edges are likely to be created during the initial graph construction phase. These edges play a vital role in graph navigation. They serve as bridges between network hubs, maintaining overall graph connectivity and enabling logarithmic scaling of the number of hops during greedy routing.<br>The algorithm then takes the set of all of...