K-Nearest Neighbor Approximation Via the Friend-of-a-Friend Principle

arXiv1908.07645MaRDI QIDQ6323973FDOQ6323973

Authors: Jacob D. Baron, Richard W. R. Darling 

Publication date: 20 August 2019

Abstract: Suppose $V$ is an $n$-element set where for each $xinV$, the elements of $Vsetminusx$ are ranked by their similarity to $x$. The $K$-nearest neighbor graph is a directed graph including an arc from each $x$ to the $K$ points of $Vsetminusx$ most similar to $x$. Constructive approximation to this graph using far fewer than $n^2$ comparisons is important for the analysis of large high-dimensional data sets. $K$-Nearest Neighbor Descent is a parameter-free heuristic where a sequence of graph approximations is constructed, in which second neighbors in one approximation are proposed as neighbors in the next. Run times in a test case fit an $O(n{K}^{2}logn)$ pattern. This bound is rigorously justified for a similar algorithm, using range queries, when applied to a homogeneous Poisson process in suitable dimension. However the basic algorithm fails to achieve subquadratic complexity on sets whose similarity rankings arise from a ``generic linear order on the $$ inter-point distances in a metric space.

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorics of partially ordered sets (06A07)

This page was built for publication: K-Nearest Neighbor Approximation Via the Friend-of-a-Friend Principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323973)