Meeting the challenges of k-nearest neighbor search implementation for GPU accelerators

• Thesis title in Czech: Analýza a řešení výzev implementace vyhledávání k nejbližších sousedů pro GPU akcelerátory
• Thesis title in English: Meeting the challenges of k-nearest neighbor search implementation for GPU accelerators
• Key words: kNN|top-k|parallel|GPU|CUDA
• English key words: kNN|top-k|parallel|GPU|CUDA
• Academic year of topic announcement: 2021/2022
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Distributed and Dependable Systems (32-KDSS)
• Supervisor: doc. RNDr. Martin Kruliš, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 01.11.2021
• Date of assignment: 02.11.2021
• Confirmed by Study dept. on: 10.11.2021
• Date and time of defence: 06.09.2023 09:00
• Date of electronic submission: 18.07.2023
• Date of submission of printed version: 24.07.2023
• Date of proceeded defence: 06.09.2023
• Opponents: RNDr. Jakub Yaghob, Ph.D.

Guidelines

The k-nearest neighbor search (or the top-k problem) is well established search pattern known to database systems, but also integrated in many data processing and data analysis algorithms (k-means clustering, self-organized maps training, permutation-based indexing, etc.). Although its sequential implementation is trivial and typically based on basic data structures like regular heaps, its concurrent implementation brings many challenges. These challenges become even more profound in many-core parallel systems like GPU accelerators. There are many techniques that can be used to mitigate these challenges such as data privatization and parallel reduction and many research publications have address this topic; however, no publications proposed universal solution or complex performance overview of various problem configurations. The main objective of this thesis is to explore existing solutions for GPU-based top-k selection, perform their empirical evaluation, and propose universal solution for all possible scenarios. Furthermore, it is expected that additional performance optimizations may be discovered during the exploration.

References

V. Garcia, E. Debreuve, and M. Barlaud. Fast k nearest neighbor search using gpu. In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pages 1-6. IEEE, 2008.

M. Krulis, H. Osipyan, and S. Marchand-Maillet. Optimizing sorting and top-k selection steps in permutation based indexing on gpus. In East European Conference on Advances in Databases and Information Systems, pages 305{317. Springer, 2015.

M. Krulis and M. Kratochvil. Detailed analysis and optimization of cuda k-means algorithm. In 49th International Conference on Parallel Processing - ICPP '20, New York, NY, USA, 2020. Association for Computing Machinery.

S. Li and N. Amenta. Brute-force k-nearest neighbors search on the gpu. In International Conference on Similarity Search and Applications, pages 259-270. Springer, 2015.

X. Tang, Z. Huang, D. Eyers, S. Mills, and M. Guo. Efficient selection algorithm for fast k-nn search on gpus. In 2015 IEEE International Parallel and Distributed Processing Symposium, pages 397-406. IEEE, 2015.