RFN-B+树索引文件及其有效性

在对比传统的B树和B⁺树的定义和操作算法的基础上,定义了一种新的B⁺树:RFN-B⁺树,以获得更高的空间利用率和可用性.首先比较和分析了RFN-B⁺树与传统B⁺树的空间效率,然后讨论了RFN-B⁺树索引文件的有效性以及支持这种有效性的全链接指针结构和两个备用模块:基于虚拟根结点的随机检索算法和重构结点的算法.     

约束数据库中的索引

本文研究了约束数据库中的索引技术，提出了存储区间常数刺穿集的数据结构S树和S^*树．在刺穿集的最大长度受到限制的条件下，S^*树存储效率是最优的．与M树相比，S树和S^*树有一个明显的改进：可以支持删除操作．     

变长字段在关系数据库中的实现

关系数据模型具有操作方便等许多优点，然而关系数据模型是一个框架理论，对于关系中每个字段都必须 给定长度，即每个字段是定长的，这种限制给许多应用领域带来不便。． 本文对关系数据库系统中的数据结构进行了分析，对索引方法进行了修改。对于变长字段采用保序散列技术进 行索引，而不是常用的B树索引方法，使得变长字段能在关系数据库系统中实现。     

基于分布式内存数据库的移动对象全时态索引

针对现有移动索引仅对内存/磁盘两层结构进行优化,忽略了索引节点在内存中的缓存敏感性,提出一种基于分布式内存数据库的全时态索引结构DFTB^x树。该索引结构针对存储器Cache、内存和磁盘3层结构进行优化,根据Cache行、指令数量和TLB失配数等多个条件设计内存索引节点的大小。同时,根据磁盘数据页的大小设计历史数据迁移链节点的大小,使得Cache和内存能够一次读取索引节点和迁移链节点数据,避免多次读取数据带来的延迟。此外,构建历史数据迁移链,实现历史数据持久化,从而支持移动对象全时态索引。实验结果表明:与B^x树、B^dual树、TPR*树和STRIPES算法相比,DFTB^x树具有较高的查询和更新效率。     

基于B+树的多关键字密文排序检索方法

针对当前社会信息量大、隐私信息需要加密存储带来的检索难度大等问题,研究分析了现有的基于密文的可搜索加密方案,提出了一种基于B⁺树的多关键字密文排序方法。利用向量模型构建索引和查询陷门,根据相关性分数和关键字匹配度对检索结果进行排序。在真实数据集上进行了实验,结果证明本方案具有较高的检索效率。     

图象处理中边界转换的并行算法及其实现

本文提出了一种把图象中边界转换成区域四分树的并行方法.该方法基于MIMD模型,并在曙光1000上实际运行.整个算法用P个处理器可以在时间O((B×logB)/P)内完成其中B是循环代码长度.该算法可应用于图象处理、计算机图形学、模式识别等领域.     

基于并行B+-树的并行Join算法的设计、分析与实现

Ｂ＾＋－树是一种有效的数据库存储结构，被普遍应用于各种关系数据库系统。把Ｂ＾＋－树并行化，使之用于并行数据库系统显然是一项很有意义的重要工作。本文研究了适用于并行数据库的并行Ｂ＾＋－树存储结构，提出两类基于并行Ｂ＾＋－树工并行Ｊｏｉｎ算法。理论和实验结果表明，这些算法效率高基其它并行Ｊｏｉｎ算法。     

B^＋树它引文件结构的优化设计

指出当普通Ｂ＾＋树的数据块设计为定长时,数据块长度的选择具有一个最优的选取设计过程。给出了在两种数据库系统模型中,对Ｂ＾＋树索引文件结构的优化设计：⑴在具有限量内存在数据库系统ＤＢＳＬＡＭ（Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ｌｉｍｉｔｅｓｄ Ａｍｏｕｎｔ ｏｆ Ｍａｉｎ Ｍｅｍｏｒｙ）模型中,只有缓存Ｂ＾＋树中的部分结点;⑵具有极大数量内存在的数据库系统ＤＢＳＶＬＡＭ（Ｄａｔａｂａｓｅ     

一种新的细分曲线方法研究

对经典的四点细分格式进行推广，提出了可通过对形状参数的适当选择来实现对极限曲线形状调整和控制的三参数四点细分曲线造型方法，并对其收敛性进行了分析，同时给出了曲线C⁰到C³连续的克分条件，并加以证明．     

多维索引hB树的改进方法——hB*树

本文在hB树基础上提出多属性索引方法——hB^*树.hB*树索引结点溢出时先寻求避免分裂,以期得到较好的空间利用率;通过避免和消除多父结点,使hB^*树成为严格的树形结构.本文表明hB^*树提高了空间利用率,树形化的代价也不高.     

基于DS-Adaboost算法的人脸检测

