A fast method for frequent pattern discovery with secondary memory

Abstract

Data mining technology has been widely studied and applied in recent years. Frequent pattern mining is one important technical field of such research. The frequent pattern mining technique is popular not only in academia but also in the business community. With advances in technology, databases have become so large that data mining is impossible because of memory restrictions. In this study, we propose a novel algorithm for Fast mining with Secondary Memory, abbreviated as FSM-Mining, to help improve this situation. FSM-Mining saves a part of the information that is not stored in the memory, and through the use of mixed hard disk and memory mining we are able to complete data mining with limited memory. The results of empirical evaluation under various simulation conditions show that FSM-Mining delivers excellent performance in terms of execution efficiency and scalability.

Keywords

Data mining frequent patterns big data

References

Adnan

and Alhajj

, DRFP-tree: disk-resident frequent pattern tree, Applied Intelligence 30 (2009), 84-97.

Agrawal

and Srikant

, Fast algorithms for mining association rules, in: Proc. 20th int. conf. very large data bases, VLDB, 1994, pp. 487-499.

Agrawal

and Srikant

, Quest Synthetic Data Generator. IBM Almaden Research Center, San Jose, California, in, 2009.

Baralis

, Cerquitelli

, Chiusano

and Grand

, P-Mine: Parallel itemset mining on large datasets, in: Data Engineering Workshops (ICDEW), 2013 IEEE 29th International Conference on, IEEE, 2013, pp. 266-271.

Goethals

and Zaki

M.J.

, Frequent itemset mining dataset repository, Frequent Itemset Mining Implementations (FIMI 2003), 2003.

Grahne

and Zhu

, Efficiently using prefix-trees in mining frequent itemsets, in: FIMI, 2003, pp. 123-132.

Grahne

and Zhu

, Mining frequent itemsets from secondary memory, in: Data Mining, 2004. ICDM'04. Fourth IEEE International Conference on, IEEE, 2004, pp. 91-98.

Han

, Pei

, Yin

and Mao

, Mining frequent patterns without candidate generation: A frequent-pattern tree approach, Data Mining and Knowledge Discovery 8 (2004), 53-87.

Hong

T.-P.

, Lin

C.-W.

and Wu

Y.-L.

, Incrementally fast updated frequent pattern trees, Expert Systems with Applications 34 (2008), 2424-2435.

10.

Islam

A.R.

and Chung

T.-S.

, An improved frequent pattern tree based association rule mining technique, in: 2011 International Conference on Information Science and Applications, IEEE, 2011, pp. 1-8.

11.

Javed

and Khokhar

, Frequent pattern mining on message passing multiprocessor systems, Distributed and Parallel Databases 16 (2004), 321-334.

12.

Lai

and ZhongZhi

, An efficient data mining framework on Hadoop using Java persistence API, in: Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on, IEEE, 2010, pp. 203-209.

13.

, Wang

, Zhang

and Chang

E.Y.

, Pfp: parallel fp-growth for query recommendation, in: Proceedings of the 2008 ACM conference on Recommender systems, ACM, 2008, pp. 107-114.

14.

Liang

Y.-H.

and Wu

S.-Y.

, Sequence-Growth: A Scalable and Effective Frequent Itemset Mining Algorithm for Big Data Based on MapReduce Framework, in: Big Data (BigData Congress), 2015 IEEE International Congress on, IEEE, 2015, pp. 393-400.

15.

Lin

C.-W.

, Hong

T.-P.

and Lu

W.-H.

, The Pre-FUFP algorithm for incremental mining, Expert Systems with Applications 36 (2009), 9498-9505.

16.

Lin

K.W.

and Chung

S.-H.

, A fast and resource efficient mining algorithm for discovering frequent patterns in distributed computing environments, Future Generation Computer Systems 52 (2015), 49-58.

17.

Lin

K.W.

and Deng

D.-J.

, A novel parallel algorithm for frequent pattern mining with privacy preserved in cloud computing environments, International Journal of Ad Hoc and Ubiquitous Computing 6 (2010), 205-215.

18.

Lin

K.W.

and Lo

Y.-C.

, Efficient algorithms for frequent pattern mining in many-task computing environments, Knowledge-Based Systems 49 (2013), 10-21.

19.

Lin

W.-T.

and Chu

C.-P.

, Determining the appropriate number of nodes for fast mining of frequent patterns in distributed computing environments, International Journal of Parallel, Emergent and Distributed Systems (2014), 1-13.

20.

Moens

, Aksehirli

and Goethals

, Frequent itemset mining for big data, in: Big Data, 2013 IEEE International Conference on, IEEE, 2013, pp. 111-118.

21.

Pyun

, Yun

and Ryu

K.H.

, Efficient frequent pattern mining based on linear prefix tree, Knowledge-Based Systems 55 (2014), 125-139.

22.

Qiu

, Lan

Y.-J.

and Xie

Q.-S.

, An improved algorithm of mining from FP-tree, in: Machine Learning and Cybernetics, 2004. Proceedings of 2004 International Conference on, IEEE, 2004, pp. 1665-1670.

23.

Schlegel

, Gemulla

and Lehner

, Memory-efficient frequent-itemset mining, in: Proceedings of the 14th International Conference on Extending Database Technology, ACM, 2011, pp. 461-472.

24.

and Alaghband

, Novel parallel method for mining frequent patterns on multi-core shared memory systems, in: Proceedings of the 2013 International Workshop on Data-Intensive Scalable Computing Systems, ACM, 2013, pp. 49-54.

25.

Xia

, Zhou

, Rong

and Zhang

, IPFP: An Improved Parallel FP-Growth Algorithm for Frequent Itemsets Mining, in: Proc. 59th ISI World Statistics Congress, Hong Kong (Session CPS026), Citeseer, 2013, pp. 4034-4039.

26.

Yang

, Shi

, Xu

L.D.

, Liang

and Kirsh

, DH-TRIE frequent pattern mining on Hadoop using JPA, in: Granular Computing (GrC), 2011 IEEE International Conference on, IEEE, 2011, pp. 875-878.

27.

Yang

X.Y.

, Liu

and Fu

, MapReduce as a programming model for association rules algorithm on Hadoop, in: Information Sciences and Interaction Sciences (ICIS), 2010 3rd International Conference on, IEEE, 2010, pp. 99-102.

28.

Yen

S.-J.

, Lee

Y.-S.

, Wang

C.-K.

, Wu

J.-W.

and Ouyang

L.-Y.

, The studies of mining frequent patterns based on frequent pattern tree, in: Advances in Knowledge Discovery and Data Mining, Springer, 2009, pp. 232-241.

29.

Zaki

M.J.

, Parthasarathy

, Ogihara

and Li

, Parallel algorithms for discovery of association rules, Data mining and Knowledge Discovery 1 (1997), 343-373.

30.

Zhou

and Yu

K.-M.

, Tidset-based parallel FP-tree algorithm for the frequent pattern mining problem on PC clusters, in: Advances in Grid and Pervasive Computing, Springer, 2008, pp. 18-28.

31.

Zhou

and Yu

K.-M.

, Balanced Tidset-based parallel FP-tree algorithm for the frequent pattern mining on grid system, in: Proceedings of the 2008 Fourth International Conference on Semantics, Knowledge and Grid, IEEE Computer Society, 2008, pp. 103-108.

32.

Zhou

, Zhong

, Chang

, Li

, Huang

J.Z.

and Feng

, Balanced parallel fp-growth with mapreduce, in: Information Computing and Telecommunications (YC-ICT), 2010 IEEE Youth Conference on, IEEE, 2010, pp. 243-246.