# Fully-Dynamic Decision Trees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 1 Dec 2022.

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

- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [TRI`EST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size](https://mlsanity.com/paper/1602.07424/) (2016)
- [Fully-Dynamic Coresets](https://mlsanity.com/paper/2004.14891/) (2020)
- [Dynamic Model Tree for Interpretable Data Stream Learning](https://mlsanity.com/paper/2203.16181/) (2022)
- [Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams](https://mlsanity.com/paper/1504.02268/) (2015)
- [Near-Optimal Fully Dynamic Densest Subgraph](https://mlsanity.com/paper/1907.03037/) (2019)
- [An Eager Splitting Strategy for Online Decision Trees](https://mlsanity.com/paper/2010.10935/) (2020)
- [Optimal Fully Dynamic k-Centers Clustering](https://mlsanity.com/paper/2112.07050/) (2021)

## Built on by (most cited first, 2 of 2)

- [Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees](https://mlsanity.com/paper/2302.03994/) (2023)
- [Approximating splits for decision trees quickly in sparse data streams](https://mlsanity.com/paper/2601.12525/) (2026)

## Abstract (arXiv)

We develop the first fully dynamic algorithm that maintains a decision tree over an arbitrary sequence of insertions and deletions of labeled examples. Given ε > 0 our algorithm guarantees that, at every point in time, every node of the decision tree uses a split with Gini gain within an additive ε of the optimum. For real-valued features the algorithm has an amortized running time per insertion/deletion of Obig(fracd log3 nε2big), which improves to Obig(fracd log2 nεbig) for binary or categorical features, while it uses space O(n d), where n is the maximum number of examples at any point in time and d is the number of features. Our algorithm is nearly optimal, as we show that any algorithm with similar guarantees uses amortized running time Omega(d) and space tildeOmega (n d). We complement our theoretical results with an extensive experimental evaluation on real-world data, showing the effectiveness of our algorithm.