Solving All-k-Nearest Neighbor Problem without an Index

Among the similarity queries in metric spaces, there are one that obtains the k-nearest neighbors of all the elements in the database (All-k-NN). One way to solve it is the naïve one: comparing each object in the database with all the other ones and returning the k elements nearest to it (k-NN). Ano...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Chávez, Edgar, Ludueña, Verónica, Reyes, Nora Susana
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2019
Materias:
Ciencias Informáticas
All-k-NN problem
Database
k Nearest Neighbor Graph
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/90536
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-90536
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
All-k-NN problem
Database
k Nearest Neighbor Graph
spellingShingle Ciencias Informáticas
All-k-NN problem
Database
k Nearest Neighbor Graph
Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
Solving All-k-Nearest Neighbor Problem without an Index
topic_facet Ciencias Informáticas
All-k-NN problem
Database
k Nearest Neighbor Graph
description Among the similarity queries in metric spaces, there are one that obtains the k-nearest neighbors of all the elements in the database (All-k-NN). One way to solve it is the naïve one: comparing each object in the database with all the other ones and returning the k elements nearest to it (k-NN). Another way to do this is by preprocessing the database to build an index, and then searching on this index for the k-NN of each element of the dataset. Answering to the All-k-NN problem allows to build the k-Nearest Neighbor graph (kNNG). Given an object collection of a metric space, the Nearest Neighbor Graph (NNG) associates each node with its closest neighbor under the given metric. If we link each object to their k nearest neighbors, we obtain the k Nearest Neighbor Graph (kNNG).The kNNG can be considered an index for a database, which is quite efficient and can allow improvements. In this work, we propose a new technique to solve the All-k-NN problem which do not use any index to obtain the k-NN of each element. This approach solves the problem avoiding as many comparisons as possible, only comparing some database elements and taking advantage of the distance function properties. Its total cost is significantly lower than that of the naïve solution.
format Objeto de conferencia
Objeto de conferencia
author Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
author_facet Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
author_sort Chávez, Edgar
title Solving All-k-Nearest Neighbor Problem without an Index
title_short Solving All-k-Nearest Neighbor Problem without an Index
title_full Solving All-k-Nearest Neighbor Problem without an Index
title_fullStr Solving All-k-Nearest Neighbor Problem without an Index
title_full_unstemmed Solving All-k-Nearest Neighbor Problem without an Index
title_sort solving all-k-nearest neighbor problem without an index
publishDate 2019
url http://sedici.unlp.edu.ar/handle/10915/90536
work_keys_str_mv AT chavezedgar solvingallknearestneighborproblemwithoutanindex
AT luduenaveronica solvingallknearestneighborproblemwithoutanindex
AT reyesnorasusana solvingallknearestneighborproblemwithoutanindex
bdutipo_str Repositorios
_version_ 1764820490126360577

Ejemplares similares