基于四维聚类的R^＊-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出一种新的R*-树结点分裂算法,该算法以R*-树结点最小边界矩形外接球半径为权值,对点、三角形、矩形等多种三维几何对象进行加权处理,将其统一表示为四维点对象,选定距离最远的两个四维点作为初始分簇中心,根据点到两分簇中心的距离进行分簇,结合k-means算法以结点外接球半径为权值计算新的分簇中心,并迭代分簇过程,直到各分簇中心不再变化,结束R*-树的结点分裂过程。试验证明,采用该结点分裂算法可处理复杂数据对象的分簇,并在提高建树效率的同时,优化R*-树结构,提高空间查询效率,对提高逆向工程数据预处理效率具有重要意义。

R＊-树结点自适应聚类分簇算法

为提高逆向工程中点云、三角网格等数据的索引效率,提出一种R*-树结点自适应聚类分簇算法,采用均匀分布数据作为参考点集,基于间隙统计法及k-均值算法获得使结点相似度之和开始收敛的自然簇数,进而实现R*-树的结点自适应聚类分簇.实验证明,该算法可实现各类复杂几何对象的R*-树结点分簇问题,并能降低R*-树结点分簇的参数依赖性,减少结点重合度,提高R*-树空间数据查询效率.

R*-树空间索引的优化研究

针对大型空间数据库应用的需求及己有空间索引技术的不足,在论述R-树及R*-树索引技术的相关概念、数据结构、算法描述及性能分析的基础上,提出了一种改进的R*-树空间索引结构。研究结果表明:改进后的R*-树与原始的R*-树相比具有更高的性能。

基于最小生成树的R^＊-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.

基于SR-树的空间对象反最近邻查询技术研究

反最近邻查询是空间数据库的重要应用之一,是在最近邻查询基础上提出的一种新的查询类型,以往基于范围查询或最近邻查询的方法搜索影响集效率不高,本文在分析RNN查询的基本概念和存储区域的基础上,区别于R*-树,提出了基于SR-树的RNN查询方法,优化了空间对象的反最近查询性能,在高维空间查询上具有明显优势。

基于R^＊-tree的散乱点云截面数据获取算法

为快速准确地获取散乱点云的截面数据,以较少数据准确表达模型信息,提出一种截面数据获取算法.采用R*-tree建立点云的动态空间索引结构,基于该结构快速准确获取截面邻域数据,依据该数据与截平面的位置关系将邻域数据分为正负两个邻域,通过对两邻域数据点配对连线与截平面求交获取截面数据,并采用最小生成树算法对其排序,最终得到有序的截面数据.结果表明,该算法数据适应性强,截面数据获取精度高,运行速度快,且能够以较少数据准确表达模型型面特征.

R^＊-树空间索引的改进

R*-树基于局部调整的思想对节点进行管理,存在时间与效率上的不足。为克服R*-树的不足,给出了一种新型的存储结构,并给出新型存储结构的插入、溢出、分裂等空间索引常用操作的算法。分析新的存储结构的优点,并通过实验结果说明该方案比R*-树具有更高的效率。

树的[r,s,t]-着色

通过用树T的导出星K1,Δ(T)的一个[r,s,t]-着色对树T进行点、边着色,证明了树的[r,s,t]-色数等于树中最大导出星的[r,s,t]-色数.

树的D(r)-点可区别边染色

图G的一个正常边染色是指对G的每条边分配一种颜色使得任意相邻的两条边的颜色不同.图G的正常边染色f称为D(r)-点可区别边染色,如果对G中任意两个距离不超过r的顶点u,v∈V(G),有C’(u)≠C’(v),其中C’(x)={f(xy):xy∈E(G)}.图G的D(r)-点可区别边色数是指对图G进行D(r)-点可区别边染色所需要的最小色数,记为χ’_r(G)文章讨论了树的D(2)-点可区别边染色及D(3)-点可区别边染色问题通过逐层染色的方法,得到了树的D(2)和D(3)-点可区别边色数的上界,并给出了线性时间的染色算法.另外通过边染色与全染色的关系,得到了树T的D(3)-点可区别全色数不超过Δ(T)+3,D(2)-点可区别全色数不超过Δ(T)+2.

一种基于PSR*-树索引结构的研究

目前查询效果很好的R*树,但R*-树结点分裂算法复杂度比较高,极大影响了R-树的整体检索性能。针对其缺陷,本文提出了一个更为合理的PS约束条件,进一步改善了结点分裂的合理性。PSR*—树在确保查询性能的前提下,大幅度提高了索引结构的空间利用率,而且极大降低了构造代价和空间开销代价。

面向多维对象的RC-反k近邻查询新方法

分析现有反k近邻(reverse k nearest neighbor,RkNN)查询在效率、数据维度等方面的不足,提出基于R树结点覆盖值(R-tree’s cover-value)的RC-反k近邻查询方法.该方法需预先计算R树每个结点的覆盖值,采用过滤-精炼两步式处理方法,在过滤阶段采用两种剪枝启发式.该方法可有效处理数据库更新,适用于任意k值、任意维的对象集,查询结果精确,且计算量较小.实验结果表明,在k>6时RC-反k近邻查询时间比同类工作更短.

