Ítem


Solving multiple kth smallest dissimilarity queries for non-metric dissimilarities with the GPU

The kth smallest dissimilarity of a query point with respect to a given set is the dissimilarity that ranks number k when we sort, in increasing order, the dissimilarity value of the points in the set with respect to the query point. A multiple kth smallest dissimilarity query determines the kth smallest dissimilarity for several query points simultaneously. Although the problem of solving multiple kth smallest dissimilarity queries is an important primitive operation used in many areas, such as spatial data analysis, facility location, text classification and content-based image retrieval, it has not been previously addressed explicitly in the literature. In this paper we present three parallel strategies, to be run on a Graphics Processing Unit, for computing multiple kth smallest dissimilarity queries when non-metric dissimilarities, that do not satisfy the triangular inequality, are used. The strategies are theoretically and experimentally analyzed and compared among them and with an efficient sequential strategy to solve the problem

Work partially supported by the Spanish Ministerio de Economía y Competitividad under Grant TIN2014-52211-C2-2-R. We also gratefully acknowledge the support of NVIDIA Corporation with the donation of the Tesla K40 GPU used for this research

info:eu-repo/grantAgreement/MINECO//TIN2014-52211-C2-2-R/ES/GENERACION, SIMULACION Y VISUALIZACION DE MODELOS 3D A PARTIR DE GRANDES CONJUNTOS DE DATOS. APLICACIONES EN LA MEJORA DE LA CALIDAD DE VIDA DE LAS PERSONAS Y SU ENTORNO/

Elsevier

Director: Ministerio de Economía y Competitividad (Espanya)
Autor: Fort, Marta
Sellarès i Chiva, Joan Antoni
Data: 20 setembre 2016
Resum: The kth smallest dissimilarity of a query point with respect to a given set is the dissimilarity that ranks number k when we sort, in increasing order, the dissimilarity value of the points in the set with respect to the query point. A multiple kth smallest dissimilarity query determines the kth smallest dissimilarity for several query points simultaneously. Although the problem of solving multiple kth smallest dissimilarity queries is an important primitive operation used in many areas, such as spatial data analysis, facility location, text classification and content-based image retrieval, it has not been previously addressed explicitly in the literature. In this paper we present three parallel strategies, to be run on a Graphics Processing Unit, for computing multiple kth smallest dissimilarity queries when non-metric dissimilarities, that do not satisfy the triangular inequality, are used. The strategies are theoretically and experimentally analyzed and compared among them and with an efficient sequential strategy to solve the problem
Work partially supported by the Spanish Ministerio de Economía y Competitividad under Grant TIN2014-52211-C2-2-R. We also gratefully acknowledge the support of NVIDIA Corporation with the donation of the Tesla K40 GPU used for this research
Format: application/pdf
Accés al document: http://hdl.handle.net/10256/12561
Llenguatge: eng
Editor: Elsevier
Col·lecció: info:eu-repo/semantics/altIdentifier/doi/10.1016/j.ins.2016.03.054
info:eu-repo/semantics/altIdentifier/issn/0020-0255
És part de: info:eu-repo/grantAgreement/MINECO//TIN2014-52211-C2-2-R/ES/GENERACION, SIMULACION Y VISUALIZACION DE MODELOS 3D A PARTIR DE GRANDES CONJUNTOS DE DATOS. APLICACIONES EN LA MEJORA DE LA CALIDAD DE VIDA DE LAS PERSONAS Y SU ENTORNO/
Drets: Tots els drets reservats
Matèria: Infografia
Computer graphics
Sistemes d’ajuda a la decisió
Decision support system
Títol: Solving multiple kth smallest dissimilarity queries for non-metric dissimilarities with the GPU
Tipus: info:eu-repo/semantics/article
Repositori: DUGiDocs

Matèries

Autors