Mining time-changing data streams

Geoff HultenLaurie SpencerPedro M. Domingos

article2001KDD1,952 citations

Develops CVFDT, an incremental decision tree algorithm that adapts to concept drift in high-speed data streams in constant time per example by dynamically maintaining and swapping alternative subtrees as data distributions evolve.

Listen

Modern data-driven organizations increasingly rely on continuous, high-volume data streams generated by web applications, sensors, and financial systems. Traditional machine learning algorithms typically assume stationary environments where the underlying data generation process remains constant over time. However, real-world data streams frequently experience concept drift, where statistical properties change dynamically. Existing streaming classification models either fail to adjust to these changes or rely on computationally expensive retraining over sliding windows, creating bottlenecks and reducing predictive accuracy over time.

The article introduces and evaluates the Concept-adapting Very Fast Decision Tree algorithm, an extension of the Very Fast Decision Tree stream-mining architecture. The primary objective is to demonstrate how decision tree models can continuously adapt to time-changing concept drift while processing extremely fast data streams in constant time per example and using bounded memory.

The authors evaluated the algorithm through systematic simulations on synthetic datasets with controlled drift rates, as well as an empirical evaluation on real-world web data consisting of user browsing traces from a major commercial website over a multi-week period. The core approach maintains statistical counts over a moving window of recent data, monitors the ongoing validity of split decisions across all tree nodes, and grows alternative subtrees in parallel when a split becomes sub-optimal. Once an alternative subtree outperforms the existing branch, it replaces it without halting stream processing.

The experimental findings show that the adaptive algorithm maintained substantially higher accuracy than non-adaptive stream models in dynamic environments, rapidly recovering from both abrupt and gradual concept drift. On synthetic benchmarks, the adaptive tree tracked concept shifts with negligible recovery lag, whereas stationary tree models suffered permanent accuracy degradation of up to several percentage points. On the web dataset, the algorithm adapted to shifting user browsing behaviors across several million page visits, maintaining a compact model size while achieving lower classification error than static baselines. Furthermore, the memory management and pruning mechanisms allowed the algorithm to process hundreds of thousands of examples per second without exhausting available memory.

These findings indicate that organizations managing continuous data feeds can maintain up-to-date predictive models with lower operational costs and minimal administrative intervention. By eliminating the need for periodic manual model rebuilding, systems can safely automate decisions in rapidly changing environments such as fraud detection, digital ad targeting, and dynamic network security.

For practical implementation, organizations should establish robust stream monitoring and calibrate the window size parameter to match the expected rate of drift in their domain, balancing sensitivity against statistical stability. Teams should initially pilot adaptive decision tree architectures on high-throughput, non-critical classification streams before full enterprise deployment. Further work is recommended to evaluate performance under extreme label latency, where true class labels arrive significantly after initial predictions are made.

A key limitation is that the model assumes class labels become available promptly to update internal node statistics and evaluate alternative subtrees. Additionally, the approach relies on user-defined window sizes, which may require tuning if drift rates fluctuate unpredictably. Despite these constraints, confidence in the results is high for high-speed streaming scenarios where concept changes occur across observable data attributes.

Innovation Next University of Washington association rules decision trees efficient algorithm mining time-changing data streams data streams

Hulten et al (2001).pdf

Paper: Mining high-speed data streams, Pedro Domingos et al. (2000). CVFDT directly extends the Very Fast Decision Tree (VFDT) algorithm introduced here to handle time-changing data distributions and concept drift.
Paper: Induction of Decision Trees, J. R. Quinlan (1986). This seminal work establishes the foundational principles of top-down decision tree induction and split selection heuristics underlying streaming tree models.

Paper: Learning with Drift Detection, João Gama et al. (2004). This paper builds on drift adaptation in streaming models by introducing a formal statistical error-rate monitoring method (DDM) to trigger model adaptation.
Paper: Learning from Time-Changing Data with Adaptive Windowing, Albert Bifet et al. (2007). This work introduces the ADWIN adaptive sliding window algorithm, advancing the fixed-window drift handling concepts used in CVFDT.
Paper: A Framework for Clustering Evolving Data Streams, Charu C. Aggarwal et al. (2003). CluStream extends the paradigm of mining evolving, time-changing data streams from decision tree classification to dynamic stream clustering.
Paper: Learning under Concept Drift: A Review, Jie Lu et al. (2019). This survey provides a comprehensive review of modern concept drift detection, understanding, and adaptation frameworks that evolved from foundational streaming algorithms like CVFDT.

