A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree

Given a reference set $R$ of $n$ points and a query set $Q$ of $m$ points in a metric space, this paper studies an important problem of finding $k$-nearest neighbors of every point $q \in Q$ in the set $R$ in a near-linear time. In the paper at ICML 2006, Beygelzimer, Kakade, and Langford introduced a cover tree and attempted to prove that that its construction requires $O(n\log n)$ time while the nearest neighbor search needs $O(n\log m)$ time with a hidden dimensionality factor. In 2015, section~5.3 of Curtin's PhD thesis pointed out that the proof of the latter claim might contain a serious gap in time estimation. In the paper at TopoInVis 2022, the authors built explicit counterexamples for a key step in the proofs of both claims. The past obstacles will be overcome by a simpler compressed cover tree on the reference set $R$. The first new algorithm constructs a compressed cover tree in $O(n \log n)$ time. The second new algorithm finds all $k$-nearest neighbors of all points from $Q$ using a compressed cover tree in time $O(m(k+\log n)\log k)$ with a hidden dimensionality factor depending on point distributions of the sets $R,Q$ but not on their sizes.