recall at k concept

Definition	The fraction of a query's true k nearest neighbours that an index returned. Equation 11.3. Also anti-hub recall.
Example	Returning 7 of a query’s 10 true neighbours is recall at 10 of 0.7.
Book	Data Mining as Observation, draft 0.2, commit `f3914f0`; entry id `recall-at-k`, kind concept.
Status	no ledger row names this entry. Corrections: none recorded.
Defining equation	Book equation 11.3.
Assumptions and scope	The fraction of a query’s true k nearest neighbours, computed from the uncompressed vectors, that the index returned. It lies in the unit interval and is one exactly when the returned list is the true list. The aggregate over queries is a weighted mean over strata, so a stratum that fails entirely moves it by no more than its weight. That is why the anti-hub stratum is reported on its own, and why aggregate recall is never an acceptance metric on its own.
Prior art	none recorded
Evidence	`turboquant-pro/docs/HUBNESS_PRIMER.md:86-131`, `lean/DataMiningAsObservation/RecallAtK.lean`
Reviewed	not yet reviewed; generated 2026-09-10 from records at the commits on the provenance page.

Of the k true neighbours, how many the k returned contain.

Equation

Book equation 11.3.

\[\begin{gathered} \mathrm{recall}@k=\frac{\big|\text{returned top-}k\ \cap\ \text{true top-}k\big|}{k}, \\ \text{true top-}k\text{ computed from the uncompressed vectors}. \end{gathered}\]

Conditions

The fraction of a query’s true k nearest neighbours, computed from the uncompressed vectors, that the index returned. It lies in the unit interval and is one exactly when the returned list is the true list.
The aggregate over queries is a weighted mean over strata, so a stratum that fails entirely moves it by no more than its weight. That is why the anti-hub stratum is reported on its own, and why aggregate recall is never an acceptance metric on its own.

Conditions are curated in entries.toml rather than read from a record.

Ledger

none

First stated

Chapter 11 section 11.3 of Data Mining as Observation, with the program’s stratified form in turboquant-pro, turboquant-pro/docs/HUBNESS_PRIMER.md:86-131.

Measurements

Where the book states it	Numbers, as the book’s sources table records them	Source
chapter 10 section 10.2	anti-hubs as where compressed indexes fail first, aggregate recall barely moves	`turboquant-pro/docs/HUBNESS_PRIMER.md:86-131`
chapter 11 section 11.6	anti-hub recall, p05, hub-rank correlation, hub-set overlap, the build gate	`turboquant-pro/docs/HUBNESS_PRIMER.md:86-131`

Failures and corrections

none

Invariance envelope

none declared

Machine checked

lean/DataMiningAsObservation/RecallAtK.lean, theorems recallAtK_mem_unit, recallAtK_eq_one_iff, aggregate_le_of_failing, aggregate_example, at observation-data-mining f3914f0; what the check covers is stated in the book’s appendix C.

Used in

Data Mining as Observation chapters 0, 10, 11, 12.

anti-hub; min-over-strata; rank certificate; hubness.

Status

Generated 2026-09-10 by encyclopedia/generate.py; book at observation-data-mining f3914f0; the commit of every record is listed in the encyclopedia’s provenance.

← read subspacerecognizer →