A General Depth-First-Search based Algorithm for Frequent Episode Discovery

Frequent episode discovery is a popular framework in an event sequence. Existing algorithms yield good results for mining frequent episodes under their support definitions, but each of them is difficult or impossible to directly mine frequent episodes when the support definition is changed. To meet the needs of flexible support definitions of users, an algorithm called FEM-DFS is proposed to mine frequent episodes in this paper. After scanning the given event sequence one pass, FEM-DFS finds frequent episodes in a depth-first-search fashion, stores frequent episodes in a shared prefix/suffix tree and compresses the search space of frequent episodes by utilizing monotonicity, prefix monotonicity or suffix monotonicity. Experimental evaluation demonstrates the effectiveness of the proposed algorithm.