Finding neighbours without checking everyone

1Not a lookup

A normal database index (a hash table or a B-tree) answers where is exactly this key? in constant or logarithmic time. Nearest-neighbour search asks a different question. There is no exact key, only “closest”.

When we allow small mistakes in exchange for speed, kNN becomes approximate nearest-neighbour search. That is what every vector database actually does.

2The honest measurement

The quality measure is recall@k:

\text{recall@}k \;=\; \frac{\lvert\, \text{returned top-}k \;\cap\; \text{true top-}k \,\rvert}{k}

Of the true 10 nearest, how many did we return? A recall of 0.95 means one query in two is missing one of its ten true neighbours.

0.1–5% of the data touched per query, typically
90–99% recall for that work
~100× faster than brute force at a billion vectors

Can we get O(1) lookups, like a hash table?

Not for exact nearest neighbours in high dimensions; that is believed to be impossible in general. What we get is sublinear:

LSH has provable bounds of the form $O(N^{\rho})$ with $\rho < 1$ (5.2 Turning a gentle slope into a cliff).
Graph indexes behave roughly like $O(\log N)$ hops in practice.

Hashing does give O(1) per bucket lookup, but you need many hash tables to avoid missing neighbours, so the total is not constant.

3Four families

Each family is a different answer to how do I pick which fraction to look at?

Trees Split the space into boxes and descend into the boxes near the query. Great in a few dimensions. → 2.2 Cut the space into pieces
Hashing Design hash functions so that close points collide. Simple and data-independent. → 2.2 Cut the space into pieces, then all of Part 5
Clustering and quantization Learn where the data actually is, file each vector under its cluster, and compress what you store. → 2.2 Cut the space into pieces, then Parts 3 and 4
Graphs Link every vector to its near neighbours and walk downhill toward the query. → 2.3 Walk toward the query

Production systems combine them: a partition to narrow down, compressed codes to scan cheaply, and exact vectors to re-rank a shortlist.