Implementing Decision Trees and Forests on a GPU

Toby Sharp
Microsoft Research, Cambridge, UK
Computer Vision ECCV 2008 (2008), pp. 595-608.


   title={Implementing decision trees and forests on a gpu},

   author={Sharp, T.},

   journal={Computer Vision–ECCV 2008},





Download Download (PDF)   View View   Source Source   



We describe a method for implementing the evaluation and training of decision trees and forests entirely on a GPU, and show how this method can be used in the context of object recognition. Our strategy for evaluation involves mapping the data structure describing a decision forest to a 2D texture array. We navigate through the forest for each point of the input data in parallel using an efficient, non-branching pixel shader. For training, we compute the responses of the training data to a set of candidate features, and scatter the responses into a suitable histogram using a vertex shader. The histograms thus computed can be used in conjunction with a broad range of tree learning algorithms. We demonstrate results for object recognition which are identical to those obtained on a CPU, obtained in about 1% of the time. To our knowledge, this is the first time a method has been proposed which is capable of evaluating or training decision trees on a GPU. Our method leverages the full parallelism of the GPU. Although we use features common to computer vision to demonstrate object recognition, our framework can accommodate other kinds of features for more general utility within computer science.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: