A Parallel Algorithm for Mining Non-Redundant Recurrent Rules from a Sequence Database
Seung-Yong Yoon and Hirohisa Seki
Department of Computer Science, Nagoya Institute of Technology
Gokiso-cho, Showa-ku, Nagoya 466-8555, Japan
We propose a parallel algorithm for mining non-redundant recurrent rules from a sequence database. Recurrent rules, proposed by Lo et al. , can express “Whenever a series of precedent events occurs, eventually a series of consequent events occurs,” and they have shown the usefulness of recurrent rules in various domains, including software specification and verification. Although some algorithms such as NR3 have been proposed, mining non-redundant recurrent rules still requires considerable processing time. To reduce the computation cost, we present a parallel approach to mining non-redundant recurrent rules, which fully utilizes the task-parallelism in NR3. We also give some experimental results, which show the effectiveness of our proposed method.
-  D. Lo, S.-C. Khoo, and C. Liu, “Efficient Mining of Recurrent Rules from a Sequence Database,” Proc. of the 13th Int. Conf. on Database Systems for Advanced Applications, pp. 67-83, 2008.
-  R. Agrawal and R. Srikant, “Mining sequential patterns,” Proc. of the 11th Int. Conf. on Data Engineering, pp. 3-14, 1995.
-  J. Han, H. Cheng, D. Xin, and X. Yan, “Frequent pattern mining: current status and future directions,” Data Mining and Knowledge Discovery, Vol. 15, Issue 1, pp. 55-86, 2007.
-  C. H. Mooney and J. F. Roddick, “Sequential pattern mining – approaches and algorithms,” ACM Computing Surveys (CSUR), Vol.45, Issue 2, Article No.19, 2013.
-  D. Lo and S.-C. Khoo, “Mining patterns and rules for software specification discovery,” Proc. of the VLDB Endowment, Vol.1, Issue 2, pp. 1609-1616, 2008.
-  F. Wang, J.-H. Wu, C.-H. Huang, C.-C. Chang, and C.-C. Li, “Temporal Specification Mining for Anomaly Analysis,” Proc. of the 11th Asian Symp. on Programming Languages and Systems, pp. 273-289, 2013.
-  D. Lo, B. Ding, Lucia, and J. Han, “Bidirectional mining of non-redundant recurrent rules from a sequence database,” Proc. of the 2011 IEEE 27th Int. Conf. on Data Engineering, pp. 1043-1054, 2011.
-  S. Cong, J. Han, and D. Padua, “Parallel mining of closed sequential patterns,” Proc. of the 11th ACM SIGKDD Int. Conf. on Knowledge Discovery in Data Mining, pp. 562-567, 2005.
-  B. Huynh, B. Vo, and V. Snasel, “An efficient method for mining frequent sequential patterns using multi-Core processors,” Applied Intelligence, Vol.46, Issue 3, pp. 703-716, 2017.
-  M. J. Zaki, “Parallel Sequence Mining on Shared-Memory Machines,” J. of Parallel and Distributed Computing, Vol.61, Issue 3, pp. 401-426, 2001.
-  S.-Y. Yoon and H. Seki, “Parallel Mining of Non-Redundant Recurrent Rules from a Sequence Database,” Proc. of the 18th Int. Symp. on Advanced Intelligent Systems (ISIS2017), pp. 379-386, 2017.
-  R. P. Garg and I. Sharapov, “Techniques for Optimizing Applications: High Performance Computing,” Sun Microsystems, Inc., 2001.
-  P. Fournier-Viger, A. Gomariz, T. Gueniche, A. Soltani, C.-W. Wu, and V. S. Tseng, “SPMF: a Java open-source pattern mining library,” J. of Machine Learning Research, Vol.15, Issue 1, pp. 3389-3393, 2014.
-  R. Kohavi, C. E. Brodley, B. Frasca, L. Mason, and Z. Zheng, “KDD-Cup 2000 organizers’ report: peeling the onion,” ACM SIGKDD Explorations Newsletter, Vol.2, Issue 2, pp. 86-93, 2000.