All Near Neighbor GraphWithout Searching
Given a collection of n objects equipped with a distance function d(·, ·), the Nearest Neighbor Graph (NNG) consists in finding the nearest neighbor of each object in the collection. Without an index the total cost of NNG is quadratic. Using an index the cost would be sub-quadratic if the search for...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2018
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/66742 http://journal.info.unlp.edu.ar/JCST/article/view/695/225 |
| Aporte de: |
| id |
I19-R120-10915-66742 |
|---|---|
| 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 near neighbor graph proximity search clustering metric indexing |
| spellingShingle |
Ciencias Informáticas near neighbor graph proximity search clustering metric indexing Chávez, Edgar Ludueña, Verónica Reyes, Nora Susana Kasián, Fernando All Near Neighbor GraphWithout Searching |
| topic_facet |
Ciencias Informáticas near neighbor graph proximity search clustering metric indexing |
| description |
Given a collection of n objects equipped with a distance function d(·, ·), the Nearest Neighbor Graph (NNG) consists in finding the nearest neighbor of each object in the collection. Without an index the total cost of NNG is quadratic. Using an index the cost would be sub-quadratic if the search for individual items is sublinear. Unfortunately, due to the so called curse of dimensionality the indexed and the brute force methods are almost equally inefficient. In this paper we present an efficient algorithm to build the Near Neighbor Graph (nNG), that is an approximation of NNG, using only the index construction, without actually searching for objects. |
| format |
Articulo Articulo |
| 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 |
All Near Neighbor GraphWithout Searching |
| title_short |
All Near Neighbor GraphWithout Searching |
| title_full |
All Near Neighbor GraphWithout Searching |
| title_fullStr |
All Near Neighbor GraphWithout Searching |
| title_full_unstemmed |
All Near Neighbor GraphWithout Searching |
| title_sort |
all near neighbor graphwithout searching |
| publishDate |
2018 |
| url |
http://sedici.unlp.edu.ar/handle/10915/66742 http://journal.info.unlp.edu.ar/JCST/article/view/695/225 |
| work_keys_str_mv |
AT chavezedgar allnearneighborgraphwithoutsearching AT luduenaveronica allnearneighborgraphwithoutsearching AT reyesnorasusana allnearneighborgraphwithoutsearching AT kasianfernando allnearneighborgraphwithoutsearching |
| bdutipo_str |
Repositorios |
| _version_ |
1764820480556007424 |