Evaluating decision trees on a GPU
US8290882B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Oct 9, 2008 |
| Grant date | Oct 16, 2012 |
| Priority date | — |
| Expiry date | Aug 17, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06N20/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods and apparatus for evaluating decision trees on a GPU are described. In an embodiment, the structure of a decision tree is converted into a 2D “tree” array with each row representing a node in the tree. Each row comprises details of any child nodes and the parameters which are required to perform the binary test at the node. A pixel shader can then be used to evaluate the decision tree in parallel for each input data point in an input array by navigating through rows in the 2D tree array. For each row, data is read from the input array dependent upon the parameters in the row and the shader moves to another row dependent upon the result of the binary test. On reaching a row which represents a leaf node, the pixel shader outputs evaluation results, such as a leaf node index or a probability distribution over classes.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.