检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

面向文件级重复数据删除的稀疏索引技术

面向文件级重复数据删除的稀疏索引技术

作者：尚颖丹国防科学技术大学

学位级别：硕士

重复数据删除技术是近几年来存储领域的研究热点，在提高存储利用率、减少数据传输带宽占用量方面表现优异，近几年来广泛应用在数据备份系统、归档存储系统、远程灾备等系统中。多数大规模数据中心中存在大量重复的数据，极大的浪费了... 详细信息

重复数据删除技术是近几年来存储领域的研究热点，在提高存储利用率、减少数据传输带宽占用量方面表现优异，近几年来广泛应用在数据备份系统、归档存储系统、远程灾备等系统中。多数大规模数据中心中存在大量重复的数据，极大的浪费了存储资源及能耗。云计算数据中心中存在大量虚拟机映像文件，这些虚拟机映像文件中存在大量的重复数据。删除其中的重复数据不仅可以节省磁盘空间，也能减少虚拟机映像文件传输时占用的带宽，提高虚拟机映像文件的访问及分发速度。重复数据删除中普遍存在的磁盘访问瓶颈问题制约了系统的性能，现有解决磁盘瓶颈问题的方法主要包括Data Domain提出的基于bloom filters、SISL和局部性保持，稀疏索引及Extreme Binning的解决方案。已有解决方案通常利用数据访问的局部性来减少内存中索引数量，减少每个索引查找时的磁盘I/O次数。这些研究方案在基于文件的更大粒度的重复数据删除下并不适用，均无法达到解决重复数据删除中的磁盘访问瓶颈问题。本文首先针对云计算中大量虚拟机映像文件下基于文件的重复数据删除中存在的磁盘访问瓶颈问题，提出了一种基于随机抽样的重复数据删除方法。内存中的索引不是全部的文件索引而是从全部文件索引中进行随机抽样出的部分样本索引，从而减少内存中索引的总数量。在文件索引的重复检测时利用虚拟机映像文件重复的局部性特征利用部分文件索引在内存中命中的情况推断目录中其他文件索引的命中情况。使得目录中每个文件索引的重复检测工作无需多次访问磁盘。通过设计实现一般情况下和随机抽样下的重复数据删除算法，对比随机抽样重复数据删除效果可知，当内存无法放置整个索引表的情况时，随机抽样的重复数据删除下内存稀疏索引数为原有索引数的1/10，不仅保证了可观的重复数据删除比例，同时减少了大量的磁盘访问量，解决了当内存无法放置整个索引表时检测性能急剧下降的问题，提高了重复数据删除系统的性能。针对基于文件的重复数据检测中索引容量瓶颈的问题，为提高稀疏索引下重复数据删除比例，进一步提出了基于分组目录的重复数据删除方式。首先对虚拟机映像文件的树结构进行相近粒度的划分为分组目录，对分组目录采用随机抽样及基于Broder理论的抽样方法，利用分组目录的样本文件索引建立内存的稀疏索引，在分组目录的基础上实现了重复数据删除方案。实现方案并利用实验数据检验并验证了虚拟机映像文件重复的局部性。针对不同抽样比例因子对比了重复数据删除效果，结果表明，当抽样内存索引数为原有的1/10时，利用虚拟机映像文件重复固有的局部性特征实现的基于分组目录的稀疏索引能够达到96%以上的重复数据删除比例，减少了内存索引数量，很好的避免了磁盘访问瓶颈问题。实验分析分组目录抽样中随机抽样及基于Broder理论的抽样方法下的重复数据删除比例，通过设定不同分组目录划分大小分析基于分组目录的重复数据删除比例的影响因子。最后根据实验结果对比基于分组目录稀疏索引和基于随机抽样的稀疏索引下的重复数据删除效果。针对集中式重复数据删除系统有限的可扩展性提出了分布式环境下的重复数据删方案，实现了重复数据删除过程的分布并行化，数据的分布式存储，设计简单的路由算法从而使得多个数据节点间的独立自治。提出了简单易行的数据迁移策略，并分析分布式环境下重复数据删除方案的特点、可实施性及对整体系统性能的影响。避免分布式环境下数据节点间相互通信带来的负面影响，实现数据节点间的独立自治，达到重复数据删除过程的分布并行化目的。

关键词：重复数据删除技术稀疏索引虚拟机映像文件文件重复局部性

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于稀疏索引算法的碱基序列比对

基于稀疏索引算法的碱基序列比对

作者：李林森深圳大学

学位级别：硕士

随着第二代测序技术(NGS)成为DNA测序的主流,科研人员得以在短时间内低成本地获取大量DNA碱基序列数据,然而如何在这海量数据中提取有用信息进行生物信息研究却成为新的挑战。一方面是越来越多的物种基因组(genome)序列图谱被描绘出来,... 详细信息

