###
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}* having
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)}.
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.
Experiments suggest that it yields costs of the form *c*_{1} n^{1.27} distance
computations for low and medium dimensional spaces, and
*c*_{2} n^{1.90} for high dimensional ones.