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

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

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

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

基于Voronoi图的最近邻查询的研究

移动查询点的最近邻查询是移动计算和现实生活应用中一种很基本也很重要的查询类型.基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间.但在以往的研究中基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及.本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树.进而给出了基于VR树索引结构的1NN查询算法.     

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

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

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

为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。     

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

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

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

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

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

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

基于Voronoi图及其对偶图的反最近邻查询

最近邻查询是地理信息系统领域经常遇到的问题,而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上,提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询,大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。     

空间数据库中基于Voronoi图的组反k最近邻查询

为了改进现有的组反k最近邻查询算法的查询速度与准确度,提出了一种基于Voronoi图的组反k最近邻查询方法(group reverse k nearest neighbor guery method based on Voronoi diagram,V_GRk NN)。该方法获得的结果集是将这组查询点中任意一点作为kN N的数据点集合,在实际应用中可以用来评估一组查询对象的影响力。该方法的特点是首先对查询点集Q进行优化处理,降低查询点数量对查询效率的负面影响;接着对数据点集P进行约减,缩小查询搜索范围;然后根据基于Voronoi图的剪枝策略对候选集进行过滤;最后经过精炼获得GRk NN查询的结果集。该方法在数据集处理阶段很大程度上提高了查询速度,在过滤、精炼阶段利用Voronoi图的特性提高了查询的准确性。理论研究和实验表明,所提方法的效率明显优于可选的已有方法。     

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

为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的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-树的反最近邻查询算法的查询性能有较大的提高.     

一种用于连续反最近邻查询的空间削减算法

动态环境中的反最近邻查询已成为空间查询的研究热点,有效的数据空间削减策略是此类查询的瓶颈。本文首先给出了连续反最近邻CRNN查询的定义,并且深入分析了问题的特点;其次,在综合分析已有削减策略的基础上给出了可用于CRNN查询的空间削减算法。该算法能在降低I/O操作的同时保证结果的精确性,并且不依赖于特定的索引结构和查询算算法。实验表明,该算法能够有效削减掉不包含RNN的结点,能够提高CRNN查询效率。     

一种基于移动对象的动态反向最近邻的算法

随着无线通讯技术的发展,移动对象的查询有广阔的应用空间.针对现有反向最近邻算法很多都是基于静态对象的情况,提出了一种新的基于移动对象的反向最近邻的算法--以TPR-tree为索引结构,对原有的半平面修剪策略进行了改进,使其性能优化,并采用过滤验证这两个处理步骤来获取移动查询点的反向最近邻,实现了移动对象的动态反向最近邻的查询.     

Voronoi图的构建与受限区域内的最近邻查询方法研究

Voronoi图在空间数据查询、数据挖掘、图像处理、模式识别和智能交通管理等方面具有重要的作用。为了简化构建的复杂性和提高构建效率,基于分治法、启发式局部优化策略和局部数据点的扫描线动态更新策略,提出了基于凸包的Voronoi图生成方法,给出了Create_Voronoi()算法。进一步,为了弥补已有近邻查询方法无法处理受限区域内的最近邻查询的不足,基于Voronoi图研究了受限区域内的同质和异质最近邻查询方法,分别提出了TVor_NN()算法和YVor_NN()算法。理论研究和实验分析表明,提出的研究方法在Voronoi图的构建和受限范围的最近邻查询等方面具有较大的优势。