# Approximating splits for decision trees quickly in sparse data streams

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

## Key facts

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

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

- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [An Eager Splitting Strategy for Online Decision Trees](https://mlsanity.com/paper/2010.10935/) (2020)
- [Fully-Dynamic Decision Trees](https://mlsanity.com/paper/2212.00778/) (2022)
- [Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees](https://mlsanity.com/paper/2302.03994/) (2023)

## Abstract (arXiv)

Decision trees are one of the most popular classifiers in the machine learning literature. While the most common decision tree learning algorithms treat data as a batch, numerous algorithms have been proposed to construct decision trees from a data stream. A standard training strategy involves augmenting the current tree by changing a leaf node into a split. Here we typically maintain counters in each leaf which allow us to determine the optimal split, and whether the split should be done. In this paper we focus on how to speed up the search for the optimal split when dealing with sparse binary features and a binary class. We focus on finding splits that have the approximately optimal information gain or Gini index. In both cases finding the optimal split can be done in O(d) time, where d is the number of features. We propose an algorithm that yields (1 + α) approximation when using conditional entropy in amortized O(α-1(1 + mlog d) log log n) time, where m is the number of 1s in a data point, and n is the number of data points. Similarly, for Gini index, we achieve (1 + α) approximation in amortized O(α-1 + m log d) time. Our approach is beneficial for sparse data where m ll d. In our experiments we find almost-optimal splits efficiently, faster than the baseline, overperforming the theoretical approximation guarantees.