  In this work, we provide data stream algorithms that compute optimal splits
in decision tree learning. In particular, given a data stream of observations
$x_i$ and their labels $y_i$, the goal is to find the optimal split point $j$
that divides the data into two sets such that the mean squared error (for
regression) or misclassification rate (for classification) is minimized. We
provide various fast streaming algorithms that use sublinear space and a small
number of passes for these problems. These algorithms can also be extended to
the massively parallel computation model. Our work, while not directly
comparable, complements the seminal work of Domingos and Hulten (KDD 2000).