Cover for Mining time-changing data streams

Abstract

Most statistical and machine-learning algorithms assume that the data is a random sample drawn from a stationary distribution. Unfortunately, most of the large databases available for mining today violate this assumption. They were gathered over months or years, and the underlying processes generating them changed during this time, sometimes radically. Although a number of algorithms have been proposed for learning time-changing concepts, they generally do not scale well to very large databases. In this paper we propose an efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast VFDT decision tree learner. This algorithm, called CVFDT, stays current while making the most of old data by growing an alternative subtree whenever an old one becomes questionable, and replacing the old with the new when the new becomes more accurate. CVFDT learns a model which is similar in accuracy to the one that would be learned by reapplying VFDT to a moving window of examples every time a new example arrives, but with O(1) complexity per example, as opposed to O(w), where w is the size of the window. Experiments on a set of large time-changing data streams demonstrate the utility of this approach.

Topics

association rules decision trees efficient algorithm stationary distribution data stream mining multiple data streams adaptive algorithms optimization problems integrated data

Keywords

mining time-changing data streams data streams

Mining Time-Changing Data Streams
1. INTRODUCTION
Categories and Subject Descriptors
General Terms
2. THE VFDT SYSTEM
4. EMPIRICAL STUDY
4.1 Synthetic Data
4.2 Web Data
5. RELATED WORK
6. FUTURE WORK
7. CONCLUSION
8. ACKNOWLEDGMENTS
9. REFERENCES

Knowls

Knowl 1 — CVFDT Algorithm for Decision Tree Induction over Concept-Drifting Data Streams
algorithm
The CVFDT (Concept-adapting Very Fast Decision Tree) learner induces and maintains a decision tree classifier over continuous, high-speed data streams subject to concept drift. It maintains sufficient statistics matching a sliding window of the most recent $w$ examples without retraining from scratch, continuously monitors existing internal node splits for validity using Hoeffding bounds, and initiates and evaluates alternate subtrees whenever an old split becomes questionable.
Input:
   $S$ : Stream of training examples $(x, y)$
   $X$ : Set of symbolic candidate attributes
   $G(\cdot)$ : Split evaluation heuristic function (e.g., Information Gain)
   $\delta$ : Desired maximum probability of choosing an incorrect attribute at any split
   $\tau$ : Attribute tie-breaking threshold
   $w$ : Sliding window size (maximum number of examples maintained)
   $n_{min}$ : Frequency (in number of examples seen) between split validity checks
   $f$ : Frequency (in number of examples seen) between tree-wide drift checks
Output:
   $HT$ : Concept-adapted decision tree model
Procedure CVFDT( $S, X, G, \delta, \tau, w, n_{min}, f$ ):
  Let $HT$ be a decision tree with a single leaf node $l_1$ (the root)
  Let $ALT(l_1) = \emptyset$ (set of alternate subtrees for $l_1$ )
  Let $G_1(X_\emptyset)$ be the heuristic value obtained by predicting the most frequent class in $S$
  Let $X_1 = X \cup \{X_\emptyset\}$
  Let $W = \emptyset$ (sliding window queue of tuples $((x, y), ID)$ )
  Initialize counts $n_{ijk}(l_1) = 0$ for each class $y_k$ , attribute $X_i \in X$ , and value $x_{ij}$

  for each example $(x, y)$ in stream $S$ :
    Sort $(x, y)$ into leaves $L$ using $HT$ and all trees in $ALT(l)$ for every node $l$ traversed
    Let $ID$ be the maximum identifier among all leaves in $L$
    Add $((x, y), ID)$ to the beginning of $W$
    if $|W| > w$ :
      Let $((x_w, y_w), ID_w)$ be the oldest element of $W$
      ForgetExample( $HT, n, (x_w, y_w), ID_w$ )
      Remove $((x_w, y_w), ID_w)$ from $W$
    CVFDTGrow( $HT, n, G, (x, y), \delta, n_{min}, \tau$ )
    if $f$ examples have arrived since the last drift check:
      CheckSplitValidity( $HT, n, \delta$ )
  return $HT$
