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 kNNG is a weighted directed graph G(U,E) such that E= {(u,v), v \in NN_k(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 c₁ n^1.27 distance computations for low and medium dimensional spaces, and c₂ n^1.90 for high dimensional ones.