Practical Construction of <i>k</i>-Nearest Neighbor Graphs in Metric Spaces

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} which have 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)}. We focus on the metric space context, so d is a metric. 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, requiring empirically around O(n^1.27) distance computations for low and medium dimensional spaces, and O(n^1.90) for high dimensional ones.