Discovering Injective Episodes with General Partial Orders

  • Avinash Achar ,
  • Srivatsan Laxman ,
  • Raajay Viswanathan ,
  • P.S. Sastry

Data Mining and Knowledge Discovery (DAMI) | , Vol 25: pp. 67-108

Frequent episode discovery is a popular framework for temporal pattern discovery in event streams. An episode is a partially ordered set of nodes with each node associated with an event type. Currently algorithms exist for episode discovery only when the associated partial order is total order (serial episode) or trivial (parallel episode). In this paper, we propose efficient algorithms for discovering frequent episodes with unrestricted partial orders. These algorithms can be easily specialized to discover only serial or parallel episodes. Also, the algorithms are flexible enough to be specialized for mining in the space of certain interesting subclasses of partial orders. We point out that frequency alone is not a sufficient measure of interestingness in the context of partial order mining. We propose a new interestingness measure for episodes with unrestricted partial orders which, when used along with frequency, results in an effifficient scheme of data mining. Simulations are presented to demonstrate the effectiveness of our algorithms.