TCS-TR-A-09-38

Date: Wed May 27 22:50:03 2009

Title: Mining Frequent Bipartite Episode from Event Sequences

Authors: Takashi Katoh, Hiroki Arimura, and Kouichi Hirata

Contact:

First name: Hiroki
Last name: Arimura
Address: Division of Computer Science, Graduate School of Information Science and Technology, Hokkaido University N14 W9, 060-0814 Sapporo, Japan
Email: arim@ist.hokudai.ac.jp

Abstract. In this paper, first we introduce a bipartite episode of the form A -> B for two sets A and B of events, which means that every event of A is followed by every event of B. Then, we present an algorithm Bipar that finds all frequent bipartite episodes from an input sequence without duplication in O(|\Sigma| ||S||) time per an episode and in O(|\Sigma|^2 n) space, where \Sigma is an alphabet, || S || is total input size, and n is the length of the input sequence. Finally, we give experimental results on artificial sequences with varying several parameters to evaluate the efficiency of the algorithm.