Knowl 2 — Alternate Subtree Generation, Evaluation, and Replacement in CVFDT
algorithm
CVFDT maintains validity of tree splits under concept drift by periodically scanning all internal nodes in the main decision tree $HT$ and any existing alternate subtrees. When sufficient statistics within the sliding window indicate that an existing split at node $l$ on attribute $X_n$ is no longer optimal (i.e., a different attribute $X_a$ achieves significantly higher split metric $G$ such that $\Delta \overline{G} = \overline{G}_l(X_a) - \overline{G}_l(X_n) > \epsilon$ or ties with $\epsilon < \tau$ ), CVFDT spawns an alternate subtree rooted at $l$ that splits on $X_a$ .
Procedure CheckSplitValidity( $HT, n, \delta$ ):
  for each node $l \in HT$ that is not a leaf:
    for each tree $T_{alt} \in ALT(l)$ :
      CheckSplitValidity( $T_{alt}, n, \delta$ )
    Let $X_n$ be the split attribute at node $l$
    Let $X_a$ be the attribute with highest heuristic evaluation $\overline{G}_l$ other than $X_n$
    Let $X_b$ be the attribute with second-highest heuristic evaluation $\overline{G}_l$ other than $X_n$
    Let $\Delta \overline{G}_l = \overline{G}_l(X_a) - \overline{G}_l(X_b)$
    if $\Delta \overline{G}_l \ge 0$ and no tree in $ALT(l)$ already splits on $X_a$ at its root:
      Compute $\epsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2 n_l}}$ using total count $n_l$ at node $l$
      if $(\Delta \overline{G}_l > \epsilon)$ or $(\epsilon < \tau \text{ and } \Delta \overline{G}_l \ge \tau / 2)$ :
        Let $l_{new}$ be an internal node that splits on $X_a$
        Let $ALT(l) = ALT(l) \cup \{l_{new}\}$
        for each branch of the split on $X_a$ :
          Add a new leaf $l_m$ to $l_{new}$ with candidate attributes $X_m = X - \{X_a\}$
          Let $ALT(l_m) = \emptyset$
          Initialize leaf counts $n_{ijk}(l_m) = 0$
Alternate subtrees $T_{alt} \in ALT(l)$ are grown concurrently with the main tree using incoming stream examples. Periodically, each alternate subtree enters a testing phase over $m$ consecutive examples where its classification accuracy over the subtree rooted at $l$ is directly compared to that of the existing subtree at $l$ . If the alternate subtree is more accurate, the old subtree at $l$ is replaced by the alternate subtree. If an alternate subtree fails to demonstrate progress (its cumulative accuracy difference relative to the current tree does not improve), it is pruned to conserve memory.
Knowl 3 — Forgetting Expired Examples from Decision Tree Sufficient Statistics
algorithm
When sliding window capacity $w$ is reached, the oldest example $(x_w, y_w)$ must be removed from the sufficient statistics of all nodes it originally updated. Because the tree topology $HT$ and alternate subtrees $ALT$ may have grown or modified since $(x_w, y_w)$ arrived, each tree node is assigned a unique, monotonically increasing integer identifier $ID$ upon creation.

When $(x, y)$ is initially processed, the maximum $ID$ among all leaf nodes it traverses across $HT$ and all $ALT$ subtrees is recorded as $ID_w$ . When forgetting $(x_w, y_w)$ , the traversal only traverses nodes with identifier $id \le ID_w$ , ensuring the statistics decrements match exactly the nodes visited when $(x_w, y_w)$ was inserted.
Procedure ForgetExample( $HT, n, (x_w, y_w), ID_w$ ):
  Sort $(x_w, y_w)$ through $HT$ , traversing only nodes with node identifier $id \le ID_w$
  Let $P$ be the set of nodes traversed in the sort
  for each node $l$ in $P$ :
    for each attribute value $x_{ij} \in x_w$ such that $X_i \in X_l$ :
      Decrement sufficient statistic count: $n_{ijk}(l) \leftarrow n_{ijk}(l) - 1$
    for each alternate tree $T_{alt} \in ALT(l)$ :
      ForgetExample( $T_{alt}, n, (x_w, y_w), ID_w$ )
