用于内存数据库的Hash索引的设计与实现

电信领域已成为数据密集型行业,需要高性能的数据库系统作为支撑系统,基于磁盘的数据库系统不能满足"实时"、"近实时"访问数据库的需求,将数据库核心数据驻留在内存中,可以使用内存数据库来满足需求。Hash索引是数据库系统中广泛使用的索引技术之一,它能够快速地访问数据,易于设计和实现。该文根据内存数据库的特点,为电信网管系统的内存数据库设计并实现了Hash索引。

时态数据的可变Hash索引

索引技术是时态数据库查询优化的重要方法之一。本文提出的可变 Hash(VH)索引是建立在时间属性上的一种新的动态索引技术,主要目的是提高时态数据库快照查询的效率。由于时间的不确定性,在时态数据的时间属性上建立 Hash 索引比较困难。VH 索引克服了 Hash 索引这一难点,提出了索引参数可变的思想,并应用 B^+-树对Hash 参数进行组织。查询时由时间值在 B^+-树上获得 Hash 参数,进而确定数据的存储地址。通过对其时间复杂度和空间复杂度的理论分析以及实验验证,表明该索引技术可以减少索引查找以及读取数据的 I/O 次数,并具有理想的空间利用率。

基于Hash索引的高通量基因序列比对并行加速技术研究

近年来随着高通量基因测序技术的迅速发展，测序成本和周期都得到了大幅降低．然而，新一代测序技术海量数据生成能力以及各类测序算法蕴含的高并发性却对现有计算机的运算能力提出了新挑战．以一个基于Hash索引算法实现的开源重测序程序（PerM）为例，研究了在商用多核CPU上加速该应用程序的关键技术．在一个64核SMP系统上的实验结果证明，提出的优化技术可以使Cache缺失率降低90％，性能提升4～11倍．接下来探讨了在一个包含XilinxLX330FPGA的加速卡上设计实现专用并行加速系统的相关问题．作为原型验证系统，在基于FPGA的PCIe加速卡上设计并实现了包含11个处理单元的脉动陈列并行计算系统．和IntelXeonX75508核CPU相比，提出的并行加速器有30～65倍性能功耗比优势．

基于共享内存的能量管理系统实时库非主键HASH索引

实时库是能量管理系统的核心之一,大部分实时数据的处理基于实时库。引入索引能够极大地优化实时库查找操作,提高实时库性能。文中介绍了HASH索引的查找算法和实现方式,设计了针对"父找子"型关系查找的双溢出型HASH索引,并介绍了其数据结构和查找算法。分析数据表明,双溢出索引适合于"父找子"型关系的查找,具有很高的查找效率。

一种改进的基于Hash算法及概率的k-mer索引方法

文章基于k-mer编码建立了Hash线性索引模型。其基本思想是统计碱基字符出现的频数,将字符进行哈弗曼编码以得到最短的字符编码方式,然后使用该编码方案对k-mer碱基串进行编码,最后得到唯一的Hash值。根据k值的大小,建立相应长度的Hash表,在每个Hash位置下以链表的形式挂接位置信息,从而建立了索引模型。提出一种将四叉树进行编码压缩的索引方案——"线性Hash编码索引模型",消除了四叉树索引模型中父节点内存浪费问题。同时,查询速度从树形的O(log4n)降到了线性的0(1),得到很大地提高。

基于Hash+链表索引的专用型内存数据库系统的设计与实现

文章研究了内存数据库管理系统的原理和关键技术,根据移动短信监控系统中内存数据库的特点,设计和实现了一个基于Hash+链表索引的专用型内存数据库系统,用于解决垃圾短信分析系统中海量短信的存取问题。

二级Hash全局和局部索引筛选的长序列比对并行算法

通过构建参考基因组的二级Hash索引,以快速筛选出测序长序列在参考基因组中可能匹配的候选区域;建立测序序列局部索引,以加速测序序列和参考基因组候选区域之间的映射定位;对每个候选区域里的k-mer与测序序列的索引命中进行左右扩展获得比对种子;采用等距离抽样方式对种子抽取多个位置,利用抽样结果建立判断依据来过滤掉那些不可能匹配的种子;建立处理包含“均聚物”类型错误的序列片段全局比对得分方程,并行填补比对骨架的空隙,并采取GPU显存预分配和后释放独立的并行比对策略,以提升序列片段全局并行比对效率.模拟与真实数据的实验结果表明,相较于已有同类的长序列比对并行算法,本文提出的并行算法获得整体上较高的比对敏感度、碱基层次灵敏度和准确度,且可有效处理第3代测序长序列含有的“均聚物”类型错误,显著加速了大规模长序列与参考基因组比对的完成.

