Why do vector databases use approximate nearest neighbour search instead of exact search?
Exact search compares the query with every vector, which gets too slow for millions of items. Approximate nearest neighbour indexes such as graph or clustering structures check only a small part of the data and usually return the same top results, trading a little recall for large speed gains.
Explain it simply
To find the closest tea stall to you in a big city, you would not measure the distance to every stall. You would look in your neighbourhood and the next one. You might miss a slightly closer stall across a boundary, but you find a good one quickly.
Approximate nearest neighbour (ANN) works like this. Indexes group or link vectors so a search jumps through nearby regions instead of scanning everything. Popular families include graph-based indexes and cluster-based ones, often with compression.
You tune a trade-off between recall (how often the true nearest items are found), speed, and memory. For a collection of a few thousand chunks, exact search is perfectly fine and simpler. ANN pays off when the collection grows large and latency matters.
Example
1,000 chunks -> exact search takes milliseconds, no index needed
10,000,000 chunks -> exact scan too slow; ANN returns top 10 in a few ms
with, say, 95-99% of the true top 10Numbers are illustrative.
What to say in the interview
"Exact nearest neighbour is linear in collection size. ANN indexes trade a small recall loss for much lower latency. I would use exact search for small corpora and tune ANN parameters against measured recall when it grows."