k-gram方法识别microRNA前体

MicroRNAs(miRNAs)是动植物中较短的参与调控基因表达的功能性非编码RNA序列.第一个miRNA是通过实验手段发现的,然而通过实验手段识别miRNA在技术上仍然具有很大的挑战性和不完整性.因此,miRNA基因识别需要寻求计算方法来弥补实验方法的不足.提出了一个全新的miRNA前体的识别方法.在构造识别模型中,把初级序列和序列二级结构相结合,采用k-gram方法把序列信息映射到高维特征空间中,然后通过特征选取方法提取特征,并用这些特征为miRNA前体的识别构造了基于SVM的识别模型.同时,采用隐马尔可夫模型(HMM)的学习方法进行了比较.实验结果表明,该方法是有效的,可以达到较高的敏感性和特异性.

一种大数据流内存B+树构建方法

面向具有时间维度的大数据流,基于二级B+树索引结构,提出了一种高效的面向时间窗口、采用批量装载技术的内存B+树构建方法。该方法对时间窗口进行分片,通过分离出可以并行处理的操作来加速构建过程,将排序操作与数据流接收并行,B+树骨架的构建与排序并行;采用基于排序的批量装载技术以及优化的构建顺序,能够避免多线程之间不必要的加锁、同步开销,有效提高构建效率。提出的多次微批量排序单次批量装载(MBSortSBLoad)B+树构建方法的构建速度快,能承载的最大流速大。实验验证了所提方法的有效性。

组合盘节能缓存替换机制

利用组合盘(由固态盘和硬盘构成)进行节能是近年来的一个研究热点.对基于文件粒度的组合盘节能缓存机制开展了研究,利用能量代价模型改编FBR,提出了基于频率和能量的替换算法FEBR;同时,基于滑动窗口机制提出了考虑硬盘寿命的自适应磁盘电源管理机制;为探索现有缓存算法在新硬件结构上的适用性,对过去提出的一系列缓存替换算法在能效、性能、硬盘寿命影响等方面进行了较为全面的比较和评价.通过对收集的4个真实用例数据进行一系列比较实验,得到了如下结论:组合盘节能是可行的,可达70%～80%节能效果;联机替换算法FEBR,FBR以及GDS在所有评价的算法中具有总体最优效果,FEBR略优于FBR和GDS,能耗代价模型可以用于指导算法;所提自适应磁盘管理机制能够较好控制硬盘寿命.

整机系统实时功率剖析与建模

功率剖析与建模是功率感知DBMS的基础。将主要硬件(处理器与磁盘)的利用率作为系统功率的指示器,根据资源利用率实时地估计系统功率,构建整机系统的实时功率模型。在多核架构下,整体CPU的活动信息会掩盖单个核的使用情况,因此,从执行核粒度考察执行频率与利用率的综合影响,采用多元线性回归方法拟合执行核的执行频率和利用率、磁盘的利用率和系统功率之间的关系。实验结果显示,所构模型平均相对误差小于12%,且占用系统资源较少,从而不会影响其他应用程序的执行,具有较好的应用价值。

面向时空数据流的移动对象空间索引构建

本文针对时空数据流提出了一种基于时间窗口数据排序和批量装载的移动对象空间索引构建方法HSTRCL.该方法用固定长度的时间窗口将连续的时空数据流进行切分,每当一个时间窗口完成数据缓存,采用优化的索引批量装载技术,从传统的构建流程中尽可能分离出耗时的数据划分和排序操作,将数据流的接收及其他构建操作并行执行,避免不必要的加锁同步开销,加快索引的构建效率;同时,采用基于Hash和STR的主、辅索引构建技术,满足高性能且多样化的查询需求.另外,为进一步提高对象查询性能,引入聚合技术划分对象,提出了一种基于时间窗口对象聚合和批量装载的移动对象空间索引构建方法OAHSTRCL,对象查询时间约为HSTRCL的65%,但对空间查询性能会有一定程度的影响.通过理论分析和多种实验验证了所提方法的有效性.

面向大数据流的分布式索引构建

大数据流的高效存储与索引是当今数据领域的一大难点.面向带有时间属性的数据流,根据其时间属性,将数据流划分为连续的时间窗口,提出了基于双层B+树的分布式索引结构WB-Index.下层B+树索引基于窗口内流数据构建,索引构建过程结合基于排序的批量构建技术,进一步对时间窗口分片,将数据流接收、分片数据排序以及B+树构建并行化,提高了构建性能.上层B+树索引基于各时间窗口构建,结合时间窗口时间戳的递增性和无限性,提出了避免节点分裂的构建方法,减少了B+树分裂移动开销,提高了空间利用率和更新效率.WB-Index架构中,将流数据和索引分离,同时利用内存缓存尽可能多的双层B+索引和热点数据来提高查询性能.理论和实验结果表明,该分布式索引架构能够支持高效的实时数据流写入以及流数据查询,能够很好地应用于具有时间属性的数据流场景.

