Optimization Of Frequent Pattern Mining Algorithm Based On Persistent Memory

Effective mining of frequent patterns in a given data set is an important problem in the field of data mining.Frequent pattern mining of data can reveal the effective information hidden behind the data set.The development of nonvolatile memory(NVM)provides an opportunity for frequent pattern mining algorithms in persistent memory.However,the extra operational constraints of NVMs,such as the asymmetries of read and write operations,and limited lifetime,have created a barrier from directly using NVMs as main memory.Although the use of frequent pattern tree(FP-tree)structure is an effective way to carry out frequent pattern mining,but when the frequent pattern mining algorithm applied to nonvolatile memory,FP-tree construction process will produce a lot of unnecessary write operation on non-volatile memory.It will greatly reduce the energy efficiency and affect the performance of the algorithm.This work is motivated by the serious demands of a high-performance in-memory frequent-pattern mining strategy,with joint optimization over the mining performance and system durability.Our goal is to realize the ideals of high-performance,energy-efficient in-memory data analytics,while guaranteeing satisfactory durability of the mining memory/storage systems.In order to realize the persistent and high-performance of frequent pattern mining,this paper uses nonvolatile memory as the system memory.By considering the characteristics of frequent pattern mining algorithm and nonvolatile memory,this paper proposes a frequent pattern mining algorithm based on nonvolatile memory.So as to increase the scalability of the proposed algorithm,we also propose a scalable frequent pattern mining algorithm based on nonvolatile memory.This work makes the following contributions:First,the traditional frequent pattern mining algorithm will generate a lot of read and write operations on memory.Due to the asymmetries of read and write operations as well as limited lifetime of nonvolatile memory,the excessive write operation will not only affect the system performance,but also reduce lifetime of memory.By considering the characteristics of nonvolatile memory and frequent pattern mining algorithm,this paper proposes a frequent pattern mining algorithm named Ev FP-tree based on nonvolatile memory.The proposed algorithm can reduce the unnecessary update operation,improve the performance of algorithm,reduce energy consumption,and extend lifetime of non-volatile memory.Second,the increase of the amount of data to be excavated causes a challenge for the performance of frequent pattern mining.Based on EvFP-tree,we propose a parallel frequent pattern mining algorithm named PevFP-tree to enhance the scalability of EvFP-tree.And we also take the defects of nonvolatile memory into account,try to minimize the number of write operations.By enhancing the scalability of frequent pattern mining methods on nonvolatile memory,the performance of frequent pattern mining algorithms is further improved.Finally,we conduct experiments based on a series of realistic traces in Linux system to verify the validity of the proposed algorithm.Compared with the traditional frequent pattern mining algorithm,the experimental results show that EvFP-tree can improve the mining performance and system lifetime by 40.28% and 87.20% on average,respectively.And EvFP-tree reduces the energy consumption by 50.30% on average.Compared with the algorithm running on the single-core system,the mining performance of PevFP-tree is improved by 63.67% on average.