基于稀疏矩阵面向论文索引排名的启发式算法

为了提高学术论文检索的精准性,进而为学术研究提供便利,提出了针对学术论文检索问题的排名策略。首先,介绍了基于网页排名算法面向论文索引排名的启发式方法,其中利用Hash索引技术有效地减少了稀疏矩阵计算对内存的消耗;其次,定义了论文间引用关系图的密集度均衡值,并通过大量实验阐明了不同排名算法的迭代次数与图密集度均衡值之间的关系;最后,将所提出的基于论文索引排名的启发式算法应用于科学引文索引(SCI)数据库中,并与原被引频次降序的排序结果进行比较与分析。实验结果表明:在三种基于网页排名技术的算法中,基于链接结构分析的随机过程算法比较适合于按关键词搜索得到的相关领域学术论文的排名。

数据库索引技术概述

随着数据库技术的发展,数据库索引技术面临着巨大的挑战,为了了解数据库索引技术的发展方向,文章对数据库索引技术的发展现状进行了简要概述。文章从数据库技术的发展出发,阐述了数据库索引技术发展的必然方向,简单说明了传统的数据库索引技术,例如ISAM索引、b＋树、Hash索引,并对可能成第三阶段数据库主流的面向对象数据库的索引技术,例如结构索引、路径索引、多重索引进行了阐述。文章重点对当前大数据时代下,基于大数据的数据库索引技术进行梳理和总结,指出大数据环境中为应对数据容量大、速度快、种类多、价值密度低的4v特点而发展出的索引机制的特点。文章最后对数据库索引的发展方向进行思考讨论,进一步说明数据库索引技术下一步的发展可能方向。

基于Buddy^＊-Hash的移动对象时空查询方法

索引技术可以提高数据检索和查询效率,为了实现对时空数据库中移动对象的查询操作,需要引入时空索引技术。在传统Buddy-树的基础上提出Buddy*-Hash索引结构,根据扩展查询窗口策略给出范围查询算法。实验结果表明,基于BH索引结构的范围查询算法具有良好性能。

基于Hash结构词典的双向最大匹配分词法

针对当前自然语言处理中中文分词基于词典的机械分词方法,正序词典不能作为逆向最大匹配分词词典以及反序词典维护困难的问题,提出一种新的词典构造方法并设计了相应的双向最大匹配算法,同时在算法中加入了互信息歧义处理模块来处理分词中出现的交集型歧义。该算法可以在分词的过程中显著提高分词的精确度,适用于对词语切分精度要求较高的中文语言处理系统。

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构，首先在速度域中对移动对象集进行规则划分，根据速度标量大小将移动对象划分到不同的速度树中，每棵速度树中移动对象具有相近的速度；对每棵速度树中的移动对象，则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构，并基于HR树提出了反向最近邻查询算法，具有很好的动态更新性能和并发性。实验结果与分析表明，基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能，优于通用的TPR树索引。

适应横集纵贯智能电网调控系统实时数据库的设计

为了适应智能电网调度控制系统横向集成、纵向贯通的体系架构,并满足其对实时数据库大容量、高效率、安全性的要求,亟需研发与之适应的实时数据库。文中首先分析了智能电网调度控制系统对实时数据库的需求,然后介绍了实时数据库的体系架构、大容量与支持多应用扩展系列技术、实时库高效访问系列技术、实时库安全保障、模型管理和实时库同步等技术。文中测试表明实时库效率相对原有系统有明显的提升,数据访问安全性能得到有效保障。实时数据库为各类应用打下了坚强的数据基础,保障了各级智能电网调度控制系统的稳定运行,有力支撑了智能电网建设。

一种改进的高效分词词典机制