一种利用固态盘特性的散列连接改进算法

随着新一代存储设备固态盘的发展,如何发挥新存储设施的性能成为近年来的一个研究热点.将固态盘作为"黑盒",通过观察固态盘I/O外部特性,即考察访问粒度与访问队列深度与固态盘性能之间的关系,得出算法设计应遵循的原则,并应用到数据库散列连接算法的设计中.提出了并行化Grace散列连接设计方法,以及根据访问粒度、队列深度计算各阶段缓冲区大小的优化分配方法.一系列实验结果表明本文提出的并行散列连接方法能够充分发挥固态盘性能,优化的缓存分配方案可保证固态盘性能充分发挥而不浪费内存资源.

XPSort——树形数据多核并行外存排序算法

XML数据处理中一个基本问题是树形数据排序.本文针对已有算法的不足提出了一种XML文档多核并行外存排序算法——XPSort.XPSort扫描XML文档产生相互独立的排序任务,利用多核CPU对任务进行并行处理;同时,利用数据压缩、单临时文件以及避免子树匹配等策略,有效地减少磁盘I/O,提高排序性能;它克服了NEXSORT算法没能有效利用内存空间、存在大量随机I/O的问题以及难以处理"右深树"的缺陷,也克服了HERMES的数据冗余、大量磁盘开销等缺点.文章对不同特性的XML文档开展了大量比较实验,结果表明XPSort优于已有算法,所提优化方法是有效可行的.

运动腕表心率序列相似性检测

近年来学生整体的体质状况呈现下降的趋势。许多高校实行了阳光晨跑计划,但不尽理想。采用运动心率腕表采集运动心率数据来监控学生课外健身跑状况是较好的方案,由于缺少直接监督,可能会出现一人佩戴多个腕表替他人代跑的情形,这将成为该方案实施的一个技术挑战。对所有时间上重叠的心率序列对抽取距离相关和统计相关的特征,通过基于支持向量机的代跑检测方案,可实现精准并且召回较高的代跑检测。实验验证了所提方法的有效性。

组合盘GRACE散列连接算法

在传统数据库系统中,I/O开销一直是连接算法性能瓶颈.固态盘具有随机读写性能高和低延迟的特性,使得利用固态盘改善连接算法I/O性能成为可能.提出基于硬盘和固态盘混合存储系统下的组合盘GRACE散列连接算法(CGHJ).CGHJ对传统GRACE散列连接算法分区阶段作如下改进:将固态盘作为内存和硬盘之间的缓存,位于内存的各个散列桶先写到位于固态盘的临时文件缓存;临时文件缓存满后,利用迁移缓存将固态盘中的内容转移到位于硬盘的各个分区文件.新的分区方式增大了分区过程中随机写到每个分区文件的块,减少硬盘分区过程中产生的随机I/O.实验结果显示在缓存容量较小或表的数据规模较大情况下,CGHJ能取得很好消除硬盘随机I/O的效果.

一种改进的整机系统实时功率建模方法

本文通过考察处理器、内存和磁盘三个部件的活动信息,包括硬件性能事件和部件利用率,构建整机系统实时功率模型.对于处理器和内存的功耗,通过特征选择找到合适的处理器内部的性能事件,结合CPU功耗状态C-States,建立低误差的功耗模型;对于没有提供性能事件的磁盘,通过利用率对部件功耗进行估算.采用回归方法分别建立并综合两个模型即可得到整机的实时功率模型.实验使用了真实系统Eureqa建模和PosgreSQL系统运行TPC-H负载对两种功率模型进行验证,结果表明:基于硬件性能事件与C-States的实时处理器与内存功率模型的误差在3%以下;结合性能事件、C-States与利用率的整机功率模型其相对误差在4%~10%之间,优于仅使用利用率的整机功率模型,最大时提升可达7%.

散列连接算法中探测缓存与峰值功率关系建模

功率感知数据库管理系统是数据库界具有挑战性的研究议题,针对数据库系统中核心操作之一—散列连接的峰值功率估计问题开展研究.依据CPU功率与CPU利用率正相关以及CPU利用率与内存可用数据之间的关联关系,以及散列连接算法其峰值功率发生在连接阶段的事实,从理论上分析了CPU利用率与散列连接算法中可用探测缓存大小之间的关系,通过功率计对运行散列连接算法的机器功率消耗实际测量获得数据,并进行了以探测缓存大小为自变量的峰值功率预测模型构建.通过一系列实验对本文所提建模方法进行了有效性验证,所提模型相对误差在6%以内,具有一定的可用性.

数据库服务器系统中一种有效的功率封顶机制

数据中心的一个重要任务是功率控制,功率封顶是数据中心对服务器设置功率消耗上限的技术。关注的是数据中心节点机一级的动态功率控制机制。基于系统级功率模型构建了进程级功率模型,并将两者整合构成"软功率计",用于监控系统功率与进程功率;为实现功率封顶,软功率计被集成到闭环控制系统中,设计了功率控制的算法,该算法在控制系统功率不超预算的情况下,系统以较好的性能运行。实验结果表明所提控制机制能有效地控制系统的实时功率,且性能下降较少,同时也可以改善能效,可应用于功率感知的DBMS服务器中。

