Online Decision Tree
Online Decision Tree (Incremental / Streaming Decision Tree Learning) · Also known as: Hoeffding Tree, VFDT, Very Fast Decision Tree, incremental decision tree
An Online Decision Tree is a decision tree that grows incrementally from a continuous stream of data without revisiting past examples. The dominant algorithm, the Hoeffding Tree (VFDT), uses the Hoeffding bound to decide when enough examples have been seen at a node to split it confidently, enabling scalable, real-time classification on potentially infinite data streams.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use an online decision tree when data arrive as a continuous stream, when storing the full dataset is infeasible due to volume or privacy constraints, or when the model must be updated in real time with each new observation. It is well suited to IoT sensor streams, clickstream classification, fraud detection with evolving patterns, and any setting where concept drift is expected and the model must adapt without retraining from scratch. Do not use it when the dataset is small and static — a standard decision tree or random forest will be faster to implement and more accurate. Also avoid it if interpretability of the exact split thresholds is critical without accepting that thresholds may shift over time.
Strengths & limitations
- Processes data in a single pass with constant memory per node, scaling to theoretically infinite streams.
- Provides theoretical guarantees via the Hoeffding bound that splits are asymptotically identical to those of a batch tree given enough data.
- Can incorporate drift detectors to adapt to non-stationary distributions without full retraining.
- Delivers a usable model from the very first example, unlike batch methods that require a full dataset before producing any prediction.
- Naturally handles high-throughput settings where storing data is impractical or legally restricted.
- Accuracy on small datasets is typically lower than a batch decision tree because the Hoeffding bound requires many examples before early splits are made.
- Split decisions are irreversible in the basic algorithm; a poor early split can persist unless explicit subtree replacement is added.
- Tuning the confidence parameter delta and the grace period between split evaluations requires domain knowledge.
- Interpretability of the tree changes over time as new splits are added, making static reporting difficult.
Frequently asked
How is the Hoeffding Tree different from a standard CART decision tree?
A CART tree scans the full dataset at each node to find the globally best split. The Hoeffding Tree instead watches examples arrive one at a time, and only commits to a split when statistical theory guarantees the apparent winner would still win even with more data — using no stored raw examples.
Does the online decision tree handle concept drift?
The basic Hoeffding Tree does not detect drift automatically. Extensions such as the Concept-adapting Very Fast Decision Tree (CVFDT) and versions combined with ADWIN or Page-Hinkley drift detectors can replace outdated subtrees when drift is detected.
What is the grace period and how should I set it?
The grace period is the number of examples arriving at a leaf between consecutive split evaluations. A larger value reduces computation but delays splits; a smaller value evaluates splits more often at higher CPU cost. Typical defaults range from 200 to 1000 examples.
Is the online decision tree appropriate for small, static datasets?
No. For small, fully available datasets a standard batch decision tree or random forest will almost always achieve better accuracy with far less complexity. Online trees are designed specifically for the streaming, large-scale, or resource-constrained regime.
How does accuracy compare to batch methods on a fixed dataset?
With enough data the Hoeffding Tree converges to the same tree a batch learner would produce, so accuracy eventually matches. Early in the stream, before leaves have seen many examples, accuracy is lower than a batch tree trained on the same data seen so far.
Sources
- Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM. link ↗
- Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM. DOI: 10.1145/502512.502529 ↗
How to cite this page
ScholarGate. (2026, June 3). Online Decision Tree (Incremental / Streaming Decision Tree Learning). ScholarGate. https://scholargate.app/en/machine-learning/online-decision-tree
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Decision TreeMachine learning↔ compare
- Online Gradient BoostingMachine learning↔ compare
- Online LearningMachine learning↔ compare
- Online Naive BayesMachine learning↔ compare
- Online Random ForestMachine learning↔ compare
- Semi-supervised Decision TreeMachine learning↔ compare