汉语自动分词是中文信息处理的基础,在中文信息处理系统中具有广泛的应用。作者在研究几种分词词典机制的基础上提出了一种新的分词词典机制,其基本思想是:根据一字词和二字词出现频率高的特点,将词首字和次字组合成Hash索引表,其余字组成剩余结点数组。基于这种分词词典机制设计的组合Hash索引分词算法使得一字词和二字词查询只须在组合hash索引表中一步完成,从而显著提高查询速度。通过真实语料的对比实验,该算法在不降低精度的前提下,处理速度比整词二分平均提高了13.8倍,比TR IE索引树平均提高了2.7倍。结果表明:组合hash索引分词算法是实用有效的。

加密环境下大数据特征集并行存储方法研究

针对传统方法存在数据存储速度慢,容量小的问题,提出一种加密环境下大数据特征集并行存储方法.采用MMSE算法对大数据特征集进行优化处理,以获得并行的大数据特征集.在加密环境下,当内存中保留数据记录达到一定数量时,在并行处理后的数据中插入批量Hash索引.以此为基础,基于Map函数对数据进行映射处理,进而完成对大数据特征集的并行存储.实验结果表明,利用所提方法的存储过程中数据分布通道具有较好的一致性,且存储速度约为传统方法的3倍,存储容量大.

具有服务仲裁机制的内存数据库管理器的研究与设计

介绍了一个具有服务仲裁机制的多线程内存数据库管理器 (CS2 1)的研究与设计 ,重点阐述了 CS2 1中的数据库服务仲裁器 (DSM) .DSM采用指数平均法进行消息执行时间的预测 :如果一个消息预计可以在给定的时限内执行完 ,则该服务请求将被接受 ;否则就被抛弃 ,以提高系统的实时性 .另外 ,还简述了 CS2 1中的内存管理及数据索引技术 .该系统已经在一个移动通信系统中得到了应用 ,实际应用表明 ,DSM对系统负荷进行了有效的控制 。

基于Hash建立索引和Kmp快速匹配算法的DNA序列查找方法

研究了DNA序列片段的查找问题,针对DNA数据量大和DNA序列碱基排列的特点提出了DNA序列检索的问题.在对DNA序列检索中,基于Hash建立了索引表以提高在大数据中检索的速度和效率,同时在平衡树的数据存储模型上使用了改进的Kmp快速匹配算法,提高了在索引上的检索效率.介绍了Hash索引的建立、Kmp的优化以及平衡树的再平衡.利用软件评估实验得出的实验结果表明了该算法的有效性.

面向批量插入优化的并行存储引擎MTPower

针对多核处理器的特点,文章提出了一个符合MySQL接口标准的并行存储引擎MTPower.该存储引擎着重利用多核处理器的并行计算能力提升批量插入过程中的索引产生过程,主要包含存储引擎接口、并行批量线性Hash索引、并行批量B+树插入、支持并行访问的磁盘存储缓冲等部分.测试结果表明,在批量插入记录且需要创建Hash和B+树索引时,MTPower的性能比经典的单线程存储引擎MyISAM最高可以提高6.1倍和4.8倍;在系统中线程总数略大于处理器核数时,MTPower可以达到最佳性能;在处理器核的数量增加时,MTPower的性能也能随之提高.

基于定制协处理器的基因重测序加速技术研究

自2008年1月高通量测序技术应用以来,测序的通量和成本都在不断下降.然而基因数据的爆发式增长速度已经超过了摩尔定律,对海量数据的计算处理能力成为制约基因测序应用推广的瓶颈.以基于Hash索引的重测序算法为目标,对计算和访存行为进行分析,从而提出了一个现场可编程门阵列(field programmable gate array,FPGA)作为协处理器的架构,并在Convey公司的HC-1ex平台上进行了设计与实现.其基本处理单元内部采用全流水的设计及FIFO隔离计算模块和访存模块,可以完整执行重测序算法的核心流程.通过将基本处理单元和访存端口的一对一绑定,在4块Xilinx Virtex-6LX760上实现了64路并行处理流程,总平均读内存带宽可达22.59GBps.与8核Intel Xeon处理器相比,可以提升28.5倍的性能.

一种新的快速报文分类算法——RC-FST

RC FST算法利用IP地址高 8比特前缀建立Hash压缩索引表,将分类规则集分成多个子集,并针对每个子集建立快速搜索树,而这些规模相对小的本地搜索树更利于实现快速建立、查找和优化。为提高搜索树性能,在规则分割等问题上也提出了独到的解决方法,该算法查找速度快 (50Mbps)、支持分类规则数据库大、可扩展性好,适于硬件流水线方式实现,具有很高的实用价值。