Practical construction of k-nearest neighbor graphs in metric spaces

Abstract

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 to u. The k-nearest neighbor graph (kNNG) is a weighted directed graph G(U,E) such that E = {(u,v), v is an element of 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 c(1)n(1.27) distance computations for low and medium dimensional spaces, and c(2)n(1.90) for high dimensional ones.