连续近邻查询方法的研究

连续近邻查询(CNN)要检索一给定查询线段上每一点的近邻。它是时空数据库中一种重要的查询类型,在智能交通系统中有着广泛的应用。Voronoi图解决连续近邻查询问题,思想简单明晰,但Voronoi图构造代价太高,尤其是高阶的Voronoi图。本文从文献得到启示:用分枝限界的思想去界定预创建Voronoi图生成点范围的上限。提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。这种方法只是在给定查询段上所有点的k个近邻范围上限内创建一个局部的k阶Voronoi图,这样会大大降低基于Voronoi图的连续k近邻查询的代价。     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

数据集中单纯型连续近邻链查询方法

为解决数据集中的单纯型连续近邻链查询问题,提出一种基于Voronoi图的查询方法。给出单纯型连续近邻链查询的定义,利用Voronoi图的性质对大量数据点进行精减,设计可准确查询出数据集中单纯型连续近邻链的查询算法。实验结果表明,随着待查连续近邻链所含数据点规模的增大,该方法的效率比传统基于R树方法更高。     

关于k(1≤k＜n)阶Voronoi图生成算法的研究

k( 1≤k 相似文献   

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

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

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

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

Voronoi图的生成及近邻关系查询方法

针对构建Voronoi图的方法的生成效率较低,构建复杂度较高的问题,提出了利用多方法交叉融合进行Voronoi图的构建与更新的方法。为了提高空间数据最近邻查询的效率,提出了基于Voronoi图和Voronoi多边形最小内切圆的最近邻查询方法;针对查询点位置频繁变化的情况,提出了基于Voronoi图和Voronoi多边形最小外接矩形的最近邻查询方法;为了提高对偶近邻对和最近对的查询效率,利用Voronoi多边形和对应的最小内切圆进行过滤和查询,提出了统一查询对偶近邻对和最近对的新方法。实验结果表明,所提方法解决了因数据分布不均导致的额外计算量的开销问题,在数据集规模较大和查询频率较高时具有一定的优势。     

空间数据库中基于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图的特性提高了查询的准确性。理论研究和实验表明,所提方法的效率明显优于可选的已有方法。     

移动点Voronoi图拓扑维护策略的研究

移动环境下基于Voronoi图的最近邻查询必须要解决随时间不断改变的移动点Voronoi图的拓扑结构的维护问题。通过一组离散的,有限的事件序列对其对偶图Delaunay图拓扑改变过程的模拟来实现对移动点Voronoi图拓扑结构的维护。把带有事件驱动机制的移动数据结构（Kinetic Data Structure,KDS）模型作为移动点的运动模型,给出了KDS模型对其对偶图Delaunay图拓扑结构改变维护的具体策略,并对移动环境下动态插入或删除移动点时Voronoi图的拓扑维护问题进行了研究。最后给出了移动环境下基于Voronoi图的近邻查询的数据库实现模型。     

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

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

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

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

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

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

K-nearest neighbor finding using MaxNearestDist

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These algorithms are generally applicable to any index based on hierarchical clustering. The idea is that the data is partitioned into clusters which are aggregated to form other clusters, with the total aggregation being represented as a tree. These algorithms have traditionally used a lower bound corresponding to the minimum distance at which a nearest neighbor can be found (termed MinDist) to prune the search process by avoiding the processing of some of the clusters as well as individual objects when they can be shown to be farther from the query object q than all of the current k nearest neighbors of q. An alternative pruning technique that uses an upper bound corresponding to the maximum possible distance at which a nearest neighbor is guaranteed to be found (termed MaxNearestDist) is described. The MaxNearestDist upper bound is adapted to enable its use for finding the k nearest neighbors instead of just the nearest neighbor (i.e., k=1) as in its previous uses. Both the depth-first and best-first k-nearest neighbor algorithms are modified to use MaxNearestDist, which is shown to enhance both algorithms by overcoming their shortcomings. In particular, for the depth-first algorithm, the number of clusters in the search hierarchy that must be examined is not increased thereby potentially lowering its execution time, while for the best-first algorithm, the number of clusters in the search hierarchy that must be retained in the priority queue used to control the ordering of processing of the clusters is also not increased, thereby potentially lowering its storage requirements.     

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

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

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

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

不确定数据上范围受限的最近邻查询算法

不确定数据的查询处理是数据库领域近年来的热点研究课题.提出一种不确定数据上的范围受限的最近邻查询.给定不确定数据集D={o1,o2,…,on},范围约束R是一个简单多边形,q为一固定的查询点,范围受限的最近邻查询返回的是在数据集D中,既满足范围约束R,又能成为查询点q的最近邻的对象集合.为处理该查询,提出了范围受限的最近邻核心集的概念和范围受限的最近邻核心集的查找算法.并提出一种计算范围受限的最近邻候选集的优化方法,降低了查询代价.最后通过实验验证了该算法的有效性.     

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

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