ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (7): 1452-1464.doi: 10.7544/issn1000-1239.2017.20160553

Previous Articles     Next Articles

Mining Top-k Distinguishing Sequential Patterns Using Spark

Zhang Peng1, Duan Lei1,2, Qin Pan1, Zuo Jie1, Tang Changjie1, Yuan Chang’an3, Peng Jian1   

  1. 1(School of Computer Science, Sichuan University, Chengdu 610065);2(West China School of Public Health, Sichuan University, Chengdu 610041);3(Guangxi Higher Education Key Laboratory of Science Computing and Intelligent Information Processing (Guangxi Teachers Education University), Nanning 530001)
  • Online:2017-07-01

Abstract: DSP (distinguishing sequential pattern) is a kind of sequence such that it occurs frequently in the sequence set of target class, while infrequently in the sequence set of non-target class. Since distinguishing sequential patterns can describe the differences between two sets of sequences, mining of distinguishing sequential patterns has wide applications, such as building sequence classifiers, characterizing biological features of DNA sequences, and behavior analysis for specified group of people. Compared with mining distinguishing sequential patterns satisfying the predefined support thresholds, mining distinguishing sequential patterns with top-k contrast measure can avoid setting improper support thresholds by users. Thus, it is more user-friendly. However, the conventional algorithm for mining top-k DSPs cannot deal with the sequence data set with large-scale. To break this limitation, a parallel mining method using Spark, named SP-kDSP-Miner (Spark based top-k DSP miner), is designed for mining top-k distinguishing sequential patterns from large-scale sequence data set. Furthermore, in order to improve the efficiency of SP-kDSP-Miner, a novel candidate pattern generation strategy and several pruning strategies, as well as a parallel computing method for the contrast scores of candidate patterns are proposed considering the characteristics of Spark structure. Experiments on both real-world and synthetic data sets demonstrate that SP-kDSP-Miner is effective, efficient and scalable.

Key words: parallel computing, sequential pattern, top-k, contrast mining, Spark

CLC Number: