A Parallel Algorithm for Mining Non-Redundant Recurrent Rules from a Sequence Database

Seung-Yong Yoon; Hirohisa Seki

doi:10.20965/jaciii.2019.p0956

single-jc.php

« previous

JACIII Vol.23 No.5 pp. 956-961

doi: 10.20965/jaciii.2019.p0956

(2019)

Paper:

Views over last 60 days: 748

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

Received:

February 20, 2018

Accepted:

May 30, 2019

Published:

September 20, 2019

Keywords:

data mining, sequential rule, recurrent rule, sequence database, parallel algorithm

Abstract

We propose a parallel algorithm for mining non-redundant recurrent rules from a sequence database. Recurrent rules, proposed by Lo et al. [1], 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 NR³ 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 NR³. We also give some experimental results, which show the effectiveness of our proposed method.

Cite this article as:

S. Yoon and H. Seki, “A Parallel Algorithm for Mining Non-Redundant Recurrent Rules from a Sequence Database,” J. Adv. Comput. Intell. Intell. Inform., Vol.23 No.5, pp. 956-961, 2019.

Data files:

References

[1] 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.
[2] R. Agrawal and R. Srikant, “Mining sequential patterns,” Proc. of the 11th Int. Conf. on Data Engineering, pp. 3-14, 1995.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] M. J. Zaki, “Parallel Sequence Mining on Shared-Memory Machines,” J. of Parallel and Distributed Computing, Vol.61, Issue 3, pp. 401-426, 2001.
[11] 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.
[12] R. P. Garg and I. Sharapov, “Techniques for Optimizing Applications: High Performance Computing,” Sun Microsystems, Inc., 2001.
[13] 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.
[14] 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.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] 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.

[2] [2] R. Agrawal and R. Srikant, “Mining sequential patterns,” Proc. of the 11th Int. Conf. on Data Engineering, pp. 3-14, 1995.

[3] [3] 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.

[4] [4] 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.

[5] [5] 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.

[6] [6] 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.

[7] [7] 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.

[8] [8] 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.

[9] [9] 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.

[10] [10] M. J. Zaki, “Parallel Sequence Mining on Shared-Memory Machines,” J. of Parallel and Distributed Computing, Vol.61, Issue 3, pp. 401-426, 2001.

[11] [11] 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.

[12] [12] R. P. Garg and I. Sharapov, “Techniques for Optimizing Applications: High Performance Computing,” Sun Microsystems, Inc., 2001.

[13] [13] 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.

[14] [14] 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.