Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams

Hoang Ta, Hoa T. Vu

We establish nearly optimal upper and lower bounds for approximating decision tree splits in data streams. For regression with labels in the range $\{0,1,\dots ,M\}$, we give a one…