Buffer K-D Trees: Processing Massive Nearest Neighbor Queries on GPUs
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.
Cite
Text
Gieseke et al. "Buffer K-D Trees: Processing Massive Nearest Neighbor Queries on GPUs." International Conference on Machine Learning, 2014.Markdown
[Gieseke et al. "Buffer K-D Trees: Processing Massive Nearest Neighbor Queries on GPUs." International Conference on Machine Learning, 2014.](https://mlanthology.org/icml/2014/gieseke2014icml-buffer/)BibTeX
@inproceedings{gieseke2014icml-buffer,
title = {{Buffer K-D Trees: Processing Massive Nearest Neighbor Queries on GPUs}},
author = {Gieseke, Fabian and Heinermann, Justin and Oancea, Cosmin and Igel, Christian},
booktitle = {International Conference on Machine Learning},
year = {2014},
pages = {172-180},
volume = {32},
url = {https://mlanthology.org/icml/2014/gieseke2014icml-buffer/}
}