A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice

Hendrik Fichtenberger, Dennis Rohde

In the $k$-nearest neighborhood model ($k$-NN), we are given a set of points $P$, and we shall answer queries $q$ by returning the $k$ nearest neighbors of $q$ in $P$ according to…