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.
