Breadth-First Search Approach for Mining Serial Episodes with Simultaneous Events
Santhosh B. Gandreti, Ibrahim A., P. SESHADRI SASTRY · 2024
Frequent Episode Mining is a well-studied problem in the area of temporal data mining. There are many methods for mining serial, parallel and general partial order episodes. However, many of these existing methods are not very effective in capturing patterns where some events are constrained to occur simultaneously. There are a few methods for discovering such serial episodes; these methods use Depth-First Search based approaches and are not very efficient. In this paper, we propose a novel efficient algorithm for mining frequent serial episodes with simultaneous events. Our algorithm follows the Breadth-First Search approach, and, for this, we present a novel candidate generation method and formally prove its correctness. We also propose a small but significant modification to the traditional Finite State Automata based frequency counting which results in considerable speed-up of the frequency counting step. Through several simulation experiments involving both synthetic and real data, we demonstrate the efficiency of the proposed algorithm.