数据库服务器系统软功率计

功率建模是功率感知DBMS的基础.针对数据库服务器系统整机系统进行功率建模,构建其软功率计.模型利用处理器、磁盘(包括硬盘和固态盘)和内存等主要部件的活动信息,包括其利用率与核频率,其余部件产生功率作为背景功率,来构建模型.为提高模型的准确性,对各部件、可用参数对模型准确性进行全面分析.实验表明不同的模型准确性、鲁棒性存在一定的差异,大部分模型的相对误差在5%~8%之间,个别没有利用足够信息的模型相对误差在12%左右,利用全部信息的模型具有较好准确性和稳定性.

异构多固态盘的吞吐量优化

固态盘具有低访问延迟、抗震性、内部并行性等诸多优良特性,已被广泛使用。如何利用固态盘提高系统性能是当前研究议题之一。首先通过一系列不同读写比例的负载实验来探索固态盘的特性,发现在较大I/O请求粒度场景下,较高的读请求比例有利于提升各类固态盘的吞吐量。基于实验结论,提出了一种I/O只读负载分离方法 RODI,通过合理放置只读数据来分离只读负载到合适的固态盘上,以提升异构多盘阵列整体的吞吐量。大量实验表明,在较大I/O粒度的异构多盘环境中,相比传统的RAID技术,RODI方法对于改善多盘总体吞吐量更具优势。

一种统一的可扩展语言UXL及其应用

本文提出一种统一的可扩展语言UXL,它可用于描述Web上数据源、用户查询需求、各种服务、控制流以及事件等。利用UXL可实现对网上数据源和服务的统一描述,从而为各种服务器做一件外观统一的“主动服务外套”,构成所谓的“主动虚拟服务器。此外,还可利用UXL来描述查询计划,实现分布式协同工作和计算,构造可供网上使用的、动态的、可伸缩的分布式协同环境等。

异步I/O连接算法的峰值功率建模

峰值功率是影响数据中心能效的一个重要因素.本文提出一种功率感知数据库系统中连接算法的峰值功率估算方法,非运行时峰值功率的估算的挑战在于没有运行时的系统信息作为模型的输入.为克服估算困难,提出使用 CPU密集度作为 CPU功耗指示量,理论上分析了异步 I/O连接算法在峰值功率发生阶段的特性,通过模拟连接算法峰值功率发生阶段算法行为来估算该阶段最大 CPU密集度,通过 CPU密集度与 CPU功率的内在联系建立异步I/O连接算法的峰值功率预测模型.实验对数据库系统中采用异步 I/O机制的四个连接算法时模型准确性进行了验证,结果表明所提预测方法具有较好的预测准确性,平均相对误差低于 7%.

异步连接操作的峰值功率建模

功率感知数据库系统的峰值功率研究是解决数据中心能效的重要议题.非运行时峰值功率的估算的挑战在于没有运行时的系统信息作为模型的输入.为克服估算困难,提出了使用CPU密集度作为CPU功耗指示量,理论上分析了异步I/O连接算法在峰值功率发生阶段的特性,通过模拟连接算法峰值功率发生阶段算法行为来估算该阶段最大CPU密集度,根据CPU密集度与CPU功率的内在联系建立异步I/O连接算法的峰值功率预测模型.实验表明:所提预测方法具有较好的预测准确性,平均相对误差低于4%.

主动虚拟服务器和网上数据集成的新模式

针对Internet上信息搜索和数据集成存在的问题 ,提出了“主动虚拟服务器”的概念 ,并给出了基于这种虚拟服务器的数据集成模式。主动虚拟服务器可认为是网上海量数据统一的存储和处理器 ,而且具有主动服务的功能。在不改变服务器中原DBMS的前提下 ,只需用一种统一的可扩展语言UXL为各种服务器做一件外观统一的“主动服务外套” ,就可构成所需的“主动虚拟服务器”。上述“外套”对每种服务器只需实现一次 ,就能在整个网上统一使用 ,因此 。

基于k-度匿名的社会网络隐私保护方法

针对当前社会网络的匿名化隐私保护方法存在信息损失量巨大、网络关系结构被改变严重等问题,提出一种保持网络结构稳定的k-度匿名隐私保护模型Similar Graph,运用动态规划方法对社会网络按照节点度序列进行最优簇划分,然后采用移动边操作方式重构网络图以实现图的k-度匿名化.区别于传统的数值扰乱或图修改如随机增加、删除节点或边等方法,该模型的优势在于既不增加网络边数和节点数,也不破坏网络原有连通性和关系结构.实验结果表明,Similar Graph匿名化方法不仅能有效提高网络抵御度属性攻击的能力,并且还能保持网络结构稳定,同时具有较理想的信息损失代价.