Mostrar el registro sencillo de la publicación

dc.contributor.authorBarrientos, Ricardo
dc.contributor.authorMillaguir, Fabricio
dc.contributor.authorSánchez, José L.
dc.contributor.authorArias, Enrique
dc.date.accessioned2017-11-22T13:40:37Z
dc.date.available2017-11-22T13:40:37Z
dc.date.issued2017
dc.identifier.urihttp://repositorio.ucm.cl/handle/ucm/1306
dc.description.abstractEfficient kNN search, or k-nearest neighbors search, is useful, among other fields, in multimedia information retrieval, data mining and pattern recognition problems. A distance function determines how similar the objects are to a given kNN query object. As finding the distance between any given pair of objects (i.e., high-dimensional vectors) is known to be a computationally expensive operation, using parallel computation techniques is an effective way of reducing running times to acceptable values in large databases. In the present work, we offer novel GPU approaches to solving kNN (k-nearest neighbor) queries using exhaustive algorithms based on the Selection Sort, Quicksort and state-of-the-art algorithms. We show that the best approach depends on the k value of the kNN query and achieve a speedup up to 86.4 ×× better than the sequential counterpart. We also propose a multi-core algorithm to be used as reference for the experiments and a hybrid algorithm which combines the proposed algorithms with a state-of-the-art heaps-based method, in which the best performance is obtained with high k values. We also extend our algorithms to be able to deal with large databases that do not fit in GPU memory and whose performance does not deteriorate as database size increases.es_CL
dc.language.isoenes_CL
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Chile*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
dc.sourceThe Journal of Supercomputing, 73(10), 4611-4634es_CL
dc.subjectQuicksortes_CL
dc.subjectSelection Sortes_CL
dc.subjectExhaustive algorithmses_CL
dc.titleGPU-based exhaustive algorithms processing kNN querieses_CL
dc.typeArticlees_CL
dc.ucm.facultadFacultad de Ciencias de la Ingenieríaes_CL
dc.ucm.indexacionScopuses_CL
dc.ucm.indexacionScieloes_CL
dc.ucm.urisibib2.ucm.cl:2048/login?url=https://link.springer.com/article/10.1007/s11227-017-2110-yes_CL
dc.ucm.doidoi.org/10.1007/s11227-017-2110-yes_CL


Ficheros en la publicación

FicherosTamañoFormatoVer

No hay ficheros asociados a esta publicación.

Esta publicación aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo de la publicación

Atribución-NoComercial-SinDerivadas 3.0 Chile
Excepto si se señala otra cosa, la licencia de la publicación se describe como Atribución-NoComercial-SinDerivadas 3.0 Chile