Approximate Neighbours

Approximate Neighbours

Step 1 of 9

comparesall of them

Exact search compares the query with every stored vector. At a billion vectors that is the whole cost.

The Idea

Exact search compares the query with every stored vector. A graph index instead links each vector to a few neighbours, enters at one node, and repeatedly hops to whichever neighbour is closer. Layers of increasingly sparse long-range links let it cross the space in a handful of hops.

Real-World Example

Finding a house in a strange city by asking at each corner which way is closer, rather than knocking on every door. You arrive fast; occasionally you stop one street early.

The Tradeoff

You trade recall for speed, and the dial is explicit: a wider search keeps more candidates alive, finds more true neighbours, and costs more. Building the graph is slow and memory-hungry, deletes leave dangling links, and a freshly inserted vector is invisible until the index takes it.

Your turn

Put the steps in the right order.

1. 1Hop to whichever linked neighbour is closer to the query↑↓
2. 2Enter the top, sparsest layer at a fixed node↑↓
3. 3Return the best candidates kept along the way↑↓
4. 4Drop into the dense bottom layer once no neighbour improves↑↓

Check order

Mini quiz

1 / 3

An approximate index is called approximate because it:

• AStores rounded vectors
• BMay miss a true nearest neighbour
• CUses a different distance metric
• DReturns fewer results than asked