栅格划分的二叉区间树节点构造算法

针对海量数据可视化过程中预处理时间长的问题,提出一种加速构造等值面提取索引结构的栅格构造算法.该算法以二叉区间树的span space划分为基础,利用栅格化方法对二叉区间树节点进行重构,降低了区间排序预处理计算规模,可将预处理效率提高50%左右.理论分析与实验证明,文中算法与传统最优算法有相近的活动单元搜索效率,能够大大缩短整个海量数据可视化过程,对实时性要求较高的可视化应用具有实际应用价值.     

使用R树进行k-NN搜索

在地理信息系统中经常要做k-NN搜索，进行这些查询用到的算法与位置和范围查询的算法不同，需要专门进行研究，介绍了一种分支界限遍历R树算法，并将该算法概括为k-NN算法。文中讨论了两种方法。对R树进行结点内MBR的排序以及剪枝过程，以减少搜索空间中需访问结点的数量，有效地进行k-NN搜索。     

基于多维区间检索的云网络对等索引模式

在云网风起云涌发展的今天,众多用户在云对等网中进行频繁的多维区间检索,把m叉平衡树这一索引模式放进云对等网中,在此模式中进行集中的多维数据检索的多层树型结构,比如QR及R树之类.多维的区间检索算法能确保检索从树任何结点进行,防止根结点产生系统类的限制问题.经过多次验证,针对M结点网,多维区间检索效率可达到O(logm N)(m＞2).     

改进的赫夫曼树（Huffman Tree）和赫夫曼编码（Huffman Code）构造算法

通过将待排序的数据应用快速排序算法进行排序处理,使得赫夫曼算法（Huffman Algorithm）65时间复杂度从O（n^2）降低为O（n＊log2n）。当用于构造赫夫曼树（Huffman Tree）的结点比较多时,可较大的提高程序的运行时间。     

基于二叉划分树的多尺度图像分割算法

图像分割作为从图像中提取感兴趣对象的必要步骤,通常需要其能够提供多尺度的分割结果.提出一种基于二叉划分树(BPT)的多尺度图像分割算法,用于系统地记录从图像的任意过分割结果上进行的区域合并过程;然后基于BPT中每个结点与其父亲结点的差异度量,提出一种包括自动确定候选结点和分裂合并策略的结点选择算法,来选出符合期望分割区域数目的结点,并生成相应尺度的分割结果.实验结果表明,文中算法能够在较粗分割尺度下获得更适合于对象提取的分割结果,有助于提高自动对象提取的效率以及减少交互式对象提取中的人工交互.     

基于有效路径权重的XML树匹配算法

针对当前XML文档信息查询算法的不足,提出一种基于有效路径权重的树匹配算法。在保持XML文档树有效结点和树结构的基础上,树根结点信息最重要,随着树深度增加,结点信息重要性逐渐减弱的特点,按照路径层次自动计算路径权重,并赋予相应路径,根据树结点的有效信息和树结构的有效路径计算树的匹配度。在大规模XML文档查询方面,实验验证了该算法在保证较高查准率和查全率的基础上,有效提高了查询效率。     

基于B+树存储的AABB包围盒碰撞检测算法

对于碰撞检测算法,使用传统的AABB包围盒来构建包围盒层次树时,其包围盒层次树的层数、叶子结点的个数和各结点的存储字节数是影响碰撞检测效率的主要因素.为了减少结点存储容量对碰撞检测效率的影响,提高碰撞检测的效率,文中采取B+树的存储结构来存储包围盒等信息.在包围盒相交测试之前,使得各结点存储索引有序,不需要再对各结点进行额外的排序,减少了内存开销,并且避免了不必要的包围盒测试.此外B+树的非叶子结点不存储具体的数据信息,从而减少了整棵树的存储空间.实验表明,在检测环境和检测对象相同的条件下,使用B+树存储的AABB包围盒碰撞检测算法的检测时间明显比传统的AABB算法短.     

几何数据压缩的一种新算法

本文提出一种几何数据压缩的新算法,其基本思想是在已知物体网格边界的条件下,首先寻找边界的凹点,然后建立网格结点的特殊树结构,即横切面树,并将横切面树中相邻节点内网格结点之间的关系表示为链表（三角形条带）,按契约数结构及链表（三角形条带）编码、存储帮传输网格结点的连接关系,这种算法不同于Gabriel Taubin算法,它具有对顶点坐标、属性坐标及三角形连接关系压缩无损等许多优点。     

一种新的删除HB(k)树的结点的算法

Foster的删除HB(k)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除HB(k)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB(k)树的结点的算法相比,新算法不涉及辅助栈的使用。设n是HB(k)树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的删除HB(k)树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的删除HB(k)树的结点的算法短。新算法的空间复杂性是O(1),比Foster的删除HB(k)树的结点的算法低。     

自根向下压缩的二叉排序证书吊销树方案

在二叉排序证书吊销树的基础上，利用了树中的叶子结点的空链域，在已有的树结构中毋需增加结点，就可建立一种新的线性表结构。树中结点信息采用“自根向下”压缩方法，将整个树的信息汇集到叶结点中，可信中心签名线性表最后一个结点。在该CRT方案中，树结点发生变化后，毋需重新建立树，降低了维护代价，减少了名录服务器至查询者的通信代价。     

二叉排序树查找算法性能分析

查找是计算机中经常要用到的操作。二叉排序树排序树查找属于动态查找类,二叉排序树查找算法与建立算法密切相关。给出了一种计算二叉排序树平均查找长度的算法,希望能对查找算法的研究起到一点作用。     

严格平衡二叉排序树类属类

