# Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 8 Feb 2023.

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

- [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)
- [Fully-Dynamic Decision Trees](https://mlsanity.com/paper/2212.00778/) (2022)

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

- [Approximating splits for decision trees quickly in sparse data streams](https://mlsanity.com/paper/2601.12525/) (2026)

## Abstract (arXiv)

We give the first algorithm that maintains an approximate decision tree over an arbitrary sequence of insertions and deletions of labeled examples, with strong guarantees on the worst-case running time per update request. For instance, we show how to maintain a decision tree where every vertex has Gini gain within an additive α of the optimum by performing OBig(fracd,(log n)4α3Big) elementary operations per update, where d is the number of features and n the maximum size of the active set (the net result of the update requests). We give similar bounds for the information gain and the variance gain. In fact, all these bounds are corollaries of a more general result, stated in terms of decision rules -- functions that, given a set S of labeled examples, decide whether to split S or predict a label. Decision rules give a unified view of greedy decision tree algorithms regardless of the example and label domains, and lead to a general notion of ε-approximate decision trees that, for natural decision rules such as those used by ID3 or C4.5, implies the gain approximation guarantees above. The heart of our work provides a deterministic algorithm that, given any decision rule and any ε > 0, maintains an ε-approximate tree using O!left(fracd, f(n)n operatornamepolyfrachεright) operations per update, where f(n) is the complexity of evaluating the rule over a set of n examples and h is the maximum height of the maintained tree.