Knowl 4 — CVFDT Tree Growth and Split Selection
algorithm
CVFDT grows decision trees incrementally at active leaf nodes while simultaneously updating statistics across internal nodes and alternate subtrees:
Procedure CVFDTGrow( $HT, n, G, (x, y), \delta, n_{min}, \tau$ ):
  Sort $(x, y)$ into a leaf $l$ using $HT$
  Let $P$ be the sequence of nodes traversed in the sort
  for each node $l_{pi} \in P$ :
    for each $x_{ij}$ in $x$ such that $X_i \in X_{l_{pi}}$ :
      Increment sufficient statistic count: $n_{ijk}(l_{pi}) \leftarrow n_{ijk}(l_{pi}) + 1$
    for each tree $T_a \in ALT(l_{pi})$ :
      CVFDTGrow( $T_a, n, G, (x, y), \delta, n_{min}, \tau$ )
  Label leaf $l$ with the majority class among examples seen at $l$
  Let $n_l$ be the number of examples observed at leaf $l$
  if examples seen at $l$ are not all of the same class and $n_l \equiv 0 \pmod{n_{min}}$ :
    Compute heuristic $\overline{G}_l(X_i)$ for each candidate attribute $X_i \in X_l - \{X_\emptyset\}$ using counts $n_{ijk}(l)$
    Let $X_a$ be the attribute with highest heuristic evaluation $\overline{G}_l$
    Let $X_b$ be the attribute with second-highest heuristic evaluation $\overline{G}_l$
    Compute $\epsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2 n_l}}$
    Let $\Delta \overline{G}_l = \overline{G}_l(X_a) - \overline{G}_l(X_b)$
    if $(\Delta \overline{G}_l > \epsilon \text{ or } (\Delta \overline{G}_l \le \epsilon < \tau)) \text{ and } X_a \ne X_\emptyset$ :
      Replace leaf $l$ by an internal node that splits on attribute $X_a$
      for each branch value of the split on $X_a$ :
        Add a new leaf $l_m$ with candidate attribute set $X_m = X - \{X_a\}$
        Let $ALT(l_m) = \emptyset$
        Let $\overline{G}_m(X_\emptyset)$ be the heuristic value obtained by predicting majority class at $l_m$
        Initialize counts $n_{ijk}(l_m) = 0$ for all classes $y_k$ and values $x_{ij}$ of $X_i \in X_m - \{X_\emptyset\}$
Knowl 5 — Time and Memory Complexity of CVFDT vs. VFDT-Window
theoretical result
For a data stream characterized by $d$ attributes, maximum attribute value count $v$ , and $c$ distinct target classes:
- Per-Example Processing Time: CVFDT requires $O(l_c \cdot d \cdot v \cdot c)$ time per incoming training example, where $l_c$ is the length of the longest path traversed by an example through the main decision tree $HT$ and all active alternate subtrees $ALT$ . In practice, $l_c$ is comparable to the maximum depth of the main tree $l_v$ .
- Retraining vs. Incremental Sliding Window: Re-running an incremental tree learner (such as VFDT) over a sliding window of size $w$ whenever a new example arrives requires $O(w \cdot l_v \cdot d \cdot v \cdot c)$ time per example (a factor of $w \cdot l_v / l_c$ larger than CVFDT).
- Memory Consumption: CVFDT memory is dominated by the sufficient statistics tables kept at every node across the main tree and all active alternate subtrees, requiring $O((|HT| + \sum |ALT|) \cdot d \cdot v \cdot c)$ space. The memory is independent of the total stream length and does not require storing individual historical examples in RAM if window samples $W$ are stored on secondary disk storage.
Knowl 6 — Hoeffding Bound for Stream-Based Decision Tree Attribute Split Decisions
equation
To decide whether the best candidate attribute $X_a$ is strictly superior to the second-best candidate attribute $X_b$ based on a sample of $n$ examples, the Hoeffding bound guarantees that the true difference between their split heuristic values $\Delta \overline{G} = \overline{G}(X_a) - \overline{G}(X_b)$ is within $\epsilon$ of the sample mean difference with confidence $1 - \delta$ , independent of the underlying probability distribution:

$\epsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}$

where:
- $n \in \mathbb{N}^+$ is the number of examples observed at the node since split evaluation began,
- $\delta \in (0, 1)$ is a user-specified bound on the probability of committing an attribute selection error,
- $R \in \mathbb{R}^+$ is the range of the heuristic evaluation function $G(\cdot)$ (for information gain over $c$ classes, $R = \log_2 c$ ).
If the observed sample heuristic difference satisfies $\Delta \overline{G} > \epsilon$ , then with confidence $1 - \delta$ the true heuristic difference is strictly positive ( $\Delta G > 0$ ), justifying an immediate split on attribute $X_a$ .
Knowl 7 — Rotating Hyperplane Synthetic Benchmark for Concept-Drifting Data Streams
experimental setup
A synthetic data stream benchmark for evaluating classification performance under controlled concept drift is defined by a $d$ -dimensional rotating hyperplane decision boundary:

