= 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_*\in S$ satisfying
$$
d(q,x_*)=\min_{x\in S}d(q,x).
$$
For example, among $(0,0)$, $(3,0)$ and $(0,4)$, the nearest point to $(2,1)$ in <Euclidean distance> is $(3,0)$, at distance $\sqrt2$. 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>, $\|q-x\|^2=2-2\langle q,x\rangle$, so those two rankings coincide.<Candidate generation overview by Google>[Embedding space and Similarity measures]{ref}
Back to article page
