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

2019/08/20 by Baron, Jacob D., Darling, R. W. R. · 1 citation
#06A07 #90C35 #Combinatorics (math.CO) #FOS: Mathematics #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1908.07645

Abstract

Suppose V is an n-element set where for each x ∈ V, the elements of V ∖ \x\ 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 V ∖ \x\ most similar to x. Constructive approximation to this graph using far fewer than n² 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² 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 \binomn2 inter-point distances in a metric space.

Cited by

• FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data

Related

• Approximate Nearest Neighbor Search in High Dimensions
• A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice
• Empirical complexity of comparator-based nearest neighbor descent
• Approximate k-NN Graph Construction: a Generic Online Approach
• Revisiting k-Nearest Neighbor Graph Construction on High-Dimensional Data : Experiments and Analyses