A method training a randomized decision tree through multiple iterations, each is based on: a) Receiving multiple data samples that include data subsets, each data subset corresponds to an attribute. b) Distributing the data subsets to slave processing units after sorting the data samples in consecutive ascending order by updating a first index that identifies trajectories of the training data samples through the tree nodes of the previous tree level. c) Simultaneously processing the data subsets to identify split functions for each tree node with respect to each data subset and updating a second index that identifies the trajectories of the training data samples through the tree node of the current tree level. d) Collecting the split functions from the slave processing units and constructing the current tree level by selecting a preferred split function for each tree node of the current tree level.