论文部分内容阅读
随着5G高速移动网络相关技术的逐步成熟,万物互联的时代即将到来。移动终端的大规模普及带来了数据规模的跨越式增长,以大数据算法为首的数据驱动型新兴应用得到了长足发展。频繁模式挖掘技术是这类算法中揭示数据背后有价值的隐藏趋势的常用方法。传统的面向动态随机存取存储器(DRAM)设计的频繁模式挖掘技术受限于硬件的低容量、高功耗、不可持久化等特性,逐渐无法应对大规模的数据存储与挖掘需求,极大地降低了频繁模式挖掘应用的可靠性与扩展性,从而限制了技术的应用场景、提高了部署难度。
近年来,多种新型非易失性存储器件(No-Volatile Memory,简称NVM)涌现,其低延迟、按字节寻址等特性提供了接近于DRAM的读写性能,更重要的是,其低功耗、高存储密度、非易失性的优势弥补了DRAM存储系统在可靠性与扩展性上的不足。然而,现有的频繁模式挖掘算法是为动态随机存取存储器(DRAM)设计的,没有充分考虑到非易失性内存的特性。具体来说,非易失性内存具有写耐久度低的缺陷,以及不对称的读写速度与功耗,直接把传统的频繁模式挖掘技术应用到非易失性内存存储器中会导致严重的性能与能耗问题。
因此,考虑到非易失性内存带来的新特性,在本文中,提出了一种写磨损感知的频繁模式挖掘算法优化方案WFPM。首先研究磨损均衡的频繁模式树项头表滑动计数策略研究,减少递增计数器中各比特位的最大磨损度,解决比特位之间磨损不均的问题。其次,提出基于频繁模式增长的零拷贝数据集排序机制研究,降低频繁模式挖掘树在增长过程中的写开销,提高频繁模式挖掘树的增长效率。第三,提出排序的子节点哈希链表算法,通过减少高频次项目的搜索次数来优化频繁模式挖掘树的读取操作。
最后,本文实现了所提出技术的原型并在配有Linux系统的工作站中进行实验验证。收集了来自各种应用场景的实际数据集,通过运行的一系列实验,对提出的WFPM进行了性能评估。实验结果表明,与最先进的面向NVM的频繁模式挖掘方案EvFP-tree相比,WFPM在运行各数据集时达到了平均32.0%的性能提升,并使项头表的NVM寿命延长了7.4倍。
近年来,多种新型非易失性存储器件(No-Volatile Memory,简称NVM)涌现,其低延迟、按字节寻址等特性提供了接近于DRAM的读写性能,更重要的是,其低功耗、高存储密度、非易失性的优势弥补了DRAM存储系统在可靠性与扩展性上的不足。然而,现有的频繁模式挖掘算法是为动态随机存取存储器(DRAM)设计的,没有充分考虑到非易失性内存的特性。具体来说,非易失性内存具有写耐久度低的缺陷,以及不对称的读写速度与功耗,直接把传统的频繁模式挖掘技术应用到非易失性内存存储器中会导致严重的性能与能耗问题。
因此,考虑到非易失性内存带来的新特性,在本文中,提出了一种写磨损感知的频繁模式挖掘算法优化方案WFPM。首先研究磨损均衡的频繁模式树项头表滑动计数策略研究,减少递增计数器中各比特位的最大磨损度,解决比特位之间磨损不均的问题。其次,提出基于频繁模式增长的零拷贝数据集排序机制研究,降低频繁模式挖掘树在增长过程中的写开销,提高频繁模式挖掘树的增长效率。第三,提出排序的子节点哈希链表算法,通过减少高频次项目的搜索次数来优化频繁模式挖掘树的读取操作。
最后,本文实现了所提出技术的原型并在配有Linux系统的工作站中进行实验验证。收集了来自各种应用场景的实际数据集,通过运行的一系列实验,对提出的WFPM进行了性能评估。实验结果表明,与最先进的面向NVM的频繁模式挖掘方案EvFP-tree相比,WFPM在运行各数据集时达到了平均32.0%的性能提升,并使项头表的NVM寿命延长了7.4倍。