How do vector databases do approximate nearest neighbor search — like what is HNSW actually doing?

To understand Approximate Nearest Neighbor (ANN) search, it helps to first understand the problem: in high-dimensional spaces, finding the exact nearest neighbor is computationally expensive because you effectively have to compare your query against every single data point (a "brute force" linear scan).

ANN trades a tiny bit of accuracy for massive gains in speed by using clever data structures to ignore points that are obviously far away.

HNSW (Hierarchical Navigable Small World)

HNSW is currently the "gold standard" for speed and performance. To understand how it works, imagine a multi-layered social network:

1. The "Small World" Graph (The Base Layer) At its heart, HNSW creates a graph where data points are nodes, and edges represent proximity. If point A is close to point B, they are connected. To find a neighbor, you start at a random point and "hop" through the graph to closer neighbors until you reach the destination. This is efficient because "small world" networks allow you to traverse from any point to any other point in very few steps (the "six degrees of separation" principle).

2. The Hierarchical Layers HNSW builds a pyramid of these graphs:

• The Top Layers: These are sparse, containing only a few "hub" nodes. You use these for "long-distance travel" across the dataset to get into the general neighborhood of your query.
• The Bottom Layers: These are dense, containing all the data points. Once you’ve arrived in the right neighborhood via the top layers, you drop down to the bottom layer to perform a fine-grained search among the local points.

The Process:

1. Enter: You start at the top-most layer at a pre-defined entry point.
2. Greedy Search: You look at the neighbors of your current node. If one is closer to your target query than your current node, you jump to it. You repeat this until you can no longer find a closer neighbor.
3. Drop Down: Once you reach a local minimum at the current layer, you move down to the next, denser layer and repeat the greedy search starting from your current position.
4. Result: When you finish the greedy search on the bottom-most layer, the resulting node is your approximate nearest neighbor.

Other common ANN approaches

While HNSW is a graph-based method, other databases might use different strategies:

• Inverted File Index (IVF): This works like a library catalog. You cluster your data into "buckets" (Voronoi cells) based on a central point. During a search, you only look inside the bucket that is closest to your query, ignoring the rest of the database entirely.
• Product Quantization (PQ): This is a compression technique. It breaks long vectors into smaller sub-vectors and replaces them with a "code" (a compact approximation). It allows the database to store huge amounts of data in RAM and perform calculations using look-up tables instead of expensive floating-point math.

Most modern vector databases (like Milvus, Pinecone, or Weaviate) use a combination of these—typically HNSW for the graph structure and PQ for compression—to balance lightning-fast retrieval with manageable memory usage.