Abstract

Nowadays, searching algorithms are a key component in modern computer science applications. However, traditional approaches of exact search techniques are practicallyan unfeasible solution with the rise of data in high-dimensional databases. The kNN algorithm is frequently used in content based information retrieval systems as it returns similar object sand classifies them. Exhaustive sorting algorithms, such as those based on kNN, can be implemented using a Heap, reducing the computational complexity of the search process. In the present study, we analyze the efficiency of using the Heap data structure on GPUs for solving kNN queries, analyzing the performance of this type of structure as a function of the number of children in the structure. The best results were achieved by increasing the number of children, reaching a speed-up of 1.45x using aternary Heap. The source codes used for the experimentation willbe available to the scientific community in a GitHub repository:https://github.com/ruberhg/GPU-Heaps.