基于持久性存储器的频繁模式挖掘算法优化研究

摘要

有效挖掘给定数据集中频繁出现的模式是数据挖掘领域中的重要问题，对数据进行频繁模式挖掘能够揭示隐藏在数据集后面的有效信息。非易失性存储器（NVM）的发展为持久性内存频繁模式挖掘算法提供了机遇，但非易失性存储器的读写不对称、寿命有限等缺陷又成为了非易失性存储器完全替代动态随机存取内存（DRAM）的障碍。虽然利用频繁模式树（FP-tree）结构是进行频繁模式挖掘的有效方法，但若将频繁模式挖掘算法应用于非易失性存储器上时，FP-tree构建过程会产生许多对非易失性存储器的不必要写操作，因此会极大的影响算法性能。本文的目标是实现高性能、高能效、可持久的频繁模式挖掘，对挖掘性能、能耗和系统持久性进行联合优化。
　　为了实现可持久、高性能的频繁模式挖掘算法，本文采用非易失性存储器作为系统内存，针对频繁模式挖掘算法以及非易失性存储器的特性，在此平台上提出基于非易失性存储器的频繁模式挖掘算法；为了增加算法的可扩展性，进一步提出基于非易失性存储器的可扩展频繁模式挖掘算法；并通过实验对比分析算法有效性。具体工作如下：
　　第一，传统频繁模式挖掘算法会对内存产生很多读和写操作。由于非易失性存储器读写不对称且寿命有限，对其过多的写操作，会影响系统性能，还会降低存储器寿命。为此，根据非易失性存储器和频繁模式挖掘算法的特性，本文提出基于非易失性存储器的频繁模式挖掘算法，减少频繁模式挖掘算法中不必要的更新操作，达到提高算法性能，降低系统能耗，延长非易失性存储器寿命的目的。
　　第二，待挖掘数据量的增大为频繁模式挖掘的性能带来了挑战。在本文所提出的改进优化后的频繁模式挖掘算法基础上，针对待挖掘的海量数据，本文提出并行的频繁模式挖掘算法。同时考虑非易失性存储器的缺陷问题，尽可能减少写操作次数。通过增强在非易失性存储器上频繁模式挖掘方法的可扩展性，达到进一步提升频繁模式挖掘算法性能的目的。
　　最后，本文在Linux系统中进行模拟仿真实验，以验证所提出算法的有效性。实验结果表明，在单核系统上，与传统的频繁模式挖掘算法相比，本文提出的优化算法可以平均提升挖掘性能40.28％，平均提升存储器寿命87.20％，能耗平均降低50.30％；在多核系统上，与单核系统上运行的算法相比，本文提出的可扩展频繁模式挖掘算法挖掘性能平均提升63.67%。

目录

1 绪 论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 论文主要研究内容

1.4 论文组织结构

2 背景技术分析

2.1 频繁模式挖掘技术

2.2 FP-tree简介

2.3 非易失性存储器

2.4 现有算法存在的问题

2.4 本章小结

3 基于非易失性内存的频繁模式挖掘算法

3.1 惰性计数算法

3.2 均匀翻转编码方案

3.3 本章小结

4 基于非易失性内存的可扩展频繁模式挖掘算法

4.1 基于非易失性内存的并行频繁模式挖掘算法框架

4.2 链接合并算法

4.3 哈希散列算法

4.4 本章小结

5 实验测试

5.1 测试环境及测试方法

5.2 EvFP-tree测试结果及分析

5.3 PevFP-tree测试结果及分析

5.4 本章小结

6 总结与展望

6.1 工作总结

6.2 展望

致谢

参考文献

附录

A. 作者在攻读学位期间内已发表或接收的论文目录

B. 作者在攻读学位期间内参加的科研项目：

C. 作者在攻读学位期间内申请的专利