In our model contexts are sequences of file system events. To store all the previously seen contexts we use a trie. Each node in this trie contains a specific file system event. Through its path from the root, each node represents a sequence of file system events, or a context, that has been previously seen. Within each node we also keep a count of the number of times this sequence has occurred.

To easily update our model and use it to determine likely
future events, we maintain an array of pointers, 0 through **m**, that
indicate the nodes which represent the current contexts ( C0 through Cm).
With each new event **A**, we examine the children of each of
the old Ck,
searching for a child that represents the event
**A**. If such a child exists, then this sequence
(the new Ck+1)
occurred before, and is represented by this node's child, so we set
the new Ck+1
(the k+1th element of our array) to
point to this child and increment its count. If no such child is found,
then this is the first time that this sequence has occurred, so we
create a child denoting the event **A** and set the
k+1th
element of our array to point to its node. Once we have updated
each context in our set of current contexts, we have a new state that
describes our file system. Figure 1 extends an example
from Bell [2] to illustrate how this trie would
develop when given the sequence of events * CACBCAABCA*. The first
three tries show how our model builds from the initial (empty)
state. The last trie shows how our model would look after the entire
sequence. The current contexts
at each stage are indicated by the circled letters.

**1 :** Example tries for the sequence **CACBCAABCA**.

Tom M. Kroeger Tue Nov 14 21:39:48 PST 1995