# Constructing Decision Trees from Data Streams

arXiv: https://arxiv.org/abs/2403.19867 · HTML: https://mlsanity.com/paper/2403.19867/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 44 references that are in the map.
- First posted on arXiv 28 Mar 2024.

## Builds on (most cited first, 4 of 4)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Tabular Data: Deep Learning is Not All You Need](https://mlsanity.com/paper/2106.03253/) (2021)
- [River: machine learning for streaming data in Python](https://mlsanity.com/paper/2012.04740/) (2020)
- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)

## Abstract (arXiv)

In this work, we present data stream algorithms to compute optimal splits for decision tree learning. In particular, given a data stream of observations (xi) and their corresponding labels (yi), without the i.i.d. assumption, the objective is to identify the optimal split (j) that partitions the data into two sets, minimizing the mean squared error (for regression) or the misclassification rate and Gini impurity (for classification). We propose several efficient streaming algorithms that require sublinear space and use a small number of passes to solve these problems. These algorithms can also be extended to the MapReduce model. Our results, while not directly comparable, complements the seminal work of Domingos-Hulten (KDD 2000) and Hulten-Spencer-Domingos (KDD 2001).