一个新的激活策略在偏k-树上的应用

笔者使用一个新的激活策略证明了 ,如果G是一个偏k -树 ,其色数为r=k + 1 ,缺陷度d≥ 2k + 1 ,那么 ,对这个 (r,d) -松弛竞赛染色 ,Alice有一个赢的策略。这个结果可以写为 ( 2k+ 1 ) - χg(G)≤k+ 1 ,它是文献

黄浆水中高产γ-氨基丁酸乳酸菌的筛选及鉴定

经初筛、复筛,从黄浆水中筛得一株高产γ-氨基丁酸(γ-aminobutyric acid,GABA)的菌株,对其进行形态学及生理生化鉴定,并与Gen Bank上已提交的16S r DNA进行BLAST比对,结果表明,其归属于乳酸杆菌属(Lactobacillus)。由MEGA 6.0软件构建的系统发育树结果表明,该菌株与Lactobacillus plantarum 16S r DNA序列同源性达99%,且与生理生化实验结果一致,因此,确定该菌株为植物乳杆菌(Lactobacillus plantarum),编号为LP-Dfa301,测得其发酵液中GABA产量为5.833 g/L。

一种QaR树的图像粒优化分解方法

首先提出图像粒的概念,然后将所提出的概念应用于QaR树进行图像分解,最后对基于QaR树分解的结果和其他算法进行评估和对比。实验结果表明,在冗余度和精度两个指标上,基于QaR树的图像粒分解结果均优于已有方法,能够提供更为贴近图像数据和图像空间的图像局部区域。

三角网格模型的自动分割算法

提出了一种根据设计意图的三角网格模型自动分割算法,该算法采用R*-tree(recangle*-tree)建立三角网格空间索引结构.基于该结构,采用深度优先遍历方法快速准确地查询与分割面相交的三角面片,对相交三角面片进行分割并重新剖分,实现了三角网格模型不受曲率等条件限制的自动分割.实例表明:该算法可对各种复杂型面三角网格进行分割,算法运行效率高,且能有效避免分割区域的锯齿现象.

三角网格细分曲面数控加工刀轨快速生成算法

提出了一种基于三角网格细分曲面模型的刀轨生成算法,建立三角网格细分曲面模型的空间聚类索引结构,基于该结构实现网格模型与刀轨截面快速、精确求交获取刀触点集,并根据刀触点对应曲面位置处的微分几何性质确定刀位点,采用最小生成树算法对刀位点集排序生成刀轨。实例证明,该算法可有效提高复杂曲面模型的刀轨生成效率及精度。

基于全息熵的空间离群点挖掘算法研究

基于距离和基于密度的离群点检测算法受到维度和数据量伸缩性的挑战,而空间数据的自相关性和异质性决定了以属性相互独立和分类属性的基于信息理论的离群点检测算法也难以适应空间离群点检测,因此提出了基于全息熵的混合属性空间离群点检测算法。算法利用区域标志属性进行区域划分,在区域内利用空间关系确定空间邻域,并用R*-树进行检索。在此基础上提出了基于全息熵的空间离群度的度量方法和空间离群点挖掘算法,有效解决了混合属性的离群度的度量和离群点的挖掘问题。由于实现区域划分有利于并行计算,从而可适应大数据量的计算。理论和实验证明,所提算法在计算效率和实验结果的可解释性方面均具有优势。

一种基于个人位置信息的重要地点识别方法

基于位置的服务(LBS)正在从被动服务向主动服务的方向发展.因此,地点识别已成为LBS领域一个重要的研究方向.为提高现有地点识别方法的效率和准确性,本文提出了一种新的地点识别方法.一方面算法在数据预处理阶段采用了速度剪枝、时间剪枝和空间剪枝相结合的VSTPruning算法,能够有效减少后续阶段的聚类处理时间,提高聚类精度.另一方面,在数据预处理的基础上,综合R*-树空间索引机制、密度相交以及DBSCAN聚类算法,提出了基于密度的RTcluster聚类算法,更为迅速挖掘出用户的重要地点.仿真结果显示,相比于已有方法,VSTPruning和RTcluster的相互配合可以在有效保证聚类结果的前提下,花费与DBSCAN算法相比更少的时间,得到更准确的结果.

散乱点云自适应滤波算法

提出一种散乱点云自适应滤波算法,该算法采用改进的R*-树组织散乱点云的拓扑近邻关系,基于该结构快速准确获取局部型面参考数据,自适应调节二维高斯分布的数字特征计算滤波权值,计算局部型面参考数据对原始型面数据的影响因子,以此作为权值计算各点滤波后的坐标,采用加权平均方法实现散乱点云的自适应滤波.实验证明该算法可有效提高点云的滤波效率,在保留原始型面特征的基础上,减小点云的随机误差,提高光顺性。

一种新的空间数据索引方法

针对传统的R-树节点交叠面积大的问题,提出了一种新的空间数据索引结构——R0-树.主要思想是在内部树结点存储外部对象,如果将这样的对象存储在树的更高层,则低层结点的最小边界矩形MBR的面积更小,因此索引的性能更好.研究结果表明,此方法能可提高空间利用率,减少I/O访问次数,使索引性能得到大幅提升.