针对连续Adaboost算法中平滑因子选取的不足,提出了一种动态选取平滑因子的DS-Adaboost算法,该算法对弱分类器输出中的平滑因子ε进行了动态选取,根据W^j₊₁W^j－1比值的大小动态地选择平滑因子,当W^j₊₁W^j－1>1时,ε_j=W^j₊₁,当0j₊₁W^j－1<1时,ε_j=W^j－1。实验表明,DS-Adaboost算法能较好地起到平滑的作用,使得落在同一个区间里面的正样本和负样本的比例都在可以比拟的范围内。     

QBF问题中隐蔽集的求解过程

隐蔽集作为QBF问题的重要结构之一,能使QBF这一难求解问题变得更加简单. QBF问题中隐蔽集的求解相当复杂且难以理解. 为了使读者更好的理解QBF问题中隐蔽集的求解过程,本文对QBF问题中隐蔽集的求解过程进行深入研究,结合实例计算变量的深度、选择符合条件的变量X并计算其对应的三角依赖变量集D_ψ^Δ（x）,根据B=B∪{x}=x和ψ''=ψ-D_ψ^Δ（x）的思想求解出问题的隐蔽集,希望本文能为该领域的相关研究人员提供一定的参考.     

关于p－m度的分裂

本文讨论多项式时间多一可化归度（ｐ－ｍ度）的分裂间题．主要结果是：存在非零的ｐ－ｍ度ａ，对任何自然数ｎ≥１当ａ分裂成ｎ＋１个度ａ₀，ａ₁，…，ａ_n的并时，其中至少有ｎ对（ａ_i，ａ_j）（ｉ≠ｊ；ｉ，ｊ≤ｎ）不是极小对．从而推广了Ａｍｂｏｓ－Ｓｐｉｅｓ中关于存在非零ｐ—ｍ度ａ不能分裂成一个极小对的结果．     

单向Hash函数的一种构造方法*

单向Hash函数已成为密码学的一个重要组成部分．给定任一定长单向Hash函数f：∑^m→∑^t,m>t，本文给出了利用f构造一单向Hash函数F的一种新方法，该方法易于并行化．     

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

不同通信模型下的全光树环网波长分配算法

研究了波分复用全光树环网在不同通信模型下的波长分配算法及其最坏性能分析.对于静态模型,证明了5L/2是树环网所需波长数的紧界.对于动态模型,提出了一种近似比为∑_i=1^hmax_r∈Ri[log|V(r)|]+h的波长分配算法,其中h为树环网的基树的层数,R_i为树环网中处于第i层的环的集合,|V(r)|为环r上的节点数.对于增量模型,提出了一种近似度为O[log₂(t+1)]的波长分配算法,其中t为树环网中的环数.     

基于差别信息树的rough set 属性约简算法

差别矩阵为粗糙集属性约简提供了很好的思路, 但差别矩阵中存在冗余的重复和父集元素. 为了消除这些冗余元素, 提出一棵有序树: 差别信息树, 该树能消除差别矩阵中的重复元素, 同时在大多数情况下也能完全消除父集元素, 实现对差别矩阵中非空元素的压缩存储. 为了验证差别信息树的有效性, 提出一种属性约简完备算法, 并使该算法的时间复杂度降为??(∣??∣∣??∣²).

     

Grzegorczyk分层的一种延伸

本文讨论某些递归函数类的分层问题．首先给出的是原始的Ｇｏｒｚｅｇｏｒｃｚｙｋ分层的一种较为简单的等价定义．然后，作为对Ａｃｋｅｒｍａｎｎ函数的一种推广，定义了一个递归函数序列｛Ａ_ｎ｝_ｎ∈ω．并以此作为分层函数列定义了一种新的递归分层｛Ｚ_ｎ｝_ｎ∈ω（即Ｚ—分层），这种分层涉及了比原始递归函数类更大的一个违归函数类．实际上，原始递归函数类仅是Ｚ—分层的第一层Ｚ_０．而且这种分层的任意的第ｎ＋１层都含     

确定任意多边形凸凹顶点的算法

本文提出一种确定任意多边形凸凹顶点的算法．该算法的时间复杂性为O(n²logn)次乘法和O(n²)次比较．     

一类有限域上的置换多项式

有限域上的置换多项式在科学工程中的多个领域有着广泛的应用,尤其应用于现代通讯、密码学等领域中。基于Zha等人在文献[23]中提出,当t为偶数时,有限域Fpⁿ上形如(xp^k－x+δ)^t+γx+βTr(x)的多项式是置换的,通过进一步研究,运用证明置换多项式的一般方法,将其改进为无论t为奇数或偶数,(xp^k+1－x^p+δ)^t+γx+βTr(x)形式的多项式在Fpⁿ上均是置换的。