Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs


Fabian Gieseke, Justin Heinermann, Cosmin Oancea, Christian Igel ;
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):172-180, 2014.


We present a new approach for combining k-d trees and graphics processing units for nearest neighbor search. It is well known that a direct combination of these tools leads to a non-satisfying performance due to conditional computations 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 subdivision induced by k-d trees and the huge computational resources provided by today’s many-core devices. We demonstrate the potential of our approach in astronomy, where hundreds of million nearest neighbor queries have to be processed.

Related Material