Nearest neighbor search

Nearest neighbor search retrieves an element of a stored set minimizing its distance from a query. For a finite set $S$ in a metric space with distance $d$, the exact task is to return $x_{\ast }\in S$ satisfyingFor example, among $(0,0)$, $(3,0)$ and $(0,4)$, the nearest point to $(2,1)$ in Euclidean distance is $(3,0)$, at distance $\sqrt{2}$. Scanning all $n$ points in $d$ dimensions takes $O(nd)$ arithmetic work; a useful index eliminates candidates while preserving the required guarantee.

In a recommender system, stored items and queries can be vectors learned by machine learning. The comparison rule matters: minimizing Euclidean distance and maximizing dot product need not rank items identically. For unit vectors, $\Vert q-x{\Vert }^2=2-2⟨q,x⟩$, so those two rankings coincide.^[ref]