$\sum_{i=1}^d w_i x_i = w_0$

where $\mathbf{x} = (x_1, \dots, x_d) \in [0, 1]^d$ is drawn uniformly from the $d$ -dimensional unit hypercube, and continuous attribute values are discretized into five uniform bins.
- Class Labeling: An example $\mathbf{x}$ is labeled positive if $\sum_{i=1}^d w_i x_i \ge w_0$ , and negative otherwise. To evaluate multiclass or multi-band settings, parallel alternating class bands of width $0.1 \cdot w_0$ are defined: positive if $\sum w_i x_i \in [w_0, 1.1 w_0]$ or $[1.2 w_0, 1.3 w_0]$ , negative if $[1.1 w_0, 1.2 w_0]$ , etc.
- Weights and Drift Simulation: Reference weights are initialized to $w_i = 0.2$ for $i > 0$ and $w_0 = 0.25 \cdot d$ . Drift is induced every 50,000 or 75,000 examples by perturbing $D$ active dimensions: $w_i \leftarrow w_i + 0.01 \cdot \sigma_i$ , where $\sigma_i \in \{+1, -1\}$ . Weights are constrained within $[0, 1]$ , reversing $heta_i$ when bounds are reached, with a $25\%$ random sign-flip probability per perturbation to prevent co-directional drift locking.
- Label Noise: $p\%$ random label flipping is injected (standard baseline $p = 5\%$ ).
- Benchmark Hyperparameters: Total stream size 5 million examples; sliding window $w = 100,000$ ; split confidence $\delta = 0.0001$ ; tie threshold $\tau = 0.05$ ; batch frequency $n_{min} = 300$ ; drift validity period $f = 20,000$ ; alternate subtree test activation after 9,000 examples over a test window of $m = 1,000$ examples.
Knowl 8 — Empirical Performance of CVFDT Compared to VFDT and VFDT-Window on Concept-Drifting Synthetic Streams
empirical result
On the rotating hyperplane benchmark ( $d=50$ dimensions, $w=100,000$ , 5 million examples, 5% label noise, weight updates every 50,000 examples):
- Error Rate Under Drift: CVFDT maintains an average classification error of approximately $16.3\%$ (close to the $15.3\%$ error achieved by periodically applying VFDT to the sliding window, denoted VFDT-Window), whereas the stationary VFDT learner degrades to an average error of $19.4\%$ with peak error rates approaching $50\%$ when drift occurs. CVFDT provides approximately $75\%$ of VFDT-Window's accuracy advantage over VFDT.
- Tree Size: Because stationary VFDT retains obsolete splits from early distributions and must grow increasingly large subtrees to compensate, its tree size averages 2,696 nodes. CVFDT maintains much more compact models, averaging 677 nodes in total (545 nodes in the main tree and 132 in active alternate subtrees).
- Runtime Efficiency: On a 5-million example stream evaluated on a 1GHz Pentium III:
  - VFDT executed in approximately 10 minutes.
  - CVFDT completed in approximately 46 minutes (4.3 times the runtime of VFDT when window caching is in memory, or 5.7 times including disk I/O).
  - VFDT-Window (simulated by full retraining every 100,000 examples) ran at an estimated runtime cost 17,000 times that of CVFDT (an estimated 548 days if executed per example).
