Abstract
Mining serial episode rules from large databases is an important issue and has been studied by many researchers. A serial episode is a sequence of events that occur close to each other. A serial episode is frequent if it occurs frequently. A serial episode rule is composed of two frequent serial episodes X and Y where Y often occurs after X occurs in a time constraint. In recent years, the concept of data streams is motivated by some applications such as network monitoring and traffic monitoring. The streaming data arrive in high rate and can be infinite. Therefore, discovering serial episode rules over data streams is challenging due to limited CPU and memory resources. In this work, we propose a framework for serial episode rule mining over data streams. We use a prefix trie such that the frequent serial episodes having the same prefix can be represented in a compact way. Each path of the trie represents an episode X and the corresponding frequency is recorded in the last node of the path. Moreover, the time positions of X are kept in the node. Since all the frequent episodes and the sufficient information are recorded, the serial episode rules can be generated by traversing the trie. To save the memory, we periodically remove the serial episodes whose frequencies are low from the tries. However, the trie can still be too large. As a result, the trie is revised by only keeping the time difference of any two events instead of all the time positions for each serial episode. The number of event types is much less than the number of episodes. Hence, the advanced method is space-efficient. Moreover, we also prove that each episode rule can be generated from the revised data structure. The experiments show that the advanced method outperforms the original one in both the memory usage and rule generating time.