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

Marco Bressan, Mauro Sozio

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 wo…