随着第二代测序技术(NGS)成为DNA测序的主流,科研人员得以在短时间内低成本地获取大量DNA碱基序列数据,然而如何在这海量数据中提取有用信息进行生物信息研究却成为新的挑战。一方面是越来越多的物种基因组(genome)序列图谱被描绘出来,另一方面则是对这些数据分析利用的滞后,测序技术的进步未能真正带动生物科技的全面发展。所以当务之急是研发出更好的生物信息分析软件,挖掘DNA序列中包含的生物学意义,让生物技术更好地造福人类。随着已测得的基因组序列越来越多,许多时候我们需要将海量的短读数据(short-read)比对到多个基因组中。然而同源基因组间具有高度的相似性,传统的分别比对方式,实际上进行了许多重复性比对。本文提出一种稀疏索引算法,通过对齐特定碱基并向两侧扩增,实现序列的快速比对。利用这种算法能够快速提取多个基因组间相似的碱基序列,剔除重复序列后,再与短读序列进行比对,这样可以大大加快比对速度。同时这种针对特定碱基的稀疏索引,同样能够进行短读对基因组的比对,且比传统比对方法更加高效。论文首先介绍了当前DNA序列比对研究的背景与现状,包括测序技术的发展、高效的序列比对工具、BWT比对算法的原理。然后详细介绍了稀疏索引算法,包括其原理及实现序列比对的过程,分析了该算法相对于BWT等传统算法的优缺点。随后以此算法为基础实现了两个应用:基因组间比对与短读对基因组的比对,它们分别用于物种鉴别与基于参考基因组的测序数据压缩。通过与传统方法的对比实验,充分说明了稀疏索引算法占用内存小、比对速度快的优点。最后,论文针对不断发展的测序技术以及测序数据的积累,提出比对算法必须满足海量数据处理的要求,稀疏索引算法的未来发展方向在于并行化研究。

关键词：稀疏索引基因组间序列比对 Comp Map工具短读最优匹配 Read Best Map工具

基于改进Sparse Indexing的多负载消冗方法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

电子科技大学学报 2013年第5期42卷 734-739页

作者：王灿秦志光杨磊杨皓电子科技大学计算机科学与工程学院成都611731 网络与数据安全四川省重点实验室成都611731

针对现有的Sparse Indexing方法不能有效处理小文件备份负载的问题,提出了一种以Broder扩展定理为理论依据的最小特征采样算法,该算法可以对不同形式的备份负载进行有效的特征采样。在此算法的基础上,设计了一种多负载重复数据消除方法... 详细信息

针对现有的Sparse Indexing方法不能有效处理小文件备份负载的问题,提出了一种以Broder扩展定理为理论依据的最小特征采样算法,该算法可以对不同形式的备份负载进行有效的特征采样。在此算法的基础上,设计了一种多负载重复数据消除方法,该方法通过对备份负载进行特征采样,仅在内存中维护完整索引的一个很小的子集,并通过批量读入分块标识符,摊销了磁盘访问开销,提高了吞吐量。实验结果表明,该方法对混合备份负载的压缩比是Sparse Indexing的2.04倍,而吞吐量与Sparse Indexing相当。该方法适用于需要处理多种形式备份负载的高性能重复数据消除系统。

关键词：重复数据消除磁盘瓶颈最小特征采样稀疏索引吞吐量

在线全文

学校读者我要写书评

暂无评论

关于索引文件的进一步探讨

泰山学院学报 1999年第6期24卷 38-39页

作者：郇正良泰安师专数学与计算机科学系讲师泰安271000

本文探讨了索引文件的组织结构及访问方式,并对两种索引文件进行了分析.

关键词：索引内存关键字稀疏索引稠密索引

在线全文

学校读者我要写书评

暂无评论

关于顺序相关性的近似满足

山东大学学报(自然科学版) 1983年第1期 53-60页

作者：董继润山东大学计算机科学系

本文介绍了顺序相关的概念,并讨论了稠密和稀疏索引的问题。目的是给出顺序相关的一种近似满足形式,称为“几乎处处”近似满足。并且说明,在不增加存取时间的情况下,可用它减少索引空间。

关键词：稀疏索引支票数据库信用货币数据库系统稠密索引索引表索引空间属性域属性集存取时间关系模型数据模型相关性

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

关系数据库和顺序相关性

山东大学学报(自然科学版) 1983年第4期 31-40页

作者：董继润山东大学计算机系

本文分两部分,第一部分介绍关系数据库模型,大部分内容取自有关文献,但笔者试图以一种统一的观点对关系数据库的某些基本概念作一介绍,并给出定理2.2的一个新的证明方法。第二部分讨论顺序相关性,其中包括顺序相关性的定义和性质,并给... 详细信息

本文分两部分,第一部分介绍关系数据库模型,大部分内容取自有关文献,但笔者试图以一种统一的观点对关系数据库的某些基本概念作一介绍,并给出定理2.2的一个新的证明方法。第二部分讨论顺序相关性,其中包括顺序相关性的定义和性质,并给出了利用顺序相关性建立稀疏索引,增强数据库有效实现,以节省存聍空间和存取时间的索引方案。

关键词：关系数据库存取时间存贮空间关系模型数据库属性域稀疏索引形式定义稠密索引顺序文件相关性

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

多维数据的树形结构组织方法

科技资讯 2007年第13期5卷 42-43页

作者：曹丽勇韩晓虎河北行政学院基础部河北石家庄050031

为实现数据库的快速查询,我们引入了索引结构,.目前已有多种不同的数据结构可用作索引.,稀疏索引、稠密索引、辅助索引、散列表、B树等等。但随着多媒体数据库与数据挖掘等应用领域的发展,只建立一维索引已经不能解决问题,随后我们引入... 详细信息

为实现数据库的快速查询,我们引入了索引结构,.目前已有多种不同的数据结构可用作索引.,稀疏索引、稠密索引、辅助索引、散列表、B树等等。但随着多媒体数据库与数据挖掘等应用领域的发展,只建立一维索引已经不能解决问题,随后我们引入了多维索引。所谓多维索引,就是关系的每个属性都可以看成一维,而所有的元组就是在由这些维上定义的空间中的点。多维索引结构大概分为两种,一种是类散列结构,一种是树形结构。下面我主要介绍多维数据的树形结构组织方法。

关键词：稀疏索引稠密索引辅助索引散列表 B树多码索引 kd树四叉树 R树