DOAJ Open Access 2018

All Near Neighbor GraphWithout Searching

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

Abstrak

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.

Topik & Kata Kunci

Computer engineering. Computer hardware Electronic computers. Computer science

Penulis (4)

Edgar Chávez

Verónica Ludueña

Nora Reyes

Fernando Kasián

Format Sitasi

APA MLA BibTeX

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

Akses Cepat

PDF tidak tersedia langsung

Cek di sumber asli →

Lihat di Sumber doi.org/10.24215/16666038.18.e07

Informasi Jurnal

Tahun Terbit: 2018
Sumber Database: DOAJ
DOI: 10.24215/16666038.18.e07
Akses: Open Access ✓