Mining time-changing data streams.
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.
INTRODUCTION
Modern organizations produce data at unprecedented
rates; among large retailers, e-commerce sites, telecommunications
providers, and scientic projects, rates of gigabytes
per day are common. While this data can contain valuable
knowledge, its volume increasingly outpaces practitioners'
ability to mine it. As a result, it is now common practice
either to mine a subsample of the available data or to mine
for models drastically simpler than the data could support.
In some cases, the volume and time span of accumulated
data is such that just storing it consistently and reliably
for future use is a challenge. Further, even when storage is
not problematic, it is often di-cult to gather the data in
one place, at one time, in a format appropriate for mining.
For all these reasons, in many areas the notion of mining a
xed-sized database is giving way to the notion of mining
an open-ended data stream as it arrives. The goal of our re-search
is to help make this possible with a minimum of eort
for the data mining practitioner. In a previous paper [9] we
presented VFDT, a decision tree induction system capable
of learning from high-speed data streams in an incremental,
anytime fashion, while producing models that are asymptotically
arbitrarily close to those that would be learned by
traditional decision tree induction systems.
Most statistical and machine-learning algorithms, including
VFDT, make the assumption that training data is a
random sample drawn from a stationary distribution. Un-
fortunately, most of the large databases and data streams
available for mining today violate this assumption. They exist
over months or years, and the underlying processes generating
them changes during this time, sometimes radically.
For example, a new product or promotion, a hacker's attack,
a holiday, changing weather conditions, changing economic
conditions, or a poorly calibrated sensor could all lead to violations
of this assumption. For classication systems, which
attempt to learn a discrete function given examples of its inputs
and outputs, this problem takes the form of changes in
the target function over time, and is known as concept drift.
Traditional systems assume that all data was generated by a
single concept. In many cases, however, it is more accurate
to assume that data was generated by a series of concepts, or
by a concept function with time-varying parameters. Traditional
systems learn incorrect models when they erroneously
assume that the underlying concept is stationary if in fact
it is drifting.
One common approach to learning from time-changing
data is to repeatedly apply a traditional learner to a sliding
window of w examples; as new examples arrive they are
inserted into the beginning of the window, a corresponding
number of examples is removed from the end of the win-
dow, and the learner is reapplied [27]. As long as w is small
relative to the rate of concept drift, this procedure assures
availability of a model re
ecting the current concept generating
the data. If the window is too small, however, this
may result in insu-cient examples to satisfactorily learn the
concept. Further, the computational cost of reapplying a
learner may be prohibitively high, especially if examples arrive
at a rapid rate and the concept changes quickly.
To meet these challenges we propose the CVFDT system,
which is capable of learning decision trees from high-speed,
time changing data streams. CVFDT works by e-ciently
keeping a decision tree up-to-date with a window of exam-
ples. In particular, it is able to keep its model consistent
with a window using only a constant amount of time for
each new example (more precisely, time proportional to the
number of attributes in the data and the depth of the induced
tree). CVFDT grows an alternate subtree whenever
an old one seems to be out-of-date, and replaces the old one
when the new one becomes more accurate. This allows it to
make smooth, ne-grained adjustments when concept drift
occurs. In eect, CVFDT is able to learn a nearly equivalent
model to the one VFDT would learn if repeatedly reapplied
to a window of examples, but in O(1) time instead of O(w)
time per new example.
In the next section we discuss the basics of the VFDT sys-
tem, and in the following section we introduce the CVFDT
system. We then present a series of experiments on synthetic
data which demonstrate how CVFDT can outperform traditional
systems on high-speed, time-changing data streams.
Next, we apply CVFDT to mining the stream of web page
requests for the entire University of Washington campus.
We conclude with a discussion of related and future work.
2. THE VFDT SYSTEM
The classication problem is generally dened as follows.
A set of N training examples of the form (x; y) is given,
where y is a discrete class label and x is a vector of d at-
tributes, each of which may be symbolic or numeric. The
goal is to produce from these examples a model
which will predict the classes y of future examples x with
high accuracy. For example, x could be a description of a
client's recent purchases, and y the decision to send that customer
a catalog or not; or x could be a record of a cellular-
telephone call, and y the decision whether it is fraudulent
or not. One of the most eective and widely-used classi-
cation methods is decision tree learning [4, 20]. Learners of
this type induce models in the form of decision trees, where
each node contains a test on an attribute, each branch from
a node corresponds to a possible outcome of the test, and
each leaf contains a class prediction. The label
for an example x is obtained by passing the example down
from the root to a leaf, testing the appropriate attribute at
each node and following the branch corresponding to the
attribute's value in the example. A decision tree is learned
by recursively replacing leaves by test nodes, starting at the
root. The attribute to test at a node is chosen by comparing
all the available attributes and choosing the best one
according to some heuristic measure. Classic decision tree
learners like C4.5 [20], CART, SLIQ [17], and SPRINT [24]

Table

