Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs
Fabian Cristian Gieseke, Justin Heinermann, Cosmin E. Oancea, Christian Igel · 2014
We present a new approach for combining k-d trees and graphics processing units for near-est neighbor search. It is well known that a di-rect combination of these tools leads to a non-satisfying performance due to conditional com-putations and suboptimal memory accesses. To alleviate these problems, we propose a variant of the classical k-d tree data structure, called buffer k-d tree, which can be used to reorganize the search. Our experiments show that we can take advantage of both the hierarchical subdivi-sion induced by k-d trees and the huge computa-tional resources provided by today’s many-core devices. We demonstrate the potential of our ap-proach in astronomy, where hundreds of million nearest neighbor queries have to be processed. 1.