基于平面线段的反向最近邻查询

反向最近邻查询是空间数据库空间查询的研究热点。目前反向最近邻查询的查询粒度都是基于一维的点,在一些空间物体不能抽象为点的情况下将其抽象为点进行反向最近邻查询,查询结果不能达到一定的精度。该文在分析基于平面线段的最近邻查询和R树结构的基础上提出了一种改进的R树—Rcd树,并给出了基于Rcd树的平面线段反向最近邻查询算法,该方法能实现平面线段的反向最近邻查询。     

基于Voronoi图的线段反向最近邻查询

提出一种基于平面线段的反向最近邻查询方法,用于找出线段集中以查询线段作为最近邻的线段。通过构造线段集的Voronoi图处理不相交的线段。根据其邻接特性和局部特性,给出基于Voronoi图的线段反向最近邻查询算法及相关定理和证明。实验结果表明,反向最近邻方法易于找到相交的线段,具有较高的查询效率。     

基于Delaunay图的反向最近邻查询

将查询点作为Delaunay图的一个生成点,利用Delaunay图的生成点与其邻接生成点之间的关系,在查询点的邻接生成点集(元素个数小于等于6)中计算数据集中给定点的反向最近邻。把伴随Delaunay图增量生成过程产生的Delaunay树作为查询索引结构,该结构能存储Delaunay图,在数据点插入和删除时维护Delaunay图的拓扑结构。     

空间数据库平面线段快速最近邻查询算法

给出了线段按其MBR进行排序的定义.以提高线段数据库最近邻查询效率为目标,以此为基础提出了一种线段数据的索引结构——SI-树,规定SI-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行最近邻查询时可以进行快速定位.给出了新的最近邻查询剪枝规则.利用这些规则在进行相应的查询时减少了许多不必要的计算,对节点有效地进行筛选和过滤,加快了查询的速度.实验表明：给出的最近邻查询算法与现有的同类查询算法相比查询效率有较大的提高.     

不确定性对象的反向最近邻查询

多数不确定性对象的反向近邻查询不能明确回答某个不确定性对象是否为查询对象的反向最近邻,针对该问题,提出概率反向最近邻查询的概念,设计不确定性对象的概率反向最近邻查询的索引结构,给出一种基于该结构的不确定性对象的反向最近邻查询算法。     

基于VAR树的反向最近邻查询技术的研究

在空间数据库中,反向最近邻查询技术是最重要的查询技术之一,它是在最近邻查询技术的基础上提出的,如何有效地实现反向最近邻查询一直是人们研究的热点.以往都是基于类似R树索引结构的查询,在高维的情况下,使查询的速度急剧下降,形成"维数灾难".因此引用了一种新的索引结构--VAR树,并对VAR树进行了改进,引进了性能优越的SR树,并给出了基于这种索引结构的最近邻和反最近邻查询的算法.经实验验证基于VAR树的反向最近邻查询算法,在高维空间中的查询效率有了较大的提高.     

基于Voronoi图的反向最近邻查询

为了解决反向最近邻查询问题,利用Voronoi图及数据集中点的凸包进行反向最近邻查询,通过判断查询点与凸包的位置关系,可去除大量的数据点,并且给出在数据点被加入或删除后,对查询点的反向最近邻变化情况的判断方法与算法。为了便于查询,设计相应的空间存储数据结构。比较分析表明,该方法在处理多个查询点的反向最近邻时有一定的优势。     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

移动对象的动态反向最近邻查询技术

为了处理移动对象的动态反向最近邻,对时空动态反向最近邻查询问题进行形式化的定义,利用时空距离函数及限界区域等概念给出计算移动对象的动态反向最近邻的定理与算法,提出移动查询点的动态最近邻的全域查询及局域查询的方法,利用动态检测圆及时空距离函数进行动态反向最近邻的查询判断,其计算量可减少40%~60%。构建新的时空索引结构——TPRDNN树,给出操作TPRDNN树的查询算法。     

平面线段集最近邻查询算法

针对基于R-树的空间索引结构存在的节点覆盖冗余,兄弟节点之间的交叠问题,提出一种新的空间索引结构即RP-树。通过最适合划分函数和数据矩形的有序关系来对空间数据进行划分,使得该树的高度尽可能低,节点交叠较小。以RP-树为平面线段集的索引结构,利用线段集的相关定理和筛选规则,给出了一个求解平线段集最近邻的新查询算法,该算法不仅易于理解,且执行效率较高。     

空间数据库平面线段近邻查询问题研究

