fulltext.study @t Gmail

Efficient multiple bichromatic mutual nearest neighbor query processing

Paper ID Volume ID Publish Year Pages File Format Full-Text
396465 670346 2016 19 PDF Available
Title
Efficient multiple bichromatic mutual nearest neighbor query processing
Abstract

•We define and motivate multiple mutual bichromatic weighted nearest neighbor queries.•We solve 2d multiple mutual nearest neighbor queries sequentially and parallelly.•We theoretically analyze and compare the time and space complexity of both algorithms.•We experimentally show the algorithms to be effective, robust and scalable.

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′)(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′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.

Keywords
Computer science; Decision-making support system; Bichromatic mutual nearest neighbor query; Graphics Processing Unit (GPU)
First Page Preview
Efficient multiple bichromatic mutual nearest neighbor query processing
Publisher
Database: Elsevier - ScienceDirect
Journal: Information Systems - Volume 62, December 2016, Pages 136–154
Authors
, ,
Subjects
Physical Sciences and Engineering Computer Science Artificial Intelligence