基于频繁序列挖掘的预取方法研究

《基于频繁序列挖掘的预取方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号_________学号M201172385学校代码10487密级硕士学位论文基于频繁序列挖掘的预取方法研究学位申请人：王培群学科专业：计算机系统结构指导教师：构王芳教授答辩日期：2014-1-21万方数据AThesisSubmittedinPartialFulfillmentoftheRequirementsFortheDegreeofMasterofEngineeringResearchforPrefetchingMethodBasedonFrequentPatternMiningCandidat

2、e:WangPeiqunMajor:ComputerArchitectureSupervisor:Prof.WangFangHuazhongUniversityofScienceandTechnologyWuhan,Hubei430074,P.R.ChinaJan.,2014万方数据华中科技大学硕士学位论文独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献

3、的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在________年解密后适用本授权书。本论文属于不保密□。（请在以上方框内打“√”）学位论文

4、作者签名：指导教师签名：日期：年月日日期：年月日万方数据华中科技大学硕士学位论文摘要在存储系统中，CPU的处理速度远大于磁盘等I/O设备的读写速度，两者间的速度不匹配严重影响了系统整体性能。预取技术能够有效地弥补I/O设备与CPU之间的速度差异，因此被广泛应用。随着云技术、虚拟化技术的普及，集中存储前端往往承载着各种应用服务，导致前端单一应用负载内在的访问局部性和顺序性在后端被破坏，以往广泛采用的顺序预取不能很好地发挥作用。针对这样的问题，提出一种基于频繁序列挖掘的预取算法，以改进I/O预取效率，提高存储

5、性能。然而目前已提出的许多频繁序列挖掘算法针对的问题基本上是相关性挖掘、关联性分析等对时间响应没有严格要求的场景，这类场景更多的是关注序列挖掘的准确性从而相对地忽视了挖掘效率。但实时预取等时间关键的应用场景更多关注响应时间，现有的频繁序列挖掘算法往往会产生较大的时间开销。因此为了降低挖掘开销，适应存储系统等场景的在线连续运行，快速的频繁序列挖掘算法TcMiner能够有效地解决时间关键场景的局限性带来的问题。基于TcMiner预取算法利用频繁序列挖掘技术对已发生的I/O访问行为进行快速分析，获取相关性强的数

6、据序列，形成预取规则并采用子树间无包含关系的字典树（TireTree）来保存数据块间的相互关系，从而进行精度较高的预取操作。同时，为了适应不同的负载环境，在采用字典树进行预取的基础上进一步改进的多步预取和子树切割两种算法也可以进一步提高预取算法的精度。测试表明，在内存占数据量5%的情况下，基于TcMiner的预取算法及其改进方法相比于LRU算法有明显提升，相比于C-miner采用的预取算法准确率提升22%~26%。当内存限定从256MB下降到32MB时，基于TcMiner的预取算法精度从93%下降到88%

7、，而C-miner采用的预取算法精度从75%下降到52%，在内存较小的情况下，基于TcMiner的预取算法具有更好的适用性。关键字：数据相关性，频繁序列挖掘，时间关键，预取算法，字典树I万方数据华中科技大学硕士学位论文AbstractInstoragesystem,theprocessspeedofCPUisfarfasterthantheaccessspeedofI/Odevicessuchasdisk,andthespeedgapbetweenthemseriouslyreducetheperform

8、anceofsystem.Inordermakeupthereductioncausedbyspeedgap,prefetchingtechniqueiswidelyusedinmanyenvironmentandapplication.Withmoreattemptandapplicationincloudandvirtualizationtechnology,thefrontendofstorageusuallysuppo