R2.2 · LESSON 2 OF 6

Top-k selection

Implement an exact baseline, compute recall at k and explain approximate search and high-dimensional difficulty.

THE IDEA

Choosing the top k

After scoring, you need only the best k. Sorting all n scores works, but a heap of size k or a partial selection (a partition) finds the best k with less work (about n·log₂k instead of n·log₂n). Whatever method you use, fix the tie rule (for example the lower index first) or two correct implementations will return different results.

Score seen 1 of 6

Scores so far: #0:5

best 2 kept: #0 (5) new score 5 enters the kept set; ties go to the lower index

Only the k best are ever kept (a heap does this cheaply). Sorting the whole corpus is n·log₂n comparisons, a heap about n·log₂k. Always state the tie rule so results are reproducible.

Step through the scores and watch the kept set.

Predict first. Must the full corpus be completely sorted to identify its best ten entries?

Chapter context

An exact search compares every candidate under a defined metric. Approximate indexes reduce work by choosing promising candidates, accepting that some true nearest neighbors may be missed.

TRY IT YOURSELF

Part 1. Do it hands-on

Select top results with ties by hand, then implement sorting, heap and partition versions that must agree.

Score seen 1 of 6

Scores so far: #0:5

best 2 kept: #0 (5) new score 5 enters the kept set; ties go to the lower index

Only the k best are ever kept (a heap does this cheaply). Sorting the whole corpus is n·log₂n comparisons, a heap about n·log₂k. Always state the tie rule so results are reproducible.

top-2 of [5,3,5,1] top-3 n log₂ n for n = 1024 n log₂ 8 for n = 1024

To do: Scores [5, 3, 5, 1] (higher is better), indices 0–3. Rule for ties: the LOWER index first. Top-2 indices, comma separated?
To do: Top-3 indices with the same rule?
To do: Fully sorting n = 1024 scores takes roughly n · log₂ n comparisons. Type that number
To do: Keeping a heap of only the best k = 8 costs roughly n · log₂ k. Type that number for n = 1024

Part 2. Do it in code

top_k_sorted(scores, k): the indices of the k highest scores by fully sorting (ties: lower index first).
top_k_heap(scores, k): the same result using a heap of size k (import heapq): keep the k best seen so far without sorting everything. Return indices ordered best first with the same tie rule.
top_k_partition(scores, k): use np.argpartition to find the k best, then order only those k; ties as before.
comparisons(n, k, method): rough cost: "sort" → n·log2(n), "heap" → n·log2(k). ValueError for an unknown method.

import heapq
import numpy as np

def top_k_sorted(scores, k):
    pass

def top_k_heap(scores, k):
    pass

def top_k_partition(scores, k):
    pass

def comparisons(n, k, method):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Must the full corpus be completely sorted to identify its best ten entries?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

An exact dense dot-product scan over N vectors of dimension d needs Nd coordinate products plus reductions.

\operatorname{recall@k}=\frac{|R_k\cap G_k|}{k}.

This assumes k ground-truth eligible neighbors. In a d-dimensional unit box, a sub-box spanning fraction r of every axis occupies fraction $r^d$ of the volume.

Worked example

Scanning 1000 vectors of dimension 128 uses 128,000 coordinate products, before selection and other overhead. If the true three neighbors are {A,B,C} and the returned set is {A,C,E}, recall@3 is 2/3. A sub-box spanning 0.1 of each of ten axes occupies only 10^-10 of the unit-box volume.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
assert 1000*128 == 128000
truth,returned={'A','B','C'},{'A','C','E'}
assert isclose(len(truth & returned)/3,2/3)
assert isclose(.1**10,1e-10)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Index recall is not the same as judged semantic relevance. High-dimensional behavior depends on the data manifold. Tie policies can affect reported recall for identical distances.