Improvements to Algorithms for the Nearest Neighbor Problem with Cyclically Permuted Query Points

The nearest neighbor problem is concerned with finding, in a metric space, a number of training points closest to a set of query points. In this paper it is considered a variation of this problem, in which the smallest distance between a reference point and a training point is given by a pseudometric defined over all cyclic permutations of the query point. Some parallel CPU algorithms have been previously reported, but are difficult to implement due to the impossibility of using more threads than the number of query points. New GPU algorithms, multi-core and manycore, which exploit both coarse and fine-grained parallelism and allow the use of more threads than the number of query points are described. An extensive experimental study with the proposed algorithms demonstrates that large datasets can now be processed in reasonable computational time.