空间数据库的近邻查询近几年受到人们越来越多的关注.近邻查询根据程度不同可分为点与点的近邻查询、点与线段、线段与线段的近邻查询.目前,前两者研究的较多,后者没有查到相关文献.提出平面线段与线段的近邻查询问题.有针对性地解决一些空间物体无法抽象为点的情况.平面线段的近邻查询在现实中有着广泛的应用价值.根据平面线段与线段是否相交分为两类;不相交的平面线段再根据位置关系分成9种情况.分别对上述各种情况进行讨论研究.给出了线段近邻查询的筛选规则、定理和查询算法,进行了实验分析和比较,新方法实现了平面线段与线段的近邻查询,具有较高的查询效率.     

基于新型索引结构的反最近邻查询

为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的4种序的定义.依据这些定义,提出了一种新的空间数据索引结构——基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor, MBDNN-tree),该索引结构运用了R-树中分割空间数据的思想,将数据点用其基于最近邻距离的最小包围正方形表示,记为MBSD(minimum bounding square based on nearest neighbor distance),利用多种序关系对原始点集进行划分,从上至下、从左至右地按照结点几何分布以及对应的序关系构造树的各层结点.对建立MBDNN-树所需要的预处理过程以及构造过程的算法进行了详细描述和证明分析,给出了MBDNN-树的性质.在此基础上,给出了MBDNN-树进行反最近邻查询的剪枝规则,进而给出了MBDNN-树进行反最近邻查询的算法及其算法分析.反最近邻查询算法利用了MBDNN-树中同层结点之间的几何有序性,有效地减少了结点的访问数量,从而提高了查询效率.最后对基于此结构的反最近邻查询算法进行实验分析.实验表明：基于MBDNN-树的反最近邻查询算法的查询性能有较大的提高.     

路网中基于Voronoi图的反向最近邻查询方法

针对已有的在路网中的反向最近邻(Reverse Nearest Neighbor,RNN)查询方法存在的不足,提出了利用网络Voronoi图(Network Voronoi Diagram,NVD)的NVD-RNN算法,该算法具有较好的效果,它把路网划分成小的Voronoi区域,并且采用了两个过程:过滤过程和精炼过程。过滤过程主要是提前存储可能的查询结果。精炼过程主要是从可能的结果集合中找到查询结果。并且进一步给出了处理新增加点的ADDNVD-RNN算法和处理删除点的DENVD-RNN算法。实验表明,该算法在处理路网中的反向最近邻问题时有明显的优势。     

路网中互近邻查询处理方法

提出路网中的互近邻查询问题.给定路网G(V,E),对象集P,查询点q,近邻数k1和k2,互近邻查询返回既是q的k1近邻,又是q的反k2近邻的对象集.为解决该问题,首先提出基础算法,即先求出查询点q的k1近邻作为候选,再验证这些候选是否为真正的结果.然后,在此基础上提出了优化算法,根据落在对象点与查询点最短路径边上的标记点个数直接排除掉一些错误的候选对象.最后,通过实验验证了优化算法的有效性.     

障碍环境中线段组最近邻查询方法研究

为了解决现有成果无法有效处理障碍环境下的线段组最近邻查询问题,提出了障碍环境中线段组最近邻查询方法。查询过程分为过滤阶段和精炼阶段两个部分。在过滤过程中,首先根据线段Voronoi图的性质以及线段障碍组最近邻查询的定义,提出了针对数据线段的剪枝定理,并提出了OLGNN_Line_Filter算法;根据线段障碍距离的定义,进一步提出针对障碍物的剪枝定理,并给出了OLGNN_Obstacle_Filter算法。在精炼过程中,为了得到更精确的查询结果,提出了相应的精炼定理和精炼算法STA_OLGNN。理论研究和实验表明,所提算法能够有效地处理障碍环境下的线段组最近邻查询问题。     

障碍空间中基于Voronoi图的组反k最近邻查询研究

为了解决已有研究成果无法有效处理障碍空间中的组反k最近邻查询问题,提出了障碍物环境中基于Voronoi图的OGRkNN查询方法,该方法获得的结果集是将一组查询点中任意一点作为障碍kNN的数据点集合,在实际应用中可以用来评估一组查询对象的影响力.依据障碍物集合是否发生变化提出了2种情况下的OGRkNN查询方法,一种是静态障碍物环境下的OGRkNN查询(简称STA_OGRkNN查询)方法,另一种是动态障碍物环境下的OGRkNN查询(简称DYN_OGRkNN查询)方法.其中STA_OGRkNN查询方法利用Voronoi图的邻接特性可以在剪枝阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,提高整个算法的查询效率,在精炼阶段有效地提高了算法的准确性.进一步给出了3种情况下的DYN_OGRkNN查询方法,分别为障碍物动态增加情况下的OGRkNN查询算法、障碍物动态减少情况下的OGRkNN查询算法以及障碍物动态移动情况下的OGRkNN查询算法.理论研究和实验结果表明所提算法具有较高效率.