1: The VFDT Algorithm.
Inputs: S is a stream of examples,
X is a set of symbolic attributes,
G(:) is a split evaluation function,
- is one minus the desired probability of
choosing the correct attribute at any
given node,
is a user-supplied tie threshold,
nmin is the # examples between checks for
growth.
Output: HT is a decision tree.
Procedure VFDT (S; X;G; -; )
Let HT be a tree with a single leaf l 1 (the root).
g.
be the G obtained by predicting the most
frequent class in S.
For each class yk
For each value x ij of each attribute X
For each example (x; y) in S
Sort (x; y) into a leaf l using HT .
For each x ij in x such that X
Increment n ijy (l).
Label l with the majority class among the examples
seen so far at l.
Let n l be the number of examples seen at l.
If the examples seen so far at l are not all of the same
class and n l mod nmin is 0, then
Compute
using the counts n ijk (l).
Let Xa be the attribute with highest G l .
Let X b be the attribute with second-highest G l .
Compute using Equation 1.
If ((G l > ) or (G l <=  <
Replace l by an internal node that splits on Xa .
For each branch of the split
Add a new leaf l m , and let
be the G obtained by predicting
the most frequent class at l m .
For each class yk and each value x ij of each
attribute
Return HT .
use every available training example to select the best attribute
for each split. This policy is necessary when data is
scarce, but it has two problems when training examples are
abundant: it requires all examples be available for consideration
throughout their entire runs, which is problematic
when data does not t in RAM or on disk, and it assumes
that the process generating examples remains the same during
the entire period over which the examples are collected
and mined.
In previous work [9] we presented the VFDT (Very Fast
Decision Tree learner) system, which is able to learn from
abundant data within practical time and memory constrai-
nts. It accomplishes this by noting, with Catlett [5] and others
[12, 19], that it may be su-cient to use a small sample
of the available examples when choosing the split attribute
at any given node. Thus, only the rst examples to arrive
on the data stream need to be used to choose the split attribute
at the root; subsequent ones are passed through the
induced portion of the tree until they reach a leaf, are used
to choose a split attribute there, and so on recursively. To
determine the number of examples needed for each decision,
VFDT uses a statistical result known as Hoeding bounds
or additive Cherno bounds [13]. After n independent observations
of a real-valued random variable r with range R,
the Hoeding bound ensures that, with condence 1 -, the
true mean of r is at least r , where r is the observed mean
of the samples and
r
2n (1)
This is true irrespective of the probability distribution that
generated the observations. Let G(X i ) be the heuristic measure
used to choose test attributes (we use information gain).
After seeing n samples at a leaf, let Xa be the attribute with
the best heuristic measure and X b be the attribute with the
second best. Let be a new random
variable, the dierence between the observed heuristic val-
ues. Applying the Hoeding bound to G, we see that if
G >  (as calculated by Equation 1 with a user-supplied
-), we can condently say that the dierence between G(Xa)
and G(X b ) is larger than zero, and select Xa as the split at-
tribute. 1;2 Table 1 contains pseudo-code for VFDT's core al-
gorithm. The counts n ijk are the su-cient statistics needed
to compute most heuristic measures; if other quantities are
required, they can be similarly maintained. When the sucient
statistics ll the available memory, VFDT reduces its
memory requirements by temporarily deactivating learning
in the least promising nodes; these nodes can be reactivated
later if they begin to look more promising than currently
active nodes. VFDT employs a tie mechanism which precludes
it from spending inordinate time deciding between
1 This is valid as long as G (and therefore G) can be viewed
as an average over all examples seen at the leaf, which is the
case for most commonly-used heuristics. For example, if
information gain is used, the quantity being averaged is the
reduction in the uncertainty regarding the class membership
of the example.
2 In this paper we assume that the third-best and lower attributes
have su-ciently smaller gains that their probability
of being the true best choice is negligible. We plan to lift
this assumption in future work. If the attributes at a given
node are (pessimistically) assumed independent, it simply
involves a Bonferroni correction to - [18].
attributes whose practical dierence is negligible. That is,
VFDT declares a tie and selects Xa as the split attribute
any time G <  <  (where  is a user-supplied tie thresh-
old). Pre-pruning is carried out by considering at each node
a \null" attribute X ; that consists of not splitting the node.
Thus a split will only be made if, with condence 1 -, the
best split found is better according to G than not splitting.
Notice that the tests for splits and ties are only executed
once for every nmin (a user supplied value) examples that
arrive at a leaf. This is justied by the observation that
VFDT is unlikely to make a decision after any given exam-
ple, so it is wasteful to carry out these calculations for each
one of them. The pseudo-code shown is only for symbolic
attributes; we are currently developing its extension to numeric
ones. The sequence of examples S may be innite, in
which case the procedure never terminates, and at any point
in time a parallel procedure can use the current tree HT to
make class predictions.
Using o-the-shelf hardware, VFDT is able to learn as
fast as data can be read from disk. The time to incorporate
an example is O(ldvc) where l is the maximum depth of
HT , d is the number of attributes, v is the maximum number
of values per attribute, and c is the number of classes.
This time is independent of the total number of examples
already seen (assuming the size of the tree depends only on
the \true" concept, and not on the dataset). Because of the
use of Hoeding bounds, these speed gains do not necessarily
lead to a loss of accuracy. It can be shown that, with
high condence, the core VFDT system (without ties or de-
activations due to memory constraints) will asymptotically
induce a tree arbitrarily close to the tree induced by a traditional
batch learner. Let DT1 be the tree induced by a
version of VFDT using innite data to choose each node's
split attribute, HT - be the tree learned by the core VFDT
system given an innite data stream, and p be the probability
that an example passed through DT1 to level i will
fall into a leaf at that point. Then the probability that an
arbitrary example will take a dierent path through DT1
and HT - is bounded by -=p [9]. A corollary of this result
states that the tree learned by the core VFDT system on
a nite sequence of examples will correspond to a subtree
of DT1 with the same bound of -=p. See Domingos and
Hulten [9] for more details on VFDT and this -=p bound.
3. THE CVFDT SYSTEM
CVFDT (Concept-adapting Very Fast Decision Tree
learner) is an extension to VFDT which maintains VFDT's
speed and accuracy advantages but adds the ability to detect
and respond to changes in the example-generating process.
Like other systems with this capability, CVFDT works by
keeping its model consistent with a sliding window of ex-
amples. However, it does not need to learn a new model
from scratch every time a new example arrives; instead, it
updates the su-cient statistics at its nodes by incrementing
the counts corresponding to the new example, and decrementing
the counts corresponding to the oldest example in
the window (which now needs to be forgotten). This will
statistically have no eect if the underlying concept is sta-
tionary. If the concept is changing, however, some splits
that previously passed the Hoeding test will no longer do
so, because an alternative attribute now has higher gain (or
the two are too close to tell). In this case CVFDT begins to
grow an alternative subtree with the new best attribute at

Table

2: The CVFDT algorithm.
Inputs: S is a sequence of examples,
X is a set of symbolic attributes,
G(:) is a split evaluation function,
- is one minus the desired probability of
choosing the correct attribute at any
given node,
is a user-supplied tie threshold,
w is the size of the window,
nmin is the # examples between checks for growth,
f is the # examples between checks for drift.
Output: HT is a decision tree.
Procedure CVFDT(S;X; G; -; ; w; nmin)
/* Initialize */
Let HT be a tree with a single leaf l 1 (the root).
Let ALT (l 1) be an initially empty set of alternate
trees for l 1 .
be the G obtained by predicting the most
frequent class in S.
g.
Let W be the window of examples, initially empty.
For each class yk
For each value x ij of each attribute X
/* Process the examples */
For each example (x; y) in S
Sort (x; y) into a set of leaves L using HT and all
trees in ALT of any node (x; y) passes through.
Let ID be the maximum id of the leaves in L.
Add ((x; y); ID) to the beginning of W .
If
be the last element of W
removed
G; (x; y); -; nmin ; )
If there have been f examples since the last checking
of alternate trees
CheckSplitValidity(HT; n; -)
Return HT .

Table

3: The CVFDTGrow procedure.
Procedure CVFDTGrow(HT; n; G; (x; y); -; nmin ; )
Sort (x; y) into a leaf l using HT .
Let P be the set of nodes traversed in the sort.
For each node l pi in P
For each x ij in x such that X
Increment n ijy (l p ).
For each tree Ta in ALT (l p)
G; (x; y); -; nmin ; )
Label l with the majority class among the examples seen
so far at l.
Let n l be the number of examples seen at l.
If the examples seen so far at l are not all of the same
class and n l mod nmin is 0, then
Compute
using the counts n ijk (l).
Let Xa be the attribute with highest G l .
Let X b be the attribute with second-highest G l .
Compute using Equation 1 and -.
If ((G l > ) or (G l <=  <
Replace l by an internal node that splits on Xa .
For each branch of the split
Add a new leaf l m , and let
Let ALT (l m) = fg.
be the G obtained by predicting the
most frequent class at l m .
For each class yk and each value x ij of each
attribute
its root. When this alternate subtree becomes more accurate
on new data than the old one, the old subtree is replaced by
the new one.

Table

contains a pseudo-code outline of the CVFDT
algorithm. CVFDT does some initializations, and then processes
examples from the stream S indenitely. As each
example arrives, it is added to the window 3 , an old
example is forgotten if needed, and (x; y) is incorporated
into the current model. CVFDT periodically scans HT and
all alternate trees looking for internal nodes whose su-cient
statistics indicate that some new attribute would make a
better test than the chosen split attribute. An alternate
subtree is started at each such node.

Table

3 contains pseudo-code for the tree-growing portion
of the CVFDT system. It is similar to the Hoeding
Tree algorithm, but CVFDT monitors the validity of its old
decisions by maintaining su-cient statistics at every node
in HT (instead of only at the leaves like VFDT). Forgetting
an old example is slightly complicated by the fact that
HT may have grown or changed since the example was initially
incorporated. Therefore, nodes are assigned a unique,
monotonically increasing ID as they are created. When an
example is added to W , the maximum ID of the leaves it
reaches in HT and all alternate trees is recorded with it. An
example's eects are forgotten by decrementing the counts
in the su-cient statistics of every node the example reaches
3 The window is stored in RAM if resources are available,
otherwise it will be kept on disk.

Table

4: The ForgetExample procedure.
Procedure
while it traverses leaves
with id  IDw ,
Let P be the set of nodes traversed in the sort.
For each node l in P
For each x ij in x such that X
Decrement n ijk (l).
For each tree T alt in ALT (l)
in HT whose ID is  the stored ID. See the pseudo-code in

Table

4 for more detail about how CVFDT forgets examples.
CVFDT periodically scans the internal nodes of HT looking
for ones where the chosen split attribute would no longer
be selected; that is, where G(Xa) G(X b )   and  >  .
When it nds such a node, CVFDT knows that it either
initially made a mistake splitting on Xa (which should happen
less than -% of the time), or that something about the
process generating examples has changed. In either case,
CVFDT will need to take action to correct HT . CVFDT
grows alternate subtrees to changed subtrees of HT , and
only modies HT when the alternate is more accurate than
the original. To see why this is needed, let l  be a node
where change was detected. A simple solution is to replace
l  with a leaf predicting the most common class in l  's sufcient
statistics. This policy assures that HT is always as
current as possible with respect to the process generating
examples. However, it may be too drastic, because it initially
forces a single leaf to do the job previously done by a
whole subtree. Even if the subtree is outdated, it may still
be better than the best single leaf. This is particularly true
when l  is at or near the root of HT , as it will result in
drastic short-term reductions in HT 's predictive accuracy {
clearly not acceptable when a parallel process is using HT
to make critical decisions.
Each internal node in HT has a list of alternate subtrees
being considered as replacements for the subtree rooted at
the node. Table 5 contains pseudo-code for the CheckSplit-
procedure. CheckSplitValidity starts an alternate
subtree whenever it nds a new winning attribute at a node;
that is, when there is a new best attribute and G >  or if
<  and G  =2. This is very similar to the procedure
used to choose initial splits, except the tie criteria is tighter
to avoid excessive alternate tree creation. CVFDT supports
a parameter which limits the total number of alternate trees
being grown at any one time. Alternate trees are grown
the same way HT is, via recursive calls to the CVFDT pro-
cedures. Periodically, each node with a non-empty set of
alternate subtrees, l test , enters a testing mode to determine
if it should be replaced by one of its alternate subtrees. Once
in this mode, l test collects the next m training examples that
arrive at it and, instead of using them to grow its children
or alternate trees, uses them to compare the accuracy of the
subtree it roots with the accuracies of all of its alternate
subtrees. If the most accurate alternate subtree is more accurate
than the l test , l test is replaced by the alternate. During
the test phase, CVFDT also prunes alternate subtrees
that are not making progress (i.e., whose accuracy is not in-
Table

5: The CheckSplitValidity procedure.
Procedure CheckSplitValidity(HT; n; -)
For each node l in HT that is not a leaf
For each tree T alt in ALT (l)
Let Xa be the split attribute at l.
Let Xn be the attribute with the highest G l
other than Xa .
Let X b be the attribute with the highest G l
other than Xn .
If G l  0 and no tree in ALT (l) already splits on
at its root
Compute using Equation 1 and -.
If (G l > ) or ( <  and G l  =2), then
Let l new be an internal node that splits on Xn .
Let ALT
For each branch of the split
Add a new leaf l m to l new
Let ALT (l m) = fg.
be the G obtained by predicting
the most frequent class at l m .
For each class yk and each value x ij of each
attribute
creasing over time). For each alternate subtree of l test , l i
alt ,
CVFDT remembers the smallest accuracy dierence ever
achieved between the two, min (l test ; l i alt ). CVFDT prunes
any alternate whose current test phase accuracy dierence
is at least min (l test ; l i
One window size w will not be appropriate for every concept
and every type of drift; it may be benecial to dynamically
change w during a run. For example, it may make
sense to shrink w when many of the nodes in HT become
questionable at once, or in response to a rapid change in
data rate, as these events could indicate a sudden concept
change. Similarly, some applications may benet from an increase
in w when there are few questionable nodes because
this may indicate that the concept is stable { a good time to
learn a more detailed model. CVFDT is able to dynamically
adjust the size of its window in response to user-supplied
events. Events are specied in the form of hook functions
which monitor S and HT and can call the SetWindowSize
function when appropriate. CVFDT changes the window
size by updating w and immediately forgetting any examples
that no longer t in W .
We now discuss a few of the properties of the CVFDT system
and brie
y compare it with VFDT-Window, a learner
that reapplies VFDT to W for every new example. CVFDT
requires memory proportional to O(ndvc) where n is the
number of nodes in CVFDT's main tree and all alternate
trees, d is the number of attributes, v is the maximum number
of values per attribute, and c is the number of classes.
The window of examples can be in RAM or can be stored on
4 When RAM is short, CVFDT is more aggressive about
pruning unpromising alternate subtrees.
disk at the cost of a few disk accesses per example. There-
fore, CVFDT's memory requirements are dominated by the
su-cient statistics and are independent of the total number
of examples seen. At any point during a run, CVFDT
will have available a model which re
ects the current concept
generating W . It is able to keep this model up-to-date
in time proportional to O(lcdvc) per example, where l c is
the length of the longest path an example will have to take
through HT times the number of alternate trees. VFDT-
Window requires O(lvdvcw) time to keep its model up-to-
date for every new example, where l v is the maximum depth
of HT . VFDT is a factor of wlv =lc worse than CVFDT; em-
pirically, we observed l c to be smaller than l v in all of our
experiments. Despite this large time dierence, CVFDT's
drift mechanisms allow it to produce a model of similar ac-
curacy. The structure of the models induced by the two may,
however, be signicantly dierent, for the following reason.
VFDT-Window uses the information from each training example
at one place in the tree it induces: the leaf where
the example falls when it arrives. This means that VFDT-
Window uses the rst examples from W to make a decision
at its root, the next to make a decision at the rst level of
the tree, and so on. After an initial building phase, CVFDT
will have a fully induced tree available. Every new example
is passed through this induced tree, and the information it
contains is used to update statistics at every node it passes
through. This dierence can be an advantage for CVFDT,
as it allows the induction of larger trees with better probability
estimates at the leaves. It can also be a disadvantage
and VFDT-Window may be more accurate when there is a
large concept shift part-way through W . This is because
VFDT-Window's leaf probabilities will be set by examples
near the end of W while CVFDT's will re
ect all of W .
Also notice that, even when the structure of the induced
tree does not change, CVFDT and VFDT-Window can out-perform
VFDT simply because their leaf probabilities (and
therefore class predictions) are updated faster, without the
\dead weight" of all the examples that fell into leaves before
the current window.
4. EMPIRICAL STUDY
We conducted a series of experiments comparing CVFDT
to VFDT and VFDT-Window. Our goals were to evaluate
CVFDT's ability to scale up, to evaluate CVFDT's ability
to deal with varying levels of drift, and to identify and characterize
the situations where CVFDT outperforms the other
systems.
4.1 Synthetic Data
The experiments with synthetic data used a changing concept
based on a rotating hyperplane. A hyperplane in d-dimensional
space is the set of points x that satisfy
d
where x i is the ith coordinate of x. Examples for which
are labeled positive, and examples for which
are labeled negative. Hyperplanes are useful
for simulating time-changing concepts because we can
change the orientation and position of the hyperplane in a
smooth manner by changing the relative size of the weights.
In particular, sorting the weights by their magnitudes provides
a good indication of which dimensions contain the
most information; in the limit, when all but one of the
weights are zero, the dimension associated with the non-zero
weight is the only one that contains any information about
the concept. This allows us to control the relative information
content of the attributes, and thus change the optimal
order of tests in a decision tree representing the hyperplane,
by simply changing the relative sizes of the weights. We
sought a concept that maintained the advantages of a hy-
perplane, but where the weights could be randomly modied
without potentially causing the decision frontier to move
outside the range of the data. To meet these goals we used a
series of alternating class bands separated by parallel hyper-
planes. We start with a reference hyperplane whose weights
are initialized to :2 except for w0 which is :25d. To label
an example, we substitute its coordinates into the left hand
side of Equation 2 to obtain a sum s. If jsj  :1  w0 the
example is labeled positive, otherwise if jsj  :2  w0 the
example is labeled negative, and so on. Examples were generated
uniformly in a d-dimensional unit hypercube (with
the value of each x i ranging from [0, 1]). They were then
labeled using the concept, and their continuous attributes
were uniformly discretized into ve bins. Noise was added
by randomly switching the class labels of p% of the exam-
ples. Unless otherwise stated, each experiment used the following
settings: ve million training examples;
window on disk; no memory limits; no pre-pruning; a test
set of 50,000 examples; and
alternate tree test mode after 9,000 examples and used test
samples of 1,000 examples. All runs were done on a 1GHz
Pentium III machine with 512 MB of RAM, running Linux.
The rst series of experiments compares the ability of
CVFDT and VFDT to deal with large concept-drifting data-
sets. Concept drift was added to the datasets in the following
manner. Every 50,000 examples w1 was modied by
adding 0:01d to it, and the test set was relabeled with the
updated concept (with p% noise as before).  was initially
1 and was multiplied by 1 at 5% of the drift points and
also just before w1 fell below 0 or rose above :25d. Figure 1
compares the accuracy of the algorithms as a function of
d, the dimensionality of the space. The reported values are
obtained by testing the accuracy of the learned models every
10,000 examples throughout the run and averaging these
results. Drift level, reported on the minor axis, is the average
percentage of the test set that changes label at each
point the concept changes. CVFDT is substantially more
accurate than VFDT, by approximately 10% on average,
and CVFDT's performance improves slightly with increasing
d.

Figure

2 compares the average size of the models
induced during the run shown in Figure 1 (the reported values
are generated by averaging after every 10,000 examples,
as before). CVFDT's trees are substantially smaller than
VFDT's, and the advantage is consistent across all the values
of d we tried. This simultaneous accuracy and size advantage
derives from the fact that CVFDT's tree is built on
the 100,000 most relevant examples, while VFDT's is built
on millions of outdated examples.
We next carried out a more detailed evaluation of
CVFDT's concept drift mechanism. Figure 3 shows a detailed
view of one of the runs from Figures 1 and 2, the one
for 50. The minor axis shows the portion of the test

Figure

1: Error rates as a function of the number of
attributes.

Figure

2: Tree sizes as a function of the number of
attributes.

Figure

3: Error rates of learners as a function of the
number of examples seen.
set that is labeled negative at each test point (computed
before noise is added to the test set) and is included to illustrate
the concept drift present in the dataset. CVFDT is
able to quickly respond to drift, while VFDT's error rate often
rises drastically before reacting to the change. Further,
VFDT's error rate seems to peak at worse values as the run
goes on, while CVFDT's error peaks seem to have constant
height. We believe this happens because VFDT has more
trouble responding to drift when it has induced a larger tree
and must replicate corrections across more outdated struc-
ture. CVFDT does not face this problem because it replaces
subtrees when they become outdated. We gathered some
detailed statistics about this run. CVFDT took 4.3 times
longer than VFDT (5.7 times longer if including time to do
the disk I/O needed to keep the window on disk). VFDT's
average memory allocation over the course of the run was 23
MB while CVFDT's was 16.5 MB. The average number of
nodes in VFDT's tree was 2696 and the average number in
CVFDT's tree was 677, of which 132 were in alternate trees
and the remainder were in the main tree.
Next we examined how CVFDT responds to changing levels
of concept drift on ve datasets with
added using a parameter D. Every 75,000 examples, D of
the concept hyperplane's weights were selected at random
and updated as before, w
has a 25% chance of
ipping signs, chosen to prevent too
many weights from drifting in the same pattern). Figure 4
shows the comparison on these datasets. CVFDT substantially
outperformed VFDT at every level of drift. Notice
that VFDT's error rate approaches 50% for D > 2, and
that the variance in VFDT's data points is large. CVFDT's
error rate seems to grow smoothly with increasing levels of
concept change, suggesting that its drift adaptations are robust
and eective.
We wanted to gain some insight into the way CVFDT
starts new alternate subtrees, prunes existing ones, and replaces
portions of HT with alternates. For this purpose,
we instrumented a run of CVFDT on the
from

Figure

4 to output a token in response to each of these
events. We aggregated the events in chunks of 100,000 training
examples, and generated data points for all non-zero values

Figure

5 shows the results of this experiment. There
are a large number of events during the run. For example,
alternate subtrees were swapped into HT . Most of the
swaps seem to occur when the examples in the test set are
changing labels quickly.
We also wanted to see how well CVFDT would compare
to a system using traditional drift-tracking methods. We
thus compared CVFDT, VFDT, and VFDT-Window. We
simulated VFDT-Window by running VFDT on W for every
100,000 examples instead of for every example. The
dataset for the experiment had used the same
drift settings used to generate Figure 4 with
6 shows the results. CVFDT's error rate was the same
as VFDT-Window's, except for a brief period during the
middle of the run when class labels were changing most
rapidly. CVFDT's average error rate for the run was 16.3%,
VFDT's was 19.4%, and VFDT-Window's was 15.3%. The
dierence in runtimes was very large. VFDT took about 10
minutes, CVFDT took about 46 minutes, and we estimate
that VFDT-Window would have taken 548 days to do its
complete run if applied to every new example. Put another
way, VFDT-Window provides a 4% accuracy gain compared

Figure

4: Error rates as a function of the amount of
concept drift.

Figure

5: CVFDT's drift characteristics.

Figure

rates over time of CVFDT, VFDT,
and VFDT-Window.
to VFDT, at a cost of increasing the running time by a factor
of 17,000. CVFDT provides 75% of VFDT-Window's
accuracy gain, and introduces a time penalty of less than
0.1% of VFDT-Window's.
CVFDT's alternate trees and additional su-cient statistics
do not use too much RAM. For example, none of
runs ever grew to more than 70MB. We
never observed CVFDT to use more RAM than VFDT; in
fact it often used as little as half the RAM of VFDT. The
systems' RAM requirements are dominated by the su-cient
statistics which are kept at the leaves in VFDT, and at every
node in CVFDT. We observed that VFDT often had twice
as many leaves as there were nodes in CVFDT's tree and all
alternate trees combined. This is what we expected: VFDT
considers many more examples and is forced to grow larger
trees to make up for the fact that its early decisions become
incorrect due to concept drift. CVFDT's alternate tree
pruning mechanism seems to be eective at trading memory
for smooth transitions between concepts. Further, there is
room for more aggressive pruning if CVFDT exhausts available
RAM. Exploring this tradeo is an area for future work.
4.2 Web Data
We are currently applying CVFDT to mining the stream
of Web page requests emanating from the whole University
of Washington main campus. The nature of the data
is described in detail in Wolman et al. [29]. In our experiments
so far we have used a one-week anonymized trace of all
the external web accesses made from the university campus.
There were 23,000 active clients during this one-week trace
period, and the entire university population is estimated at
50,000 people (students, faculty and sta). The trace contains
million requests, which arrive at a peak rate of
17,400 per minute. The size of the compressed trace le is
about 20 GB. 5 Each request is tagged with an anonymized
organization ID that associates the request with one of the
organizations (colleges, departments, etc.) within the
university. One purpose this data can be used for is to improve
Web caching. The key to this is predicting as accurately
as possible which hosts and pages will be requested in
the near future, given recent requests. We applied decision-tree
learning to this problem in the following manner. We
split the campus-wide request log into a series of equal time
slices in the experiments we report, each
time slice is an hour. For each organization O1 ;
and each of the 244k hosts appearing in the logs
maintained a count of how many
times the organization accessed the host in the time slice,
C ijt . We discretized these counts into four buckets, representing
\no requests," \1 { 12 requests," \13 { 25 requests"
and \26 or more requests." Then for each time slice and
host accessed in that time slice (T t generated an example
with attributes
if H j is requested in time slice T t+1 and 0 if it is not. This
can be carried out in real time using modest resources by
keeping statistics on the last and current time slices C t 1
and C t in memory, only keeping counts for hosts that actually
appear in a time slice (we never needed more than 30k
counts), and outputting the examples for C t 1 as soon as
C t is complete. Using this procedure we obtained a dataset
containing 1.89 million examples, 60.9% of which were la-
5 This log is from May 1999. Tra-c in May 2000 was more
than double this size.
beled with the most common class (that the host did not
appear again in the next time slice).
Our exploration was designed to determine if CVFDT's
concept drift features would provide any benet to this ap-
plication. As each example arrived, we tested the accuracy
of the learners' models on it, and then allowed the learners
to update their models with the example. We kept statistics
about how the aggregated accuracies changed over time.
VFDT and CVFDT were both run with
and additional parameters were
achieved 72.7% accuracy
over the whole dataset and CVFDT achieved 72.3%.
However, CVFDT's aggregated accuracy was higher for the
rst 70% of the run, at times by as much as 1.0%. CVFDT's
accuracy fell behind only near the end of the run, for (we
believe) the following reason. Its drift tracking kept it ahead
throughout the rst part of the run, but its window was too
small for it to learn as detailed a model of the data as VFDT
did by the end. This experiment shows that the data does
indeed contain concept drift, and that CVFDT's ability to
respond to the drift gives it an advantage over VFDT. The
next step is to run CVFDT with dierent, perhaps dynamic,
window sizes to further evaluate the nature of the drift. We
also plan to evaluate CVFDT over traces longer than a week.
5. RELATED WORK
Schlimmer and Granger's [23] STAGGER system was one
of the rst to explicitly address the problem of concept
drift. Salganico [21] studied drift in the context of nearest-neighbor
learning. Widmer and Kubat's [27] FLORA system
used a window of examples, but also stored old concept
descriptions and reactivated them if they seemed to be appropriate
again. All of these systems were only applied to
small databases (by today's standards). Kelly, Hand, and
Adams [14] addressed the issue of drifting parameters in
probability distributions. Theoretical work on concept drift
includes [16] and [3].
Ganti, Gehrke, and Ramakrishnan's [11] DEMON frame-work
is designed to help adapt incremental learning algorithms
to work eectively with time-changing data streams.
DEMON diers from CVFDT by assuming data arrives pe-
riodically, perhaps daily, in large blocks, while CVFDT deals
with each example as it arrives. The framework uses o-line
processing time to mine interesting subsets of the available
data blocks.
In earlier work [12] Gehrke, Ganti, and Ramakrishnan
presented an incremental decision tree induction algorithm,
BOAT, which works in the DEMON framework. BOAT is
able to incrementally maintain a decision tree equivalent to
the one that would be learned by a batch decision tree induction
system. When the underlying concept is stable, BOAT
can perform this maintenance extremely quickly. When drift
is present, BOAT must discard and regrow portions of its
induced tree. This can be very expensive when the drift is
large or aects nodes near the root of the tree. CVFDT
avoids the problem by using alternate trees and removing
the restriction that it learn exactly the tree that a batch
system would. A comparison between BOAT and CVFDT
is an area for future work.
There has been a great deal of work on incrementally
maintaining association rules. Cheung, Han, Ng, and Wong
and Fazil, Tansel, and Arkun [2] propose algorithms for
maintaining sets of association rules when new transactions
are added to the database. Sarda and Srinivas [22] have also
done some work in the area. DEMON's contribution [11] is
particularly relevant, as it addresses association rule maintenance
specically in the high-speed data stream domain
where blocks of transactions are added and deleted from the
database on a regular basis.
Aspects of the concept drift problem are also addressed
in the areas of activity monitoring [10], active data mining
[1] and deviation detection [6]. The main goal here is to
explicitly detect changes, rather than simply maintain an
up-to-date concept, but techniques for the latter can obviously
help in the former.
Several pieces of research on concept drift and context-sensitive
learning are collected in a special issue of the journal
Machine Learning [28]. Other relevant research appeared
in the ICML-96 Workshop on Learning in Context-Sensitive
Domains [15], the AAAI-98 Workshop on AI Approaches
to Time-Series Problems [8], and the NIPS-2000
Workshop on Real-Time Modeling for Complex Learning
Tasks [26]. Turney [25] maintains an online bibliography on
context-sensitive learning.
6. FUTURE WORK
We plan to apply CVFDT to more real-world problems;
its ability to adjust to concept changes should allow it to
perform very well on a broad range of tasks. CVFDT may
be a useful tool for identifying anomalous situations. Currently
CVFDT discards subtrees that are out-of-date, but
some concepts change periodically and these subtrees may
become useful again { identifying these situations and taking
advantage of them is another area for further study. Other
areas for study include: comparisons with related systems;
continuous attributes; weighting examples; partially forgetting
examples by allowing their weights to decay; simulating
weights by subsampling; and controlling the weight decay
function according to external information about drift.
7. CONCLUSION
This paper introduced CVFDT, a decision-tree induction
system capable of learning accurate models from the most
demanding high-speed, concept-drifting data streams.
CVFDT is able to maintain a decision-tree up-to-date with
a window of examples by using a small, constant amount
of time for each new example that arrives. The resulting
accuracy is similar to what would be obtained by reapplying
a conventional learner to the entire window every time a new
example arrives. Empirical studies show that CVFDT is
eectively able to keep its model up-to-date with a massive
data stream even in the face of large and frequent concept
shifts. A preliminary application of CVFDT to a real world
domain shows promising results.
8.

ACKNOWLEDGMENTS

This research was partly supported by a gift from the Ford
Motor Company, and by NSF CAREER and IBM Faculty
awards to the third author.
9.



--R

Active data mining.

Learning changing concepts by exploiting the structure of change.

Megainduction: Machine Learning on Very Large Databases.
Mining surprising patterns using temporal description length.
Maintenance of discovered association rules in large databases: An incremental updating technique.

Mining high-speed data streams
Activity monitoring: Noticing interesting changes in behavior.
DEMON: Mining and monitoring evolving data.
BOAT: optimistic decision tree construction.

The impact of changing populations on classi

The complexity of learning according to two models of a drifting environment.
SLIQ: A fast scalable classi

Decision theoretic subsampling for induction on large databases.


An adaptive algorithm for incremental mining of association rules.

SPRINT: A scalable parallel classi


Learning in the presence of concept drift and hidden contexts.
Special issue on context sensitivity and concept drift.

--TR
C4.5: programs for machine learning
Learning in the presence of concept drift and hidden contexts
BOATMYAMPERSANDmdash;optimistic decision tree construction
Activity monitoring
An efficient algorithm to update large itemsets with early pruning
The impact of changing populations on classifier performance
The Complexity of Learning According to Two Models of a Drifting Environment
Mining high-speed data streams
Learning Changing Concepts by Exploiting the Structure of Change
Maintenance of Discovered Association Rules in Large Databases
Mining Surprising Patterns Using Temporal Description Length
An Adaptive Algorithm for Incremental Mining of Association Rules
DEMON

--CTR
Ying Yang , Xindong Wu , Xingquan Zhu, Combining proactive and reactive predictions for data streams, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, On demand classification of data streams, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Francisco Ferrer-Troyano , Jesus S. Aguilar-Ruiz , Jose C. Riquelme, Incremental rule learning based on example nearness from numerical data streams, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Francisco Ferrer-Troyano , Jesus S. Aguilar-Ruiz , Jose C. Riquelme, Data streams classification by incremental rule learning with parameterized generalization, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Joong Hyuk Chang , Won Suk Lee, Finding recently frequent itemsets adaptively over online transactional data streams, Information Systems, v.31 n.8, p.849-869, December 2006
Joo Gama , Pedro Medas , Pedro Rodrigues, Learning decision trees from dynamic data streams, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Joo Gama , Ricardo Rocha , Pedro Medas, Accurate decision trees for mining high-speed data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Yi Zhang , Xiaoming Jin, An automatic construction and organization strategy for ensemble learning on data streams, ACM SIGMOD Record, v.35 n.3, p.28-33, September 2006
Francisco Ferrer-Troyano , Jess S. Aguilar-Ruiz , Jos C. Riquelme, Prototype-based mining of numeric data streams, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Brain Babcock , Mayur Datar , Rajeev Motwani , Liadan O'Callaghan, Maintaining variance and k-medians over data stream windows, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.234-243, June 09-11, 2003, San Diego, California
Francisco Ferrer-Troyano , Jess S. Aguilar-Ruiz , Jos C. Riquelme, Discovering decision rules from numerical data streams, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Nilesh Dalvi , Pedro Domingos , Mausam , Sumit Sanghai , Deepak Verma, Adversarial classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
M. Otey , S. Parthasarathy , A. Ghoting , G. Li , S. Narravula , D. Panda, Towards NIC-based intrusion detection, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
George Forman, Tackling concept drift by temporal inductive transfer, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Shi Zhong, Efficient streaming text clustering, Neural Networks, v.18 n.5-6, p.790-798, June 2005
Wei Fan, StreamMiner: a classifier ensemble-based engine to mine concept-drifting data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.1257-1260, August 31-September 03, 2004, Toronto, Canada
Geoff Hulten , Pedro Domingos, Mining complex models from arbitrarily large databases in constant time, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Anand Narasimhamurthy , Ludmila I. Kuncheva, A framework for generating data to simulate changing environments, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: artificial intelligence and applications, p.384-389, February 12-14, 2007, Innsbruck, Austria

Orna Raz , Philip Koopman , Mary Shaw, Semantic anomaly detection in online data sources, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida
Yunyue Zhu , Dennis Shasha, Efficient elastic burst detection in data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Rouming Jin , Gagan Agrawal, Efficient decision tree construction on streaming data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in), Proceedings of the 28th international conference on Very Large Data Bases, p.335-345, August 20-23, 2002, Hong Kong, China
Jimeng Sun , Dacheng Tao , Christos Faloutsos, Beyond streams and graphs: dynamic tensor analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Wei-Guang Teng , Ming-Syan Chen , Philip S. Yu, A regression-based temporal pattern mining scheme for data streams, Proceedings of the 29th international conference on Very large data bases, p.93-104, September 09-12, 2003, Berlin, Germany
Haixun Wang , Jian Yin , Jian Pei , Philip S. Yu , Jeffrey Xu Yu, Suppressing model overfitting in mining concept-drifting data streams, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Hillol Kargupta , Byung-Hoon Park , Sweta Pittie , Lei Liu , Deepali Kushraj , Kakali Sarkar, MobiMine: monitoring the stock market from a PDA, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
Wei Fan, Systematic data selection to mine concept-drifting data streams, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Lilian Harada, Detection of complex temporal patterns over data streams, Information Systems, v.29 n.6, p.439-459, September 2004
Themistoklis Palpanas , Dimitris Papadopoulos , Vana Kalogeraki , Dimitrios Gunopulos, Distributed deviation detection in sensor networks, ACM SIGMOD Record, v.32 n.4, December
Joong Hyuk Chang , Won Suk Lee, Efficient mining method for retrieving sequential patterns over online data streams, Journal of Information Science, v.31 n.5, p.420-432, October   2005
Sreenivas Gollapudi , D. Sivakumar, Framework and algorithms for trend analysis in massive temporal data sets, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
Kevin B. Pratt , Gleb Tschapek, Visualizing concept drift, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Joo Gama , Ricardo Fernandes , Ricardo Rocha, Decision trees for mining data streams, Intelligent Data Analysis, v.10 n.1, p.23-45, January 2006

Charu C. Aggarwal, On Change Diagnosis in Evolving Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.587-600, May 2005
Daniel Kifer , Shai Ben-David , Johannes Gehrke, Detecting change in data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.180-191, August 31-September 03, 2004, Toronto, Canada
Mohamed Medhat Gaber , Shonali Krishnaswamy , Arkady Zaslavsky, Cost-efficient mining techniques for data streams, Proceedings of the second workshop on Australasian information security, Data Mining and Web Intelligence, and Software Internationalisation, p.109-114, January 01, 2004, Dunedin, New Zealand
Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing Data Streams Using Hamming Norms (How to Zero In), IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.529-540, March
Malu Castellanos , Fabio Casati , Umeshwar Dayal , Ming-Chien Shan, A Comprehensive and Automated Approach to Intelligent Business Processes Execution Analysis, Distributed and Parallel Databases, v.16 n.3, p.239-273, November 2004
Joong Hyuk Chang , Won Suk Lee, estWin: Online data stream mining of recent frequent itemsets by sliding window method, Journal of Information Science, v.31 n.2, p.76-90, April     2005
Tho Manh Nguyen , Josef Schiefer , A. Min Tjoa, Sense & response service architecture (SARESA): an approach towards a real-time business intelligence solution and its use for a fraud detection application, Proceedings of the 8th ACM international workshop on Data warehousing and OLAP, November 04-05, 2005, Bremen, Germany
Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Yixin Chen , Guozhu Dong , Jiawei Han , Benjamin W. Wah , Jianyong Wang, Multi-dimensional regression analysis of time-series data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.323-334, August 20-23, 2002, Hong Kong, China
Jiawei Han , Yixin Chen , Guozhu Dong , Jian Pei , Benjamin W. Wah , Jianyong Wang , Y. Dora Cai, Stream Cube: An Architecture for Multi-Dimensional Analysis of Data Streams, Distributed and Parallel Databases, v.18 n.2, p.173-197, September 2005
Weng-Keen Wong , Andrew Moore , Gregory Cooper , Michael Wagner, What's Strange About Recent Events (WSARE): An Algorithm for the Early Detection of Disease Outbreaks, The Journal of Machine Learning Research, 6, p.1961-1998, 12/1/2005
Yasushi Sakurai , Spiros Papadimitriou , Christos Faloutsos, BRAID: stream mining through group lag correlations, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
Chang-Tien Lu , Yufeng Kou , Jiang Zhao , Li Chen, Detecting and tracking regional outliers in meteorological data, Information Sciences: an International Journal, v.177 n.7, p.1609-1632, April, 2007
Yang , Li Lee , Wynne Hsu, Finding hot query patterns over an XQuery stream, The VLDB Journal  The International Journal on Very Large Data Bases, v.13 n.4, p.318-332, December 2004
Marcus A. Maloof , Ryszard S. Michalski, Incremental learning with partial instance memory, Artificial Intelligence, v.154 n.1-2, p.95-126, April 2004
Jrgen Beringer , Eyke Hllermeier, Online clustering of parallel data streams, Data & Knowledge Engineering, v.58 n.2, p.180-204, August 2006
Streaming pattern discovery in multiple time-series, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Zhiyuan Chen , Chen Li , Jian Pei , Yufei Tao , Haixun Wang , Wei Wang , Jiong Yang , Jun Yang , Donghui Zhang, Recent progress on selected topics in database research: a report by nine young Chinese researchers working in the United States, Journal of Computer Science and Technology, v.18 n.5, p.538-552, September
single-pass mining of path traversal patterns over streaming web click-sequences, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1474-1487, 14 July 2006
Mohamed Medhat Gaber , Arkady Zaslavsky , Shonali Krishnaswamy, Mining data streams: a review, ACM SIGMOD Record, v.34 n.2, June 2005
Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
Lukasz Golab , M. Tamer zsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June
Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
data streams;incremental learning;concept drift;decision trees;subsampling;hoeffding bounds