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

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

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

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

空间数据库平面曲线的点最近邻查询

基于线段最近邻查询,提出平面曲线的点最近邻查询(LPNN)概念,设计LPNN查询算法。通过R树索引空间对象,采用过滤和精炼两步法提高检索速度。过滤阶段利用平面曲线直接影响区域和筛选规则得到候选对象集,精炼阶段使用优先队列,避免相同点的重复计算,得到平面曲线的点最近邻查询结果。实验结果表明,该算法具有较好的查询性能。     

基于Voronoi图的线段最近对查询

最近对查询是空间数据库中的重要查询之一。已有的关于最近对查询的研究基本集中在点对象上,对空间对象无法抽象为点的对象则研究较少。提出基于平面线段的最近对查询,即找出两个平面线段集中距离最近的线段对。提出基于Voronoi图的线段最近对查询算法,该方法构造两个线段集的Voronoi图,利用Voronoi图的最近邻近特性和局域动态特性找到互为最近邻的线段对,从中找到结果,以缩减大量的计算代价。对线段集中增加线段和删除线段的情况做了相应的处理。实验证明,该算法具有较高的查询效率。     

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

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

空间相似查询中MBR边界区域关系研究

相似查询是基于向量空间的一种重要查询方法。点、线段、区域是向量空间对空间对象的三种基本表达。本文在不改变结点MBR区域前提下,通过区域扫描对MBR区域重叠面积进行计算。利用R*树结点MBR允许重叠的特性,在不能消除区域重叠产生的死空间情况下,研究了更为精确的MBR边界的线段关系,并给出线段的最近邻查询算法和相似线段选取算法。实验结果表明该方法的CPU计算代价较低且显著提高了相似查询与更新的效率。     

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

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

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

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

移动对象的动态反向k最近邻研究

反向最近邻查询是空间数据库中最重要的算法之一。传统的反向最近邻查询方法主要是针对静态对象的查询,随着无线通讯和定位技术的快速发展,移动对象发出的查询请求成为新的研究热点。该文将TPR-tree作为算法的索引结构,并提出了基于矩形框的对角线的修剪策略,将半平面修剪策略进行改进,给出了移动对象的动态反向k最近邻的查询方案。     

基于SR-树的空间对象最近邻查询

最近邻查询是空间数据库的重要应用之一,最近邻查询概念的扩展,即时象的相似性查询中,利用以往的定位查询以厦范围查询方法不能很好的解决最近邻查询的问题,在分析NN查询的基本概念和存储区域的基础上,提出区别于以往NN查询的基于SR-树的多时象NN查询方法,根据某几个查询点,找出离它们最近的一个点或者是七个点,在某种意义上是寻求一种最优方案。     

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

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

空间对象的反最近邻查询处理技术研究

空间数据库中反最近邻查询的研究是空间查询的研究热点。在对现有的反最近邻查询技术进行分析比较的基础上,针对提高动态数据集的查询效率问题,给出了基于R树索引结构的反最近邻查询方案。通过实验结果的分析比较,可以看出该方案能够有效地解决动态数据集的查询问题。     

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

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

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

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

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

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

基于抗体选择策略的克隆挖掘算法

针对如何有效地利用大量的原始数据分析现状来预测未来的问题,基于抗体选择策略提出一种克隆选择挖掘算法。通过评估抗体的支持度、可信度和亲和度,求得有效的关联规则。实验结果表明,该算法能较快地获得可理解的规则,并且具有较高的准确率。     

Ranked Reverse Nearest Neighbor Search

Given a set of data points P and a query point q in a multidimensional space, reverse nearest neighbor (RNN) query finds data points in P whose nearest neighbors are q. Reverse k-nearest neighbor (RkNN) query (where k ges 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have influence to all those answer data points. The degree of q's influence on a data point p (isin P) is denoted by kappap where q is the kappap-th NN of p. We introduce a new variant of RNN query, namely, ranked reverse nearest neighbor (RRNN) query, that retrieves t data points most influenced by q, i.e., the t data points having the smallest kappa's with respect to q. To answer this RRNN query efficiently, we propose two novel algorithms, kappa-counting and kappa-browsing that are applicable to both monochromatic and bichromatic scenarios and are able to deliver results progressively. Through an extensive performance evaluation, we validate that the two proposed RRNN algorithms are superior to solutions derived from algorithms designed for RkNN query.     

Rav-tree:一种有效支持反向近似近邻查询的索引结构

空间数据库的索引结构是实现有效数据查询的前提和基础。空间数据反向近似近邻查询是空间查询的一个新方向,它避免了精确查询中过多的距离计算,从而能够在效率与准确性上取得平衡。提出的Rav-tree不同于基于启发式规则的索引结构,首先利用局部近似,然后根据Voronoi cell区域和估计圆的方法实现近似近邻查询,并利用过滤结果和分域查询得到初步的候选集,最终通过反向近似近邻查询(RANNQuery)算法得到RANN集,并完整地给出基于Rav-tree的ANN查询算法和RANN查询算法。实验结果表明,Rav-tree对RANN等查询具有较好的查询效率和查全率。     

球面上的最近邻查询方法研究

球面上的最近邻查询在空间数据库最近邻查询领域具有重要的意义。为了处理球面上的最近邻查询问题,针对球面上数据对象点的特征和近邻查询的需要,给出了处理球面上最近邻查询的3种方法：利用球面voronoi图计算最近邻方法（VNS）;利用欧氏空间内的空间数据索引结构方法（SPINS）和降维方法（APNS）。进一步,在动态的密集数据集和动态的稀松数据集两种典型的组合情况下分别着重对3 种方法处理最近邻查询的性能进行了实验比较。理论分析和实验结果表明,给出的3种方法可较好地处理球面上具有不同性质特征的空间数据对象点的近邻查询问题。