- RAM Footprint: Across 50 runs, CVFDT memory consumption never exceeded 70 MB (averaging 23 MB), often utilizing as little as half the RAM of VFDT because VFDT's tree grew excessively large.
Knowl 9 — Real-World Evaluation of CVFDT on University Web Proxy Request Logs
empirical result
CVFDT was applied to predict cache access patterns from a 1-week trace of HTTP web proxy requests from the University of Washington (82.8 million requests, peak rate 17,400 requests/minute, 244,000 distinct target hosts, 170 internal organizations):
- Problem Formulation: The stream was discretized into 1-hour time slices. For each organization $O_i$ and host $H_j$ , a feature vector of access counts in the preceding hour $C_{i, j, t-1}$ and current hour $C_{i, j, t}$ was constructed to predict whether host $H_j$ would be requested in the subsequent hour $t+1$ (yielding 1.89 million examples; 60.9% negative).
- Empirical Accuracy: With parameters $\delta = 0.0001$ $δ = 0.0001$ , $\tau = 0.05$ $τ = 0.05$ , $n_{min} = 300$ $n_{min} = 300$ , $w = 100,000$ $w = 100, 000$ , and $f = 20,000$ $f = 20, 000$ :
  - CVFDT achieved an overall aggregated accuracy of $72.3\%$ , while stationary VFDT achieved $72.7\%$ .
  - During the first $70\%$ of the trace, CVFDT outperformed VFDT by up to $1.0\%$ in accuracy due to rapid tracking of active web host shifts.
  - In the final portion of the trace, VFDT achieved slightly higher accuracy because the fixed window of $w = 100,000$ examples constrained CVFDT's tree depth compared to the full accumulated dataset available to VFDT.

Coverage note — Background descriptions of stationary VFDT and previous concept drift systems (such as FLORA, STAGGER, and DEMON/BOAT) were omitted as they constitute prior art.

References

1.R. Agrawal and G. Psaila. Active data mining. In Proceedings of the First International Conference on Knowledge Discovery and Data Mining, pages 3-8, Montreal, Canada, 1995. AAAI Press.
2.N. F. Ayan, A. U. Tansel, and M. E. Arkun. An efficient algorithm to update large itemsets with early pruning. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 287-291, San Diego, CA, 1999. ACM Press.
3.P. L. Bartlett, S. Ben-David, and S. R. Kulkarni. Learning changing concepts by exploiting the structure of change. Machine Learning, 41:153-174, 2000.
4.L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
5.J. Catlett. Megainduction: Machine Learning on Very Large Databases. PhD thesis, Basser Department of Computer Science, University of Sydney, Sydney, Australia, 1991.
6.S. Chakrabarti, S. Sarawagi, and B. Dom. Mining surprising patterns using temporal description length. In Proceedings of the Twenty-Fourth International Conference on Very Large Data Bases, pages 606-617, New York, NY, 1998. Morgan Kaufmann.
7.D. W.-L. Cheung, J. Han, V. Ng, and C. Y. Wong. Maintenance of discovered association rules in large databases: An incremental updating technique. In Proceedings of the Twelfth International Conference on Data Engineering, pages 106-114, New Orleans, Louisiana, 1996. IEEE Computer Society Press.
8.A. Danyluk, T. Fawcett, and F. Provost, editors. Proceedings of the AAAI-98 Workshop on Predicting the Future: AI Approaches to Time-Series Analysis. AAAI Press, Madison, WI, 1998.
9.P. Domingos and G. Hulten. Mining high-speed data streams. In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 71-80, Boston, MA, 2000. ACM Press.
10.T. Fawcett and F. Provost. Activity monitoring: Noticing interesting changes in behavior. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 53-62, San Diego, CA, 1999. ACM Press.
11.V. Ganti, J. Gehrke, and R. Ramakrishnan. DEMON: Mining and monitoring evolving data. In Proceedings of the Sixteenth International Conference on Data Engineering, pages 439-448, San Diego, CA, 2000.
12.J. Gehrke, V. Ganti, R. Ramakrishnan, and W.-L. Loh. BOAT: optimistic decision tree construction. In Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, pages 169-180, Philadelphia, PA, 1999. ACM Press.
13.W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.
14.M. G. Kelly, D. J. Hand, and N. M. Adams. The impact of changing populations on classifier performance. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 367-371, San Diego, CA, 1999. ACM Press.
15.M. Kubat and G. Widmer, editors. Proceedings of the ICML-96 Workshop on Learning in Context-Sensitive Domains. Bari, Italy, 1996.
16.P. M. Long. The complexity of learning according to two models of a drifting environment. Machine Learning, 37:337-354, 1999.
17.M. Mehta, A. Agrawal, and J. Rissanen. SLIQ: A fast scalable classifier for data mining. In Proceedings of the Fifth International Conference on Extending Database Technology, pages 18-32, Avignon, France, 1996. Springer.
18.R. G. Miller, Jr. Simultaneous Statistical Inference. Springer, New York, NY, 2nd edition, 1981.
19.R. Musick, J. Catlett, and S. Russell. Decision theoretic subsampling for induction on large databases. In Proceedings of the Tenth International Conference on Machine Learning, pages 212-219, Amherst, MA, 1993. Morgan Kaufmann.
20.J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, CA, 1993.
21.M. Salganicoff. Density-adaptive learning and forgetting. In Proceedings of the Tenth International Conference on Machine Learning, pages 276-283, Amherst, MA, 1993. Morgan Kaufmann.
22.N. L. Sarda and N. V. Srinivas. An adaptive algorithm for incremental mining of association rules. In Proceedings of the Ninth International Workshop on Database and Expert Systems Applications, pages 240-245, Vienna, Austria, 1998. IEEE.
23.J. C. Schlimmer and R. H. Granger, Jr. Beyond incremental processing: Tracking concept drift. In Proceedings of the Fifth National Conference on Artificial Intelligence, pages 502-507, Philadelphia, PA, 1986. Morgan Kaufmann.
24.J. C. Shafer, R. Agrawal, and M. Mehta. SPRINT: A scalable parallel classifier for data mining. In Proceedings of the Twenty-Second International Conference on Very Large Databases, pages 544-555, Bombay, India, 1996. Morgan Kaufmann.
25.P. Turney. Context-sensitive learning bibliography. Online bibliography, Institute for Information Technology of the National Research Council of Canada, Ottawa, Canada, 1998. http://ai.iit.nrc.ca/-bibliographies/context-sensitive.html.
26.S. Vijayakumar and S. Schaal, editors. Proceedings of the NIPS-2000 Workshop on Real-Time Modeling for Complex Learning Tasks. NIPS Foundation, Breckenridge, Colorado, 2000.
27.G. Widmer and M. Kubat. Learning in the presence of concept drift and hidden contexts. Machine Learning, 23:69-101, 1996.
28.G. Widmer and M. Kubat. Special issue on context sensitivity and concept drift. Machine Learning, 32(2), 1998.
29.A. Wolman, G. Voelker, N. Sharma, N. Cardwell, M. Brown, T. Landray, D. Pinnel, A. Karlin, and H. Levy. Organization-based analysis of Web-object sharing and caching. In Proceedings of the Second USENIX Conference on Internet Technologies and Systems, pages 25-36, Boulder, CO, 1999.

