An Implementation of the Heuristic"NN-Descent"K-Nearest Neighbor Graph Algorithm

Fast Single-Core K-Nearest Neighbor Graph Computation

This paper presents a runtime optimized c implementation of the heuristic"nn-descent"algorithm by wei dong et al.For the l2-distance metric.Various implementationoptimizations are explained which improve performance for low-dimensional aswell as high dimensional datasets.Optimizations to speed up the selection of which datapoint pairs to evaluate the distance for are primarily impactful for low-dimensional datasets.A heuristic which exploits the iterative nature of the heuristic to reorder data in memory is presented which enables better use of locality and thereby improves the runtime.The restriction to the l2-distance metric allows for the use of blocked distance evaluations which significantlyincrease performance for high dimensional datasets.In combination the optimizations yield an implementation which significantly outperforms a widely-used implementation of the heuristic"nn-descent"algorithm on all considered datasets.