The dial: scan less, lose recall
"First part of the data" is a deliberately bad approximation. Real indexes (the next topics) choose which part to look at.
Sorting and tree structures that make ordinary database lookups fast stop helping when vectors have hundreds of numbers. Vector indexes therefore trade a little accuracy for a lot of speed, and the accuracy is measured as recall against the exact answer.
Change the code and press Run (Ctrl+Enter). Predict what will happen first, then break it on purpose and read what changes. Your edits are saved and match the lesson page.
Ready for more? This phase has 6 hands-on exercises with automatic checks.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Write recall_at_k(found, truth) that returns the fraction of truth present in found. Print it with 3 decimals for found [3, 1, 7, 9] against truth [1, 2, 3, 4], for an empty found list, and for the same four ids in reverse order.
Three queries have (found, truth) pairs ([1, 2, 3], [1, 2, 3]), ([4, 5, 6], [4, 9, 6]) and ([7, 8, 9], [1, 2, 3]). Print each query's recall and then the average and the worst, to 3 decimals. What does the average hide?
Explain it without notes
Why can a database find one number among millions with about twenty steps, but not the nearest vector among millions?
What does the distance table in the first example show, and why does it hurt indexing?
Define recall@k and compute it for found = [3, 1, 7, 9] against truth = [1, 2, 3, 4].
Why must the ground truth for recall come from exact search over the whole collection?
A teammate says the index has recall 0.97, so it is fine. What would you check before agreeing?
Expected output
approximation: look only at the first part of the data (20 queries, k = 5)
scan 100 of 400 vectors: recall@5 = 0.230
scan 200 of 400 vectors: recall@5 = 0.440
scan 300 of 400 vectors: recall@5 = 0.720
scan 400 of 400 vectors: recall@5 = 1.000
query 0, exact top-5: 136, 309, 388, 51, 244
query 0, first 200: 136, 51, 0, 169, 115