Research On Optimization Of Frequent Pattern Mining Algorithm Based On No-volatile Memory

With the gradual maturity of 5G high-speed mobile network related technologies,the era of the Internet of Everything is coming.The large-scale popularization of mobile terminals has brought about a leap in data scale,and data-driven emerging applications led by big data algorithms have been greatly developed.Among them,the frequent pattern mining technology is a common method for revealing valuable hidden trends behind data.The traditional frequent pattern mining technologies designed for dynamic random access memory(DRAM)are limited by the characteristics of hardware such as low capacity,high power consumption,and unsustainability.It is gradually unable to cope with the needs of large-scale data storage and mining,which greatly reduces The reliability and scalability of frequent pattern mining applications,and limits the application scenarios and increases the difficulty of deployment.In recent years,a variety of new types of non-volatile memory(NVM)have emerged.Their low latency,byte-addressability and other characteristics provide DRAM-class read/write performance.More importantly,the advantages of their low power consumption,high storage density and non-volatility make up for the lack of reliability and scalability of DRAM storage systems.However,the existing frequent pattern mining algorithms are designed for dynamic random access memory(DRAM)and does not fully consider the hardware characteristics of the novel non-volatile memory(NVM).Specifically,NVM has the disadvantages of low write endurance,as well as asymmetric read and write speeds and power consumption.Direct application of traditional frequent pattern mining technologies to NVM will cause serious performance and energy consumption problems.Therefore,considering the new features brought by NVM,in this thesis,we propose an efficient and wear-leveling-aware frequent pattern mining scheme,WFPM.First of all,we study the wear-leveling-aware sliding counter strategy of the header table in the frequent pattern tree,reducing the maximum wear degree of each bit in the increment counter,and solve the problem of uneven wear between bits.Secondly,we propose a copy-free growth mechanism based on frequent pattern growth to reduce the write overhead of frequent pattern mining trees during the growth process,and improve the growth efficiency of frequent pattern mining trees.Thirdly,a sorted hash walk algorithm is proposed to optimize the reading operation of frequent pattern mining trees by reducing the number of searches for high-frequency items.Finally,this thesis implements the prototype of the proposed technologies and conducts experimental verification in a workstation equipped with a Linux system.We collected realistic data sets from various application scenarios and evaluated the performance of the proposed WFPM through a series of experiments.Experimental results show that,compared with the state-of-the-art NVM-oriented frequent pattern mining scheme Ev FP-tree,WFPM achieves the performance improvement of 32.0% on average,and extends the lifetime of the header table by 7.4 times.