# Approximate Nearest Neighbor Graph via Index Construction

Given a collection of objects in a metric space, the Nearest Neighbor Graph (NNG) associate each node with its closest neighbor under the given metric. It can be obtained trivially by computing the nearest neighbor of every object. To avoid computing every distance pair an index could be construct...

Descripción completa

Autores principales: , , , Objeto de conferencia Inglés 2016 http://sedici.unlp.edu.ar/handle/10915/56767 Aportado por : SEDICI (UNLP) de Universidad Nacional de La Plata .
id I19-R120-10915-56767 dspace Universidad Nacional de La Plata I-19 R-120 SEDICI (UNLP) Inglés Ciencias Informáticas similarity search databases metric spaces approximate search Ciencias Informáticas similarity search databases metric spaces approximate search Chávez, Edgar Ludueña, Verónica Reyes, Nora Susana Kasián, Fernando Approximate Nearest Neighbor Graph via Index Construction Ciencias Informáticas similarity search databases metric spaces approximate search Given a collection of objects in a metric space, the Nearest Neighbor Graph (NNG) associate each node with its closest neighbor under the given metric. It can be obtained trivially by computing the nearest neighbor of every object. To avoid computing every distance pair an index could be constructed. Unfortunately, due to the curse of dimensionality the indexed and the brute force methods are almost equally inefficient. This bring the attention to algorithms computing approximate versions of NNG. The DiSAT is a proximity searching tree. It is hierarchical. The root computes the distances to all objects, and each child node of the root computes the distance to all its subtree recursively. Top levels will have accurate computation of the nearest neighbor, and as we descend the tree this information would be less accurate. If we perform a few rebuilds of the index, taking deep nodes in each iteration, keeping score of the closest known neighbor, it is possible to compute an Approximate NNG (ANNG). Accordingly, in this work we propose to obtain de ANNG by this approach, without performing any search, and we tested this proposal in both synthetic and real world databases with good results both in costs and response quality. Objeto de conferencia Objeto de conferencia Chávez, Edgar Ludueña, Verónica Reyes, Nora Susana Kasián, Fernando Chávez, Edgar Ludueña, Verónica Reyes, Nora Susana Kasián, Fernando Chávez, Edgar Approximate Nearest Neighbor Graph via Index Construction Approximate Nearest Neighbor Graph via Index Construction Approximate Nearest Neighbor Graph via Index Construction Approximate Nearest Neighbor Graph via Index Construction Approximate Nearest Neighbor Graph via Index Construction approximate nearest neighbor graph via index construction 2016 http://sedici.unlp.edu.ar/handle/10915/56767 AT chavezedgar approximatenearestneighborgraphviaindexconstruction AT luduenaveronica approximatenearestneighborgraphviaindexconstruction AT reyesnorasusana approximatenearestneighborgraphviaindexconstruction AT kasianfernando approximatenearestneighborgraphviaindexconstruction Repositorios 1764820477569662977