Ítem


Efficient multiple bichromatic mutual nearest neighbor query processing

In this paper we propose, motivate and solve multiple bichromatic mutual nearest neighbor queries in the plane considering multiplicative weighted Euclidean distances. Given two sets of facilities of different types, a multiple bichromatic mutual (k,k′)-nearest neighbor query finds pairs of points, one of each set, such that the point of the first set is a k -nearest neighbor of the point of the second set and, at the same time, the point of the second set is a k′-nearest neighbor of the point of the first set. These queries find applications in collaborative marketing and prospective data analysis, where facilities of one type cooperate with facilities of the other type to obtain reciprocal benefits. We present a sequential and a parallel algorithm, to be run on the CPU and on a Graphics Processing Unit, respectively, for solving multiple bichromatic mutual nearest neighbor queries. We also present the time and space complexity analysis of both algorithms, together with their theoretical comparison. Finally, we provide and discuss experimental results obtained with the implementation of the proposed sequential and a parallel algorithm

Work partially supported by the Spanish Ministerio de Economía y Competitividad under grant TIN2014-52211-C2-2-R

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: desembre 2016
Resum: In this paper we propose, motivate and solve multiple bichromatic mutual nearest neighbor queries in the plane considering multiplicative weighted Euclidean distances. Given two sets of facilities of different types, a multiple bichromatic mutual (k,k′)-nearest neighbor query finds pairs of points, one of each set, such that the point of the first set is a k -nearest neighbor of the point of the second set and, at the same time, the point of the second set is a k′-nearest neighbor of the point of the first set. These queries find applications in collaborative marketing and prospective data analysis, where facilities of one type cooperate with facilities of the other type to obtain reciprocal benefits. We present a sequential and a parallel algorithm, to be run on the CPU and on a Graphics Processing Unit, respectively, for solving multiple bichromatic mutual nearest neighbor queries. We also present the time and space complexity analysis of both algorithms, together with their theoretical comparison. Finally, we provide and discuss experimental results obtained with the implementation of the proposed sequential and a parallel algorithm
Work partially supported by the Spanish Ministerio de Economía y Competitividad under grant TIN2014-52211-C2-2-R
Format: application/pdf
Accés al document: http://hdl.handle.net/10256/13154
Llenguatge: eng
Editor: Elsevier
Col·lecció: info:eu-repo/semantics/altIdentifier/doi/10.1016/j.is.2016.07.003
É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: Sistemes d’ajuda a la decisió
Decision support system
Infografia
Computer graphics
Títol: Efficient multiple bichromatic mutual nearest neighbor query processing
Tipus: info:eu-repo/semantics/article
Repositori: DUGiDocs

Matèries

Autors