NUMA架构下数据热度的内存数据库日志恢复技术

在内存数据库故障恢复技术中,命令日志是针对内存数据库设计的粗粒度的、轻量级的日志记录方式。但在非统一内存访问(non-uniform memory access,NUMA)体系架构下面向数据的数据库设计中利用命令日志进行故障恢复时,由于数据访问频率不均衡,导致负责高频数据恢复的CPU线程负载加重,而其他CPU相对空闲。针对这种工作负载不均衡所导致的恢复时间开销增大的情况,提出了NUMA体系架构下基于热度记录的内存数据库日志恢复算法。该算法中,每一条数据的访问次数作为该数据的热度记录下来。在并行恢复时,根据数据热度,将数据比较均衡地划分到各个节点的CPU线程执行恢复操作,以此来提高数据库的恢复速度。实验结果表明,该方案比NUMA架构下的常规恢复方案快,而且数据的热度越高,恢复速度的提升越明显,最高提升了19%。     

Super-Peer网络中基于语义的分簇算法研究

在P2P网络中,利用共享数据的语义信息,将网络划分成不同的语义簇是提高网络查找性能、增强网络可扩展性的有效手段.然而现有的基于分类层次的语义分簇方法较少考虑簇之间的负载平衡问题,这必然会影响网络的性能.为此本文提出了两种针对分类层次语义空间的自组织语义分簇算法,即语义优先分簇算法SFCA和负载平衡优先分簇算法LBFCA,这两种算法能够根据网络的负载动态的将网络划分成不同的语义簇,并很好的保持了簇中数据的语义关系和簇之间的负载平衡.实验表明这两种分簇算法具有良好的性能和可扩展性.     

TBSN:一种基于分类层次的P2P网络

构建语义覆盖网络是支持基于语义的搜索、提高P2P网络查找性能和可扩展性的重要手段.现有的基于分类层次的P2P语义覆盖网络并不能充分利用分类层次所包含的语义信息,为此提出了一种基于分类层次的P2P网络(TBSN),该网络充分考虑遵循某种分类层次的数据源的特点,能够利用分类层次所包含的语义信息,动态地将peer节点聚簇成不同的语义簇,语义簇之间根据语义关系建立相应的语义路由,从而形成了一种基于语义的P2P网络.每个语义簇由一个super-peer节点和多个peer节点组成,仅负责回答其语义子空间上的查询.查询根据语义首先被路由到可能有结果的语义簇中,然后转发给相关的peer节点,从而减少查询所涉及的节点和消息的数量,提高了网络的性能.实验表明,TBSN网络在查找性能和开销之间取得了良好的平衡,同时较好地保持了语义簇之间的负载平衡和簇中数据之间的语义关系.     

时序图中Top-k稠密子图查询算法研究

稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用.目前,关于稠密子图查询的研究工作主要基于静态图.而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图.因此,如何高效地在时序图上查找稠密子图仍然是一个挑战.为了解决上述挑战,首先规范化地定义了基于时序图的稠密子图查找问题;然后,根据图的拓扑结构和包含时间标签的边之间的相似度,提出一种基于阈值的近似查找算法DTS-base.为了加快算法的收敛速度,提出了一个基于快速计算最大相似度时间片的优化算法DTS-opt.最后,通过在真实数据集上的实验,证明了所提算法的高效性和可扩展性.     

基于分片的XML快速结构连接算法

结构连接作为XML查询的重要部分,对查询性能来说起着非常重要的作用.目前有几种结构连接算法已经被提出,例如Stack-Tree、XR-tree.这些算法主要集中在节点之间关系的确定上.与之不同,作者从分片的角度去解决结构连接问题,首先把节点间的关系引申到分片之间的关系,从而得出各分片之间的一些性质,再利用分片间的性质来提高结构连接操作的性能.文中提出了一种基于分片的结构连接算法和两种优化方法,实验表明该算法在性能上要优于Stack-Tree算法和XR-tree算法.设计了一个简单而又高效的索引结构来存储分片结果,实验结果表明该索引结构的维护代价要小于XR-tree的维护代价.     

决策树的并行训练策略

随着生物科学技术的发展，其数据量的增长也非常迅速，很难在一定合理的时间内对数据进行建模和分析。因此，对并行数据挖掘算法的研究巳变成解决此问题的重要途径。决策树途径巳被广泛用作一种重要的分类工具，本文研究了几种决策树的并行训练策略并对它们的性能进行了比较。     

Xen虚拟机资源调度优化算法

针对Xen虚拟化平台中虚拟机资源分配不合理的问题,提出了两种资源调度优化算法,即细粒度优化算法和粗粒度优化算法.细粒度优化算法主要解决单个物理节点上虚拟机资源分配不合理问题,能够根据物理节点上运行的各虚拟机的资源利用情况来调整资源分配量,适当增加利用率较高的虚拟机的资源,减少资源利用率低的虚拟机的资源,从而优化资源分配,提高资源利用效率,避免不必要的虚拟机迁移.粗粒度优化算法是针对集群中多个物理节点之间虚拟机负载不均衡问题而提出的.该算法结合粒子群优化技术,选择将集群系统中热点物理机上的部分虚拟机迁移到最适合的冷点物理机上,从而避免高载物理机宕机.实验结果表明,这两种资源调度优化算法能够有效解决虚拟机资源分配不合理的问题,具有较好的适用性和应用前景.     

TH-Ring: 一种基于语义的结构化P2P网络

构建基于语义的P2P网络是支持基于语义的查找和提高网络性能的重要手段.考虑遵循某种分类层次的数据源的特点,提出了一种基于分类层次语义空间的P2P网络(TH-Ring),并给出具体实现算法. TH-Ring根据广度优先遍历算法对分类层次语义空间进行编码,为新加入的Peer提供PeerID的高32位.数据项根据所属分类加入到环中,同一个分类的数据项存储在环上连续的Peer上,这些Peer的PeerID高32位相同,低32位不同. Peer根据数据负载分布动态地加入或离开环. Peer之间根据PeerID的高32位建立路由关系,从而形成了一个基于语义的P2P网络.实验表明,TH-Ring具有良好的可用性和扩展性,而且数据项插入后的负载平衡维护代价相对很小.     

基于最大间隙空间映射的高维数据索引技术

在基于高维索引技术的相似性查询处理中,通常通过过滤那些不包含任何查询结果的非活动子空间来不断缩减搜索空间.但是在活动子空间中,有些可能根本就不包含任何查询结果,这样的活动子空间被称为假活动子空间.显然,查询处理性能会随着假活动子空间访问次数的增加而下降.这一问题在高维数据情况下将会变得更加严重,实验显示出随着维数的增加,假活动子空间的访问次数也会增加.为了解决这一问题,提出了一种空间映射方法来减少这种不必要的访问.对于一个给定的查询,可以通过在映射空间内进一步精炼该查询来过滤假活动子空间.为了提高映射空间内查询精炼的处理效率,提出了一个最大间隙空间映射策略--MaxGapMapping.基于这种映射方法,设计并实现了一种新的索引结构--MS-tree,给出了索引的构建算法和范围查询处理算法.最后对MS-tree及其他索引结构的性能进行了详细的比较和分析.