An Improved GPU-based Algorithmfor Processing the k Nearest Neighbor Query

Abstract

The k Nearest Neighbor (k-NN) query is a common spatial query that appears in several big data applications. We propose and implement a new GPU-based algorithm for the k-NN query, which improves our previous Symmetric Progression Partitioning method (SPP) by adding a heap buffer. We experimentally prove that the addition of heap speeds up the k-NN query, especially in larger values of k. Using random, synthetic and real datasets, we present an extensive experimental performance comparison against two of our algorithms. This comparison shows that the new algorithm excels in all the conducted experiments. © 2020 ACM.