Embeddings and nearest-neighbour search
Turning items into vectors and finding similar ones in milliseconds.
01The intuition
The problem it solves
Asha types "sunset at the beach" into Google Photos. None of her photos has that caption; they are just pixels. A keyword index cannot help, because there are no keywords. Or: a reader has just finished an article about monsoon forecasting, and the app wants to show three similar articles among ten million, where "similar" means about the same thing, not sharing the same words.
Both need a way to say how alike two things are, whether they are a photo and a sentence or two articles. And both need to find the most alike items out of millions in the time a page takes to load, which rules out comparing with every item one by one.
Build it one piece at a time
Step 1: turn each item into a list of numbers. A trained model maps a photo, a sentence or an article to a vector, for example 512 numbers. The model is trained so that things with similar meaning land close together: the vector for a beach sunset photo is near the vector for the text "sunset at the beach". These vectors are embeddings.
Step 2: measure closeness. Closeness is the distance between two vectors, or the cosine of the angle between them. With two numbers per item you can picture it on graph paper; with 512 the arithmetic is the same.
| Item | Vector (2 of 512 shown) | Cosine to query "sunset at the beach" |
|---|---|---|
| photo 1 (beach, evening) | (0.91, 0.40, …) | 0.88 |
| photo 2 (office desk) | (−0.20, 0.75, …) | 0.12 |
| photo 3 (lake at dusk) | (0.80, 0.52, …) | 0.74 |
Step 3: search by brute force, and see it fail. Embed the query, compute its cosine against every stored vector, keep the top ten. For 10,000 photos that is instant. For 10 million it is 10 million × 512 multiplications, about 5 billion operations, roughly a second per query on one core. For a billion items it is minutes.
Step 4: approximate nearest neighbours (ANN). Give up exactness for speed. One way: cluster the vectors into 10,000 groups, store each group's centre, and at query time compare the query with the 10,000 centres, then only with the vectors inside the closest 20 groups. Another way, HNSW, builds a graph where each vector links to its near neighbours, with a few long-range links, and search walks the graph greedily from an entry point toward the query. Both check a few thousand vectors instead of millions and find the true top ten most of the time.
Step 5: shrink the vectors. A billion vectors of 512 32-bit floats is 2 TB of RAM. Quantisation stores each vector in 64 bytes instead of 2,048 by rounding it to codebook entries, so the same billion fits in 64 GB and search gets faster because memory traffic drops.
Why it works, with the numbers
Brute force costs n × d per query. A clustered index costs about c × d for the centres plus (n ÷ c) × p × d for the p probed clusters:
n = 109, d = 512, c = 104, p = 20: 104 × 512 + 105 × 20 × 512 ≈ 109 operations, about 1,000× fewer than brute force
The guarantee is "recall at 10", the fraction of the true top ten that the approximate search returns, typically tuned to 95 percent or better; it is a measured number, not a promise of exactness. The honest limits: results are only as good as the embedding model, so a photo the model does not understand is unfindable; a new item is searchable only after it is embedded and inserted, which for some indexes means a periodic rebuild; and the index must be sharded across machines at billion scale, with each shard answering a query and a merge of the results, exactly like scatter-gather search.
The trade-off you must say out loud
Probing more clusters raises recall and latency together; quantising harder saves memory and loses a little accuracy. Say the recall target and the latency you bought it with. The interviewer's follow-up is often about filters ("beach photos from 2023"): either filter the candidates after the vector search and risk too few results, or build the filter into the index, which costs more index structures.
Where it shows up in the 100 Google problems
- Design Google Photos: images and text queries in one embedding space, with a per-user index small enough for exact search and a global index for shared libraries.
- Design a recommendation system: candidate generation by nearest neighbours of the user's history embedding.
- Retrieval-augmented generation pipeline: chunks of documents embedded and retrieved by similarity to the question, then reranked.
- Design Google News: clustering articles into stories by embedding distance.
- Design TikTok: videos near what a user just watched, refreshed as they swipe.