Approximate Nearest Neighbors at Scale
In Lesson 6 the expensive thing was training: one cross-validated fit cost 25 minutes, so we spent evaluations like a scientist. This lesson flips the ledger. For nearest-neighbor methods, training is free, and the bill arrives at prediction time, once per query, forever.
Meet Priya, a search engineer at a music-streaming service. Under every song sits a "More like this" shelf: the 10 tracks that sound most similar to the one playing. Each of her 4,000,000 tracks is stored as an embedding, a list of 64 numbers describing its sound, chosen so that similar-sounding tracks get nearby lists. Finding the shelf is exactly a nearest-neighbor query, the method you know from the classification course. The catch is the contract: the shelf must come back in under 15 milliseconds, and at peak the service builds about 2,000 shelves a second. Exact kNN answers this query perfectly, and cannot possibly answer it fast enough.
By the end of this lesson you will be able to:
- Count the true cost of exact nearest-neighbor search, and say why no clever exact index rescues it in high dimension
- Read recall@10 as the honesty meter of an approximate answer
- Build a navigable graph in R and run the greedy and beam searches that power HNSW-style indexes, watching recall rise as the beam widens
- Run a production HNSW index in R, and know which dial to turn when recall falls short in the real system
Prerequisites: kNN and the Curse of Dimensionality (what a kNN prediction is, Euclidean distance, and the fact that distances blur together in high dimension), and comfort reading R matrices. Everything else is built from scratch here.
The widget below is kNN exactly as you met it: place a query, the k nearest points light up. Notice what the highlight hides: to find those k points, the distance to EVERY point was measured. At 18 points that is invisible. At 4 million it is the whole problem.
One query pays for the whole catalog
kNN "trains" by memorizing the data, and does all of its work at prediction time: measure the distance from the query to every stored point, keep the k closest. One shelf therefore costs \(n\) distance measurements, and each measurement compares \(d\) numbers, so the price per query is proportional to \(n \times d\), where \(n\) is the number of tracks in the catalog and \(d\) is the length of one embedding.
Put Priya's numbers in. One distance in 64 dimensions is roughly 200 arithmetic operations (a subtraction, a squaring and an addition per dimension). Times 4,000,000 tracks, that is around 800 million operations for ONE shelf. Even at two billion operations a second in tight compiled code, that is a few tenths of a second, against a budget of 15 milliseconds, for one listener, with 2,000 more arriving that second. Buying hundreds of servers to brute-force it is exactly what Priya's infrastructure bill cannot absorb.
Each lesson runs in a fresh interactive R session, so we build a small replica of her catalog right here: 2,000 tracks, embeddings of 8 numbers, and 6 broad style pockets (think lo-fi, metal, salsa) so that "similar tracks" genuinely exist. Small enough that every experiment runs in your browser in seconds; the mechanics are identical at 4 million.
Row 1 IS track 1: its sound, compressed to 8 numbers. Now the search itself. Because wall-clock time depends on your machine, we count the thing that actually costs money: distance measurements. Every distance our code ever computes passes through one metered function, so the price of any search is a number we can read, not a stopwatch we have to trust. The query is a listener's taste vector: the average embedding of their last three plays, tracks 6, 10 and 14, all from the same style pocket.
There is the exact shelf: track 1610 is the closest match at distance 1.42 (two of their own recent plays, 14 and 10, also make the cut; a real system would filter those out downstream). And there is the bill: 2,000 distance measurements, the entire catalog, for one query. Every future query pays it again in full.