对严格平衡二叉排序树的查找时间复杂度进行了详细分析,给出了平均查找长度的计算公式及其渐进性态的误差估计。基于C＋＋语言的模板,提出了严格平衡二叉排序树类属类的总体设计方案及主要成员函数的详细设计。最后提出了有关严格平衡二叉排序树平均查找长度近似计算的绝对误差的一个猜想,以及有关广义严格平衡二叉排序树的一种构想。     

基于衰减窗口与剪枝维度树的实时数据流聚类*

提出一种基于衰减窗口的实时数据流聚类算法PDStream。算法首先对数据空间进行网格划分,采用改进的维度树结构维护和更新数据流的摘要信息,设计了一种周期性剪枝策略,周期性地剪去维度树中的稀疏网格,最后采用深度优先搜索算法在线处理聚类请求。基于人工数据集和真实数据集的实验表明,PDStream算法可以有效地发现数据流中任意形状的聚类,内存消耗少,具有较好的计算精度。     

基于等值线的海区网格插值算法研究

为了将人类长期海洋观测所获取的矢量等值线数据与遥感反演等所获取的栅格数据进行比对运算,存在由等值线到海区网格的插值需求.以海洋表层水温矢量等值线为例,运用具有层次嵌套关系的三级分辨率海区网格,对等值线进行了离散化,通过建立离散点与海区网格之间的空问索引关系,并运用顾及方向的单点移面平均加权法,进行了海区网格点插值运算过程的研究.     

基于三角网的等值线填充算法研究

通过对现有等值线填充算法的深入研究,提出了一种覆盖填充等值线的算法。该算法把等值线分类为凸包边封闭等值线(CHCL)和自封闭等值线(SCL),充分利用等值线的特点,使对等值线拓扑关系及填充颜色的判定达到最简化。对于CHCL采用对凸包边等值点及凸包点追踪来确定填充区域,对于SCL则根据拓扑关系以最外层的SCL为根节点构建一棵多叉树以确定填充顺序.通过对等值区域依次反复覆盖填充,最终完成所有等值线的填充。采用了一种穿过原始离散点平滑等值线的算法,减小了等值线平滑造成的精度损失。并运用客户端语言AS3.0(ActionScript3.0)实现了算法模型。实验结果表明,该算法简单易于实现,而且运算速度能满足业务需要。     

B+树索引机制的研究及优化

B+树索引是大型数据库系统中较为常用的一种索引技术。当数据庞杂时,B+树索引在查找效率和空间利用率方面还存在不足。针对该问题提出一种改进的B+树结构,首先通过调整叶子结点与非叶子结点的数量关系,以降低树的深度;然后优化原插入算法,在分裂结点前进行平衡处理(BP),以提高树的空间利用率。经试验,改进后的B+树与传统B+树相比,在查找效率和空间利用率上分别提高了10%和6%,证明对B+树的改进具有可行性。     

一种支持多维区间查询的云对等网络索引架构*

针对用户在大规模云对等网络环境下多维区间查询问题,将基于m叉平衡树的索引架构引入到云对等网络环境下,在该架构上实现集中式环境下支持多维数据索引的层次化树结构,例如R树,QR树等。多维区间查询算法保证查询从树的任意位置开始,避免了根节点引起的系统性能瓶颈问题。通过计算和实验验证,对于N个节点的网络,多维区间查询效率为O(logmN)(m>2)(m表示扇出),由此可见,查询效率和维数d无关,查询效率不会随着维数d的增加而降低。最后建立基于扇出m的代价模型,并且计算出了最优的m值。     

Grid k-d tree approach for point location in polyhedral data sets – application to explicit MPC

ABSTRACT

Explicit model predictive control (EMPC) moves the online computational burden of linear model predictive control (MPC) to offline computation by using multi-parametric programming which produces control laws defined over a set of polyhedral regions in the state space. The online computation of EMPC is to find the corresponding control law according to a given state, this is called the point location problem. This paper deals with efficient point location in larger polyhedral data sets. The authors propose a hybrid data structure, grid k-d tree (GKDT), which is constructed by the k-dimensional tree (k-d tree), hash table and binary search tree (BST). The main part of GKDT is a multiple branch tree which constructs subtrees by splitting the polyhedral region into several equal grids based on the k-d tree and is traversed by the hash function on each level. GKDT has a high search efficiency, even though it needs much more storage memory. A complexity analysis of the approach in the runtime and storage requirements is provided. Advantages of the method are supported by two examples in the paper.     

基于关键词权重的XML查询结果排序方法

XML关键字查询结果质量不高的一个很重要的原因是查询关键词难以反映用户真实的查询意图,而给关键词设置权重在一定程度上可以解决这一难题. 本文结合关键字之间的结构关系提出了一种新的结果排序方法,该方法给查询关键词设置权重,并参照查询关键词的权重给包含关键字的结点设定结点权重,然后根据关系树中的结点权重和关键词之间结构关系^[1]统计SLCA结点的重要程度,再以此依据对查询结果进行排序,最后返回给用户有序的查询结果. 实验结果和分析表明,提出的排序方法具有较高的准确率,能够较好地满足用户查询的需求和偏好.     

The reliability of general vague fault-tree analysis on weapon systems fault diagnosis

An algorithm of vague fault-tree analysis is proposed in this paper to calculate fault interval of system components from integrating expert's knowledge and experience in terms of providing the possibility of failure of bottom events. We also modify Tanaka et al's definition and extend the new usage on vague fault-tree analysis in terms of finding most important basic system component for managerial decision-making. In numerical verification, the fault of automatic gun is presented as a numerical example. For advanced experiment, a fault tree for the reactor protective system is adopted as simulation example and we compare the results with other methods. This paper also develops vague fault tree decision support systems (VFTDSS) to generate fault-tree, fault-tree nodes, then directly compute the vague fault-tree interval, traditional reliability, and vague reliability interval.