I'm concerned about the repeated filtering/caching happening at each pass. It would potentially slow things down for big datasets.

An alternative approach would be to set up one pass per tree level - at pass 1, we find the best split, at pass 2, we find the best two splits, at pass 3 we find the best 3 splits, etc. 

Each data item would get evaluated with 
1) The current model so far (so that it can find its place in the tree)
2) Plus every candidate split at the next level. 

The result of the map side would be a big vector that indicates #1 the point's current position in the tree, and #2 stats on where the point would end up for each candidate split, along with #3 its response value.

Finally, we could just do a big reduceByKey (which would just be a parallel entropy calculation, maybe even just a vector sum for gini) on #1, and pick our best split for each current position based on the result. This would eliminate the need for intermediate caching, and also allow us to add in a step of "sub-trees are small enough => train locally"