A comparative study of k nearest neighbor computations on GPUs and CPUs

Sammanfattning: The problem of nearest neighbors search arises in many areas of computer science. This search could see a performance boost if implemented on a GPU, utilizing its multithreading capabilities, compared to the sequential execution on a CPU. The purpose of this report is to invesigate how a simple GPU implementation of k nearest neighbors search compares to other common algorithms on a CPU. A brute force search on the GPU was implemented using NVIDIAs CUDA platform, and its performance was tested and compared to implementations from an existing library of both exact brute force search and approximate search on a CPU. Results show that the GPU brute force search achieves a significant increase in performance compared to its CPU counterpart, but it struggles to keep up with the approximate search as the amount of data increases.