Nearest-neighbour search finds the vectors closest to a query vector.
Exact search compares against every vector and is perfectly accurate.
That becomes far too slow once you have millions of vectors.
Approximate nearest neighbour trades a little recall for enormous speed.
In practice ANN returns almost the same results thousands of times faster.
Nearest-neighbour search is the operation at the heart of vector retrieval.
Given a query vector, find the stored vectors closest to it.
Exact search compares against every vector and is perfectly accurate.
With a thousand vectors that is instant, and with fifty million it is hopeless.
The cost grows linearly with the corpus and every query pays it in full.
Approximate nearest neighbour gives up the guarantee to buy speed.
It searches a structure built in advance rather than scanning everything.
Recall measures what it costs you, being the fraction of true neighbours returned.
Typical settings reach 95 to 99 per cent recall while being hundreds of times faster.
Missing one result in twenty rarely matters when a reranker sees the rest.
HNSW builds a navigable graph and is the most common approach.
IVF splits the space into cells and searches only the nearest few.
Product quantisation compresses vectors so more of them fit in memory.
Each has a knob trading recall against speed and memory, and none of the three is free.
Exact search is still right for small collections, and premature indexing is a common waste.
A brute-force scan computes the distance to every stored vector and keeps the smallest, which is exact by construction.
With a million vectors of 768 dimensions that is about 1.5 billion multiply-adds per query, or a few hundred milliseconds on a CPU core.
Adding the selection of the top changes nothing important. The scan dominates, and it grows linearly with the corpus forever.
A flat index is therefore the right answer up to roughly a hundred thousand vectors, and the wrong one above a few million.
Space-partitioning trees work by pruning branches that cannot contain a closer point, and pruning depends on distances being well separated.
In high dimensions they are not, so almost no branch can be excluded and the tree degrades to a full scan with overhead on top.
Embeddings live in hundreds of dimensions, which is exactly the regime where exact indexing stops being possible.
An approximate index gives up exactness and reports how much: recall of 0.95 means 19 of the true top 20 were found.
That is the bargain. Two orders of magnitude faster for one missed result in twenty, and for retrieval the twentieth result rarely changes the answer.
The three families divide by what they give up. Trees and graphs restrict what is visited, hashing restricts what is compared, and quantisation shrinks what is stored.
Step three is why quantised indexes still work.
The compressed vectors choose the candidates and the full vectors decide the order, so the compression error affects recall rather than ranking.
Below vectors, a flat exact index needs no tuning.
From to , HNSW is the fastest and the most memory-hungry.
Above , IVF with product quantisation suits data on disk.
Those thresholds move with hardware and with how much memory you are willing to buy, and the ordering between them does not.
The first question to ask of any vector database is which of these it is running underneath, because every tuning parameter it exposes belongs to one of them.
One question on this card. Every option explains itself once you pick, right or wrong.
17 concepts in this module, then a graded test with every answer explained.