About Nearest Neighbour
Nearest Neighbour explains how approximate similarity search works, from the naive approach upward.
Not how to run a vector database. Not which one to buy. Not what an embedding is in one sentence. The mechanism: metrics, index structures, quantization, and the trade-off surface they all sit on.
Why this is a whole site
Because most writing about vector search stops at the level of “it finds similar things, and there’s an index that makes it fast.”
That’s true, and it’s not enough to work with. It doesn’t tell you why one parameter costs you recall and another costs you memory. It doesn’t tell you why a filter that matches 0.1% of your documents behaves completely differently from one matching 30%. It doesn’t tell you why your results got worse when the vectors got shorter.
All of those follow directly from how the index works. Once you can picture the traversal, the behaviour stops being surprising and the parameters stop being magic numbers you copy from a tutorial.
How posts are written
Every one follows the same shape, deliberately:
- The naive approach — the obvious way to do it.
- Exactly how it fails — and at what scale.
- The fix, introduced as the natural response to that failure.
- How it actually works, with pseudocode where that’s clearer than prose.
- What it gives up — all of this is approximate, and the approximation should be named.
- The knobs, and which direction each one moves you.
The aim is that you finish able to re-derive the idea, not just recognise its name. Geometry comes before notation, always. If a formula can be preceded by a sentence about what it does in space, it is.
What we think
“Approximate” is the whole subject, not a caveat. Exact nearest-neighbour search is easy and doesn’t scale. Everything interesting here is a specific, principled way of being slightly wrong in exchange for being much faster. A post that doesn’t say what accuracy is being traded hasn’t explained anything.
The curse of dimensionality is more specific than people say. It isn’t “high dimensions don’t work” — plenty of high-dimensional search works fine. The real phenomenon is that under certain distributions, distances concentrate, and the gap between nearest and farthest shrinks until the ranking carries little information. Whether that bites you depends on your data, not just its dimension count.
Index families aren’t better or worse, they’re differently shaped. Graph indexes and cluster indexes make opposite bets about where to spend memory and when to do work. Which is right depends on your update rate, your filter patterns, and your memory budget.
On numbers
We don’t publish benchmarks.
Complexity claims are fair game — logarithmic-ish traversal versus linear scan is a property of the algorithm and doesn’t go stale. Measured recall percentages and latencies are not: they depend on the dataset, the dimensionality, the distribution, the implementation and the hardware, and a figure lifted from one setting tells you nothing reliable about another.
Where a well-documented qualitative result exists, you’ll get it qualitatively. Where something depends on your data, you’ll be told which property of your data it depends on.
Products are not ranked, scored, or recommended here. Index families are compared constantly — that’s the point of the site — but that’s a comparison of mechanisms, not of vendors.
Where the boundary is
This site explains algorithms. Running a deployed vector database — sizing, rebuilds, backups, monitoring — is a genuinely different discipline with a different reader, and it isn’t covered here.