Nearest-Neighbor Search

Finding the closest friend in a crowd.

Imagine you walk into a crowded room and want the person standing physically closest to you. The honest way is to measure your distance to every single person, then pick the smallest. Slow, but it cannot miss. Nearest-neighbor search is exactly that, except the "people" are the passage points in the store and "you" are the question, turned into its own point.

The store already holds every passage as a point (its embedding). At question time you embed the question into a point too, then ask: which stored points are nearest to this one? Closeness here means similarity of meaning (you saw how to measure it with cosine in Unit 1). Near in space is near in meaning.

Brute force, the honest way.

The simplest method is brute force, and it is worth doing once by hand so the idea is concrete. Three steps: compare the query to every stored vector, sort by closeness, take the top few. Here is a tiny store of five passages, with a made-up closeness score for each (higher is closer):

Ask for the top-k, the k closest, and with k = 2 you get back p3 and p1. That "k" is just how many neighbors you want: top-5 means the five closest passages, the shortlist you will hand to the next stage. Brute force always returns the true closest, because it checked everyone.

Why brute force stops working.

Five passages is nothing. The trouble is the cost grows with the size of the store. Comparing against every vector means the work doubles when the store doubles. Five comparisons is instant. A store with a million passages means a million comparisons for every single question, and the comparisons themselves are not free, since each is across hundreds of numbers in the vector.

Back to the crowded room: measuring your distance to four people is easy. Measuring it to every person in a packed stadium, for every newcomer, every second, is hopeless. At serving time you have a few milliseconds to answer, not seconds. Brute force is correct and too slow at scale.

The shortcut: approximate, but fast.

The fix is to stop insisting on the perfect answer. Approximate nearest-neighbor search (ANN) organizes the points ahead of time so a query only has to look at a small, promising slice of them instead of all of them. Back in the stadium: instead of measuring everyone, you go straight to the section where people like you tend to sit, and search just there.

The trade is in the name. Approximate means it might occasionally miss a true neighbor that was sitting in a section it skipped. In exchange it is far faster, often turning a million comparisons into a few thousand. For retrieval that is a great deal: you give up a sliver of accuracy and gain orders of magnitude in speed. The next lesson gives you the number that measures exactly how much you gave up.

Key takeaways