Fully-Dynamic Decision Trees

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.