Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs by Fabian Gieseke, Justin Heinermann, Cosmin Oancea, Christian Igel. (Journal of Machine Learning Research W&CP 32 (1): 172-180, 2014)
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.
The complexity of your data may or may not be a barrier to this technique. The authors report that for feature spaces < 4, specialized solutions exist and benefits exist for feature spaces up to 27.
Pure speculation on my part but it could be the case that some level of size or complexity of data, a general solution that is equally applicable to every data set, isn’t possible.
I first saw this in a tweet by Stefano Bertolo