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

Fabian Gieseke, Justin Heinermann, Cosmin Oancea, Christian Igel
Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark
Journal of Machine Learning Research W&CP 32 (1): 172-180, 2014


   title={Buffer kd Trees: Processing Massive Nearest Neighbor Queries on GPUs},

   author={Gieseke, Fabian and Heinermann, Justin and Oancea, Cosmin and Igel, Christian},

   booktitle={Proceedings of The 31st International Conference on Machine Learning},




Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: