###
Practical Construction of *k*-Nearest Neighbor Graphs in Metric Spaces

####
Rodrigo Paredes, Edgar Chávez, Karina Figueroa, and Gonzalo Navarro

Let *U* be a set of elements and *d* a distance function defined among them.
Let *NN_k(u)* be the *k* elements in *U-{u}* which have
the smallest distance towards *u*.
The *k*-nearest neighbor graph (*k*nng) is a weighted directed graph
*G(U,E)* such that *E = {(u,v), v in NN_k(u)}*.
We focus on the metric space context, so *d* is a metric.
Several *k*nng construction algorithms are known, but
they are not suitable to general metric spaces.
We present a general methodology to construct *k*nngs
that exploits several features of metric spaces,
requiring empirically around *O(n^1.27)* distance
computations for low and medium dimensional spaces, and
*O(n^1.90)* for high dimensional ones.