Yggdrasil: An Optimized System for Training Deep Decision Trees at Scale
Deep distributed decision trees and tree ensembles have grown in importance due to the need to model increasingly large datasets. However, PLANET, the standard distributed tree learning algorithm implemented in systems such as XGBOOST and Spark MLLIB, scales poorly as data dimensionality and tree depths grow. We present YGGDRASIL, a new distributed tree learning method that outperforms existing methods by up to 24×. Unlike PLANET, YGGDRASIL is based on vertical partitioning of the data (i.e., partitioning by feature), along with a set of optimized data structures to reduce the CPU and communication costs of training. YGGDRASIL (1) trains directly on compressed data for compressible features and labels; (2) introduces efficient data structures for training on uncompressed data; and (3) minimizes communication between nodes by using sparse bitvectors. Moreover, while PLANET approximates split points through feature binning, YG-GDRASIL does not require binning, and we analytically characterize the impact of this approximation. We evaluate YGGDRASIL against the MNIST 8M dataset and a high-dimensional dataset at Yahoo; for both, YGGDRASIL is faster by up to an order of magnitude.
This paper presents a new system for performing distributed computing in an efficient way for decision trees. This is done in a classical master-workers setting. Compared to Planet, the algorithm used in standard implementation, the proposed method splits data vertically, distributing distinct features to workers (as opposed to distributing learning instances). The purpose of the method is to solve the bottleneck created by the expensive communication necessary for horizontal approaches (like Planet), scaling up to a larger number of features and bigger decision trees.
The paper is well written, and its structure is adapted to the content. Upon reading the paper, one might think that the contribution resides in the vertical splitting of the data over the workers, but the state of the art study presented later on shows that this idea by itself is not new. The novelty comes from associating it with data also distributed vertically, sparse bit vectors for inter-node communications, feature compression with custom data structures and training on compressed data. The paper shows formally and experimentally how the proposed heuristics significantly improve the communication between the nodes and speed up training.  The remark that using run-length encoding for the features allows them to hold in the L3 cache, thus decreasing the number of DRAM accesses, doesn't seem to always be true. The paper should explain in which conditions this is true (size of the cache, size of the data, number and type of features, etc.).  The heuristics are presented for a fixed type of architecture: one master connected to a certain number of workers in a star configuration. Is this the only setting used for large scale distributed computing, in machine learning or fields with similar needs? Would changing this architecture remove some of the existing bottlenecks?  The experimental results compare Yggdrasil against different implementations of Planet. On the two datasets the method shows important improvements in the computation time compared to other methods. Here, each of the datasets is used for a different task (classification and regression), so it is hard to tell if the speed gain is general or specific to the dataset and the task. It would be useful to see the performance of Yggdrasil on some other datasets as well.  Yggdrasil could be of impact in the community making use of distributed architectures. While the experimental results show a clear improvement over state of the art methods, they would be more convincing over a larger number of datasets.  Minor remarks: I am not sure that the NIPS format allows to surround figures (Figure 3 in this case) with text. End of Eq. (1): x should maybe be in bold?