Hierarchical Navigable small world

Was looking at some stuff about how postgresql stores vectors, and found that pgvector indexing supports HNSW and IVF, so I spent some time digging into them.

Navigable small world

What is NSW? it’s just a graph containing nodes(vectors) and each node is connected to K nodes that are closest to itself. The purpose is to make vector similarity search efficient.
To do a query (finding the top k closest nodes):

1. Pick an entry node and put it in both the Candidate Pool(min-heap, length efSearch) and Result List(max-heap, length K).
2. Pop the closest node from the Candidate Pool.
3. Check unvisited neighbors of the popped node: Calculate distance(usually cosin similarity) from the query to each unvisited neighbor.
4. Update lists: Add valid neighbors to both the Candidate queue and Result queue (if a neighbor is better than the worst item in pool at efSearch, drop the worst item).
5. Repeat or Terminate: Repeat steps 2–4 until a terminating rule triggers:

• Distance Rule: The closest candidate in the pool is farther away than the worst (farthest) item in your Result List.
• Graph Exhaustion Rule: The Candidate Pool is empty

Hierarchical Navigable small world (HNSW)

It’s basically a combination navigable small world (NSW) and skip linked list concept.

The Ground level: the lowest level, all nodes are here
Top levels: higher levels contain less nodes, and each level definitely contains all the nodes that are in one level higher.

To do a query:

1. starting at a node in the top level
2. Check neighbors and hop to whichever is closest to the query vector.
3. When no layer neighbor gets closer, drop straight down to the same node on the next level.
4. Repeat until reaches ground level
5. At ground level just do the usual Navigable small world query

Hierarchy’s sole purpose is to find the entry node for the gound level’s NSW search.

Time Complexity: O(log N)
Why: similar to a Skip-List. Higher levels can help you reach to the dest sooner.
Space Complexity: O(efSearch+K), efSearch is the size of the priority queues

How to build the graph

Insert vectors one by one
For each new vector:

1. Decide which is the max level the new by rolling a dice (100% only on ground level, 10% reaches ground+1 level, 1%…).
2. do a usual HNSW search until the max level the vector should live on
3. do a NSW search on this level to find K top closest nodes to connect.
4. Trim the edges if some nodes have too many edges
5. drop then repeat 3 and 4 to the ground floor

Insertion / Index Build Time Complexity for N nodes: O(N logN)

Why: Inserting a vector requires running a search at each level it lives on (O(\log N) search steps) plus connecting to K neighbors K operations. K is a predefined constant, so the operation is O(1).
The number of levels is also constant.

Space Complexity during Build:
O(efConstruction+K), also the size of the queue

Summary

I’ll do IVF in the next article ha