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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Postgraduate Office, School of Computer Science, Universidad Nacional de La Plata
2018-04-01
|
| Series: | Journal of Computer Science and Technology |
| Subjects: | |
| Online Access: | http://journal.info.unlp.edu.ar/JCST/article/view/695 |
| _version_ | 1828522430072619008 |
|---|---|
| author | Edgar Chávez Verónica Ludueña Nora Reyes Fernando Kasián |
| author_facet | Edgar Chávez Verónica Ludueña Nora Reyes Fernando Kasián |
| author_sort | Edgar Chávez |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-12-11T20:07:39Z |
| format | Article |
| id | doaj.art-000ff31aa57e4bb7b91e0da08600813f |
| institution | Directory Open Access Journal |
| issn | 1666-6046 1666-6038 |
| language | English |
| last_indexed | 2024-12-11T20:07:39Z |
| publishDate | 2018-04-01 |
| publisher | Postgraduate Office, School of Computer Science, Universidad Nacional de La Plata |
| record_format | Article |
| series | Journal of Computer Science and Technology |
| spelling | doaj.art-000ff31aa57e4bb7b91e0da08600813f2022-12-22T00:52:22ZengPostgraduate Office, School of Computer Science, Universidad Nacional de La PlataJournal of Computer Science and Technology1666-60461666-60382018-04-011801e07e0710.24215/16666038.18.e07695All Near Neighbor GraphWithout SearchingEdgar Chávez0Verónica Ludueña1Nora Reyes2Fernando Kasián3Centro de Investigación Científica y de Educación Superior de Ensenada, MéxicoDepartamento de Informática, Universidad Nacional de San Luis, San Luis, ArgentinaDepartamento de Informática, Universidad Nacional de San Luis, San Luis, ArgentinaDepartamento de Informática, Universidad Nacional de San Luis, San Luis, ArgentinaGiven 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.http://journal.info.unlp.edu.ar/JCST/article/view/695near neighbor graphproximity searchclusteringmetric indexing |
| spellingShingle | Edgar Chávez Verónica Ludueña Nora Reyes Fernando Kasián All Near Neighbor GraphWithout Searching Journal of Computer Science and Technology near neighbor graph proximity search clustering metric indexing |
| title | 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_short | All Near Neighbor GraphWithout Searching |
| title_sort | all near neighbor graphwithout searching |
| topic | near neighbor graph proximity search clustering metric indexing |
| url | http://journal.info.unlp.edu.ar/JCST/article/view/695 |
| work_keys_str_mv | AT edgarchavez allnearneighborgraphwithoutsearching AT veronicaluduena allnearneighborgraphwithoutsearching AT norareyes allnearneighborgraphwithoutsearching AT fernandokasian allnearneighborgraphwithoutsearching |