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

Guardado en:
Detalles Bibliográficos
Autores principales: Chávez, Edgar, Ludueña, Verónica, Reyes, Nora Susana, Kasián, Fernando
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2016
Materias:
Ciencias Informáticas
similarity search
databases
metric spaces
approximate search
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/56767
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-56767
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
similarity search
databases
metric spaces
approximate search
spellingShingle 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
topic_facet Ciencias Informáticas
similarity search
databases
metric spaces
approximate search
description 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.
format Objeto de conferencia
Objeto de conferencia
author Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
Kasián, Fernando
author_facet Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
Kasián, Fernando
author_sort Chávez, Edgar
title Approximate Nearest Neighbor Graph via Index Construction
title_short Approximate Nearest Neighbor Graph via Index Construction
title_full Approximate Nearest Neighbor Graph via Index Construction
title_fullStr Approximate Nearest Neighbor Graph via Index Construction
title_full_unstemmed Approximate Nearest Neighbor Graph via Index Construction
title_sort approximate nearest neighbor graph via index construction
publishDate 2016
url http://sedici.unlp.edu.ar/handle/10915/56767
work_keys_str_mv AT chavezedgar approximatenearestneighborgraphviaindexconstruction
AT luduenaveronica approximatenearestneighborgraphviaindexconstruction
AT reyesnorasusana approximatenearestneighborgraphviaindexconstruction
AT kasianfernando approximatenearestneighborgraphviaindexconstruction
bdutipo_str Repositorios
_version_ 1764820477569662977

Ejemplares similares