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 NNk(u) be the k elements in U - {u} having
the smallest distance towards u.
The k-nearest neighbor graph kNNG is a weighted directed graph
G(U,E) such that E= {(u,v), v \in NNk(u)}.
Several kNNG construction algorithms are known, but
they are not suitable to general metric spaces.
We present a general methodology to construct kNNGs
that exploits several features of metric spaces.
Experiments suggest that it yields costs of the form c1 n1.27 distance
computations for low and medium dimensional spaces, and
c2 n1.90 for high dimensional ones.