Buffer k-d trees: processing massive nearest neighbor queries on GPUs

TY - GEN

T1 - Buffer k-d trees

T2 - International Conference on Machine Learning 2014

AU - Gieseke, Fabian Cristian

AU - Heinermann, Justin

AU - Oancea, Cosmin Eugen

AU - Igel, Christian

N1 - Conference code: 31

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

M3 - Article in proceedings

T3 - JMLR: Workshop and Conference Proceedings

BT - Proceedings of the 31st International Conference on Machine Learning, Beijing, China, 2014

Y2 - 21 June 2014 through 26 June 2014

ER -