Search Machine Learning Repository:
Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs
Authors: Fabian Gieseke, Justin Heinermann, Cosmin Oancea and Christian Igel
Conference: Proceedings of the 31st International Conference on Machine Learning (ICML-14)
Abstract: 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.
authors venues years
Suggest Changes to this paper.
Brought to you by the WUSTL Machine Learning Group. We have open faculty positions (tenured and tenure-track).