Citation

MLA

Hulten, G., et al. “Mining Time-changing Data Streams”. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 97–106, https://doi.org/10.1145/502512.502529.

APA

Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 97–106. https://doi.org/10.1145/502512.502529

Chicago

Hulten, G., L. Spencer, and P. Domingos. 2001. “Mining Time-changing Data Streams”. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 97–106. https://doi.org/10.1145/502512.502529.

Harvard

Hulten, G., Spencer, L. and Domingos, P. (2001) “Mining time-changing data streams”, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 97–106. Available at: https://doi.org/10.1145/502512.502529.

Vancouver

1. Hulten G, Spencer L, Domingos P (2001) Mining time-changing data streams. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 97–106

BibTeX

@inproceedings{Hulten_2001, series={KDD01}, title={Mining time-changing data streams}, url={http://dx.doi.org/10.1145/502512.502529}, DOI={10.1145/502512.502529}, booktitle={Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Hulten, Geoff and Spencer, Laurie and Domingos, Pedro}, year={2001}, month=Aug, pages={97–106}, collection={KDD01} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Mining time-changing data streams

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — CVFDT Algorithm for Decision Tree Induction over Concept-Drifting Data Streams

Knowl 2 — Alternate Subtree Generation, Evaluation, and Replacement in CVFDT

Knowl 3 — Forgetting Expired Examples from Decision Tree Sufficient Statistics

Knowl 4 — CVFDT Tree Growth and Split Selection

Knowl 5 — Time and Memory Complexity of CVFDT vs. VFDT-Window

Knowl 6 — Hoeffding Bound for Stream-Based Decision Tree Attribute Split Decisions

Knowl 7 — Rotating Hyperplane Synthetic Benchmark for Concept-Drifting Data Streams

Knowl 8 — Empirical Performance of CVFDT Compared to VFDT and VFDT-Window on Concept-Drifting Synthetic Streams

Knowl 9 — Real-World Evaluation of CVFDT on University Web Proxy Request Logs

References

Citation

BibTeX

Access the Paper