Mostrar el registro sencillo de la publicación
An exhaustive algorithm based on GPU to process a kNN query
| dc.contributor.author | Riquelme, Javier A. | |
| dc.contributor.author | Barrientos, Ricardo | |
| dc.contributor.author | Hernández-García, Ruber | |
| dc.contributor.author | Navarro, Cristóbal A. | |
| dc.date.accessioned | 2021-11-22T17:36:02Z | |
| dc.date.available | 2021-11-22T17:36:02Z | |
| dc.date.issued | 2020 | |
| dc.identifier.uri | http://repositorio.ucm.cl/handle/ucm/3502 | |
| dc.description.abstract | The Nearest Neighbors search is a widely used technique with applications on several classification problems. Particularly, the k-nearest neighbor (kNN) algorithm is a well-known method used in modern information retrieval systems aiming to obtain relevant objects based on their similarity to a given query object. Although algorithms based on an exhaustive search have proven to be effective for the kNN classification, their main drawback is their high computational complexity, especially with high-dimensional data. In this work, we present a novel and parallel algorithm to solve kNN queries on a multi-GPU platform. The proposed method is comprised of two stages, which first is based on pivots using the value of K to reduce the search space, and the second one uses a set of heaps to return the final results. Experimental results showed that using between 1-4 GPUs, the proposed algorithm achieves speed-ups of 117x, 224x, 330x, and 389x, respectively. Besides, the obtained results were compared with previous approaches of the state-of-the-art (cp-select and CUB Library), evidencing the superiority of our proposal. | es_CL |
| dc.language.iso | en | es_CL |
| dc.rights | Atribución-NoComercial-SinDerivadas 3.0 Chile | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | * |
| dc.source | 39th International Conference of the Chilean Computer Science Society (SCCC), 2020, 1-8 | es_CL |
| dc.subject | kNN | es_CL |
| dc.subject | GPU | es_CL |
| dc.subject | Multi-GPU | es_CL |
| dc.subject | Exhaustive search | es_CL |
| dc.title | An exhaustive algorithm based on GPU to process a kNN query | es_CL |
| dc.type | Article | es_CL |
| dc.ucm.facultad | Facultad de Ciencias de la Ingeniería | es_CL |
| dc.ucm.indexacion | Scopus | es_CL |
| dc.ucm.uri | ieeexplore.ieee.org/document/9281231 | es_CL |
| dc.ucm.doi | doi.org/10.1109/SCCC51225.2020.9281231 | es_CL |
Ficheros en la publicación
| Ficheros | Tamaño | Formato | Ver |
|---|---|---|---|
|
No hay ficheros asociados a esta publicación. |
|||
Esta publicación aparece en la(s) siguiente(s) colección(ones)
Excepto si se señala otra cosa, la licencia de la publicación se describe como Atribución-NoComercial-SinDerivadas 3.0 Chile