道路网络中的连续最近邻查询

为了减少连续最近邻查询中计算K个最近邻的次数和减小算法需要的存储空间,提出一种道路网络中求连续最近邻的方法。给出分点的计算方法及连续最近邻查询算法,对算法的正确性、可终止性进行证明,并分析算法复杂度。与相关算法进行实验比较,得出该算法更适合于对象频繁发生变化的实际网络。     

空间对象的反最近邻查询

本文在对现有反最近邻查询方法研究的基础上,提出了一种新的索引结构一SRdnn-树;在此基础上提出了基于SRdn矿树的反最近邻查询方法,并给出了该结构上的最近邻查询方法,以及插入和删除方法,第5节实验表明,基于SRdnn-树的反最近邻查询在性能上优于以往查询方法。     

空间网络数据库中反k最近邻查询算法

在空间网络数据库中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,因此,基于欧氏空间的反最近邻查询算法不适用于空间网络数据库.本文对空间网络数据库中的反最近邻查询问题进行了研究.给出网络数据和兴趣点的索引结构及空间网络数据存储模型.给出查询空间修剪定理,并在此基础上,提出空间网络数据库中适用于单、双色反七最近邻查询的RkNN算法.证明了该算法的正确性.最后通过实验对算法进行了验证.     

道路网络环境中的多对象最近邻查询

多对象最近邻查询(all nearest neighbors query)在地理信息系统、城市规划和资源分配等领域有着广泛的实际应用,也可作为某些聚类算法或应用的核心模块.针对欧氏空间的查询处理算法不能直接适用于道路网络环境,通过重复调用道路网络环境下的最近邻查询算法来进行多对象最近邻查询处理的计算代价较大,利用M树对道路网络中的边建立索引结构,基于该索引,提出了一个新颖的多对象最近邻查询处理算法BANNS(batched all nearest neighbors search).实验显示BANNS能稳定、快速、准确地处理道路网络中的多对象最近邻查询.     

道路网络中的多类型K最近邻查询

空间数据库的多类型最近邻查询逐渐受到人们的关注,关于K最近邻查询的研究也较多,但多类型K最近邻查询的研究还存在空白。针对道路网络中的多类型K-最近邻（MT-KNN）问题,结合多类型最近邻查询及K最近邻查询的理论,提出了多类型K最近邻查询算法。通过对分层编码视图进行扩展,建立了多路径分层编码视图,并利用逐步扩展局部路径的方法,实现了多类型K最近邻查询,实验结果分析表明算法具有较好的性能。     

路网中线段反k最近邻查询研究

为了弥补现有的研究成果无法有效地处理路网环境下基于线段的反k最近邻问题的不足,提出了在路网环境下线段反k最近邻查询方法。该查询方法主要应用于评估查询对象的影响范围。根据路网及Voronoi图的特点提出了网络线段Voronoi图的概念。在静态数据集情况下利用网络线段Voronoi图的性质提出了STA_RVLRk NN算法,查询包括过滤过程和精炼过程两大部分。进一步,在动态数据集的情况下提出了DYN_RVLRk NN算法,查询分为空间线段对象增加和删除两种情况,并对不同的情况给出了相应的算法,得到查询结果集。理论研究和实验表明,所提算法能有效地处理路网中基于线段的反k最近邻问题。     

GRkNN:空间数据库中组反k最近邻查询

反k最近邻(Reverse k-Nearest-Neighbor,RkNN)查询是在k最近邻(k-Nearest-Neighbor,kNN)查询问题的基础上产生的,获得将查询对象作为kNN的数据对象集合,RkNN可以用于评价查询对象的影响力.根据实际应用中需要查询一组对象的RkNN,如评价连锁店或商业区的影响.文中提出了针对空间数据库的组反k最近邻(Group RkNN,GRkNN)的概念,并设计了相关算法.查询点集合是一组邻近的空间对象,计算查询对象的最小覆盖圆,将最小覆盖圆中的对象作为一个整体进行过滤,设计了基于R树的剪枝方法,通过提炼获取了最终的GRkNN结果.针对真实数据集进行的大量实验表明,提出的GRkNN算法的效率明显优于目前最好的RkNN算法.     

空间数据库中基于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查询效率。     

Reverse Approximate Nearest Neighbor Queries on Road Network

World Wide Web - Reverse k Nearest Neighbor (RkNN) queries retrieve all objects that consider the query as one of their k most influential objects. Given a set of user U, a set of facilities F and...     

路网中速度不确定移动对象的k近邻查询

目前在基于道路网的移动对象的各类查询研究中,大多都是在假定移动对象速度固定不变的基础上进行的.而实际上因为外界环境和自身情况等不确定性因素的影响,对象的速度可能会发生变化.基于此,本文提出一种基于路网的速度不确定的移动对象的k近邻查询处理方法.在查询时刻根据查询点位置执行查询操作,得到构成查询点k近邻的候选对象集合,再根据概率计算方法得到结果集及其概率.实验结果表明本文所提方法是有效的.     

时间依赖路网中反向k近邻查询

在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后, 利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。     

室内双色数据集上的反向最近邻查询

随着Wi-Fi、RFID等室内定位技术的发展,产生了越来越多的基于室内空间的位置服务需求。目前已有文献提出了针对室内环境的范围查询和最近邻查询,而双色反向最近邻（bichromatic reverse nearest neighbor,BRNN）查询作为常见的空间查询类型,在室内空间中尚未有相关的研究。为此,提出了基于兴趣点集合的兴趣点融合图模型,并提出了基于路径、基于楼层和基于单元的3种剪枝策略,用于在查询处理时削减搜索空间。在兴趣点融合图和剪枝策略的基础上,提出了室内双色反向最近邻（indoor bichromatic reverse nearest neighbor, IBRNN）查询算法Smart。Smart算法通过对兴趣点融合图中的图元素的检查,从而判断与该图元素关联的移动对象是否有可能属于结果集。最后通过实验,对所提算法的有效性和高效性进行了验证。     

动态权重路网下的连续近邻查询

现有的近邻查询在查询相同或相近目标时,会得到相同的行驶路线,从而导致大量用户聚集到该区域,造成二次拥堵。针对上述问题,提出一种支配关系监控算法。该算法采用实时交通信息作为动态权重,并给出一个在路网权重变化下的连续k近邻查询方法,有效地避免二次拥堵。实验结果验证了该算法的有效性和高效性。     

障碍环境中可视反向视域K最近邻查询

在障碍环境下的空间应用中,用户通常只对视域范围内可视的数据对象感兴趣。为解决障碍环境中视域范围内的反向最近邻查询问题,将视域可视性引入到反向K最近邻查询中,提出一种可视反向视域K最近邻查询算法。给定某空间数据集P、障碍集O和查询点q,可视反向视域K最近邻查询检索P中数据点,并将q作为可视视域K最近邻。应用查询点进行障碍过滤,得到障碍过滤算法,利用数据对象的视域进行剪枝,使用查询点与数据对象的关系剪枝,形成有效的障碍剪枝规则,并根据剪枝规则得到视域可视性判断算法。在此基础上,分别基于R^*-树和VFR-树提出可视反向视域K最近邻查询算法R^*-V2-RKNN和VFR-V2-RKNN,并分别通过对R^*-树和VFR-树进行一次遍历得到查询结果。在真实数据集和模拟数据集上的实验结果表明,VFR-V2-RKNN算法的查询性能明显优于R^*-V2-RKNN算法。     

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

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