Efficient Depth-First Search Approach for Mining Frequent Chain Episodes

Frequent episode mining is a popular method of finding temporal patterns in sequential data.Here the data is viewed as a sequence of events characterized by an event-type and the time of occurrence, and, the episodes are partially ordered sets of event-types, representing a temporal pattern.Frequently occurring episodes capture temporal dependencies in the data.There are efficient mining algorithms for restricted classes of episodes such as serial episodes (where the partial order is a total order) and parallel episodes (where the partial order is null).Chain episodes are the most general form of episodes (imposing the least restrictions on the partial order) that have been considered in the literature.At present, the only mining algorithms available for chain episodes are based on the Breadth-First-Search (BFS) approach.In this paper, we present a new and efficient algorithm for mining chain episodes based on the Depth-First-Search (DFS) strategy.Our algorithm is capable of pruning the search space using the apriori idea (which is normally used only in BFS methods) and it also includes a partial frequency closure check for pruning some redundant frequent episodes.We show through simulations that the algorithm is more efficient than the existing BFS methods.