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.