  We introduce a novel incremental decision tree learning algorithm, Hoeffding
Anytime Tree, that is statistically more efficient than the current
state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of
Hoeffding Anytime Tree---"Extremely Fast Decision Tree", a minor modification
to the MOA implementation of Hoeffding Tree---obtains significantly superior
prequential accuracy on most of the largest classification datasets from the
UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in
the limit, is naturally resilient to concept drift, and can be used as a higher
accuracy replacement for Hoeffding Tree in most scenarios, at a small
additional computational cost.
