Artículo de revista
Practical construction of k-nearest neighbor graphs in metric spaces
Fecha
2006Registro en:
EXPERIMENTAL ALGORITHMS, PROCEEDINGS Book Series: LECTURE NOTES IN COMPUTER SCIENCE Volume: 4007 Pages: 85-97 Published: 2006
0302-9743
Autor
Paredes, Rodrigo
Chávez, Edgar
Figueroa, Karina
Navarro, Gonzalo
Institución
Resumen
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.