Characterization of Parallelism Techniques for Decision Tree Ensembles

Ensembles of decision trees enhance accuracy of individual decision trees by combining the predictions of multiple trees. Recent research accelerated inference for ensembles running on a single core. However, in most previous work, parallelism is either not sufficiently explored or assumed to be trivial in ensembles. Novel data structures introduced in previous can support well known methods to parallelize inference, i.e., data parallelism and model parallelism. In addition, ensembles also support another method of parallelism: structure parallelism. In structure parallelism, portions of a restructured forest are distributed across cores, enabling parallelism even in the execution of a single sample. We compared the different methods for parallelizing ensembles and showed that structure parallelism can be $\mathbf{4 2 \%}$ faster than existing methods alone.