EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

All Near Neighbor GraphWithout Searching

Edgar Chávez, Verónica Ludueña, Nora Reyes, Fernando Kasián

Journal of Computer Science and Technology · 2018

DOI: 10.24215/16666038.18.e07 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Computer Science and Technology, 2018. Verfasst von Edgar Chávez und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Chávez, E., Ludueña, V., Reyes, N., & Kasián, F. (2018). All Near Neighbor GraphWithout Searching. Journal of Computer Science and Technology. https://doi.org/10.24215/16666038.18.e07

Vancouver

Chávez E, Ludueña V, Reyes N, Kasián F. All Near Neighbor GraphWithout Searching. Journal of Computer Science and Technology. 2018. doi:10.24215/16666038.18.e07

BibTeX
@article{Chvez2018,
  author = {Chávez, Edgar and Ludueña, Verónica and Reyes, Nora and Kasián, Fernando},
  title = {All Near Neighbor GraphWithout Searching},
  journal = {Journal of Computer Science and Technology},
  year = {2018},
  doi = {10.24215/16666038.18.e07}
}
Kostenlos starten →