一种基于Voronoi图的反k最近邻查询方法

摘要

本发明公开一种基于Voronoi图的反k最近邻查询方法，属于空间数据查询技术领域。包括下述步骤：步骤1：根据查询站点集，生成相应的Voronoi图；步骤2：导入查询对象数据集；步骤3：输入k值和查询点q的坐标，按k值调用步骤1所生成Voronoi图，得到RkNN查询结果；步骤4：结束。本发明实现变化频繁的数据集下的双色RkNN查询，即在某一k阶Voronoi图上可以查询出R(k－1)NN、RkNN、R(k＋1)NN的结果。本发明减少了预计算量，并且查询效率与现有方法相比有较大提高，而且随着查询对象集数量的增大，这种优势也越明显，增强了Voronoi图的应用性。

说明书

技术领域

本发明涉及一种查询方法，特别涉及一种基于Voronoi图的反k最近邻查询方法，属于空间数据查询技术领域。

背景技术

空间数据库中移动对象查询技术可以应用于城市交通、航空航天、通讯网络等存在移动对象的网络中，它可以根据大量的时空数据来挖掘信息从而提供给客户相关咨询。典型的空间查询是最近邻（nearest neighbors，NN）查询和k最近邻（k nearest neighbors，kNN）查询。例如：旅客会问哪家酒店距离车站最近；司机会查询最近的2个加油站在什么地方。反最近邻（reverse  nearest neighbors，RNN）查询是NN查询的变种，其回答谁把查询对象看成最近邻居，如某个城市的一系列连锁店可能要给客户发布一些广告，每个连锁店发广告的客户群是不同的，这些客户的范围可以定义成为受到某个连锁店影响的客户群，用RNN查询就可以确定这些群体；还有在移动数据库系统中各个移动对象倾向于在最近或者反向对进的对象中共享一些信息等等。此外，在游戏领域，空间数据库查询技术也有一定的发展前景，比如由美国的Blizzard公司开发的大型网络游戏中，游戏玩家在地图侦测中发现敌人或寻找建筑物等操作就是kNN和RNN的体现。

反k最近邻（reverse k nearest neighbors，RkNN）查询则是kNN查询的补充和发展，按数据集的不同分为单色RkNN查询和双色RkNN（bichromatic reverse k nearest neighbors，BRkNN）查询。F.korn和S.Muthukrishnan提出了RNN查询的概念，并给出了求解RNN的查询方法。使用了两个R树来进行查询、插入、删除操作。Yang和Lin改进了以上的方法，使得用单一树进行RNN查询和NN查询成为可能。Stanoi等人提出了一种在没有预测的情况下进行计算的方法。该方法将查询点的周边范围划分成6个大小相同的扇区，首先在各自的扇区内找到RNN的候选对象；其次，对于每个候选对象完成了一个独立的NN查询来判断这个候选对象是不是最后的结果。Maheshwari等人提出了主存数据结构的RNN查询，对于每个点其结构维持着其到最近邻的距离。

Stanoi等人提出的方法在高维空间中，随着维数的增加，RNN的候选值呈现指数增长。效率大幅降低。为了解决这个问题，Singh等人提出了通过执行常规的kNN查询找出RkNN候选值。但该方法的缺点在于不是总能找到所有的RkNN点。Tao等人提出的方法与Stanoi等人提出的相似，该方法分成筛选和精炼两个阶段，给定一个查询点q，方法递归回到q点未划分的空间，直到没有候选对象剩下。在过滤的步骤时，去除了一些确定为错误结果的候选对象。

在基于Voronoi图的RNN查询方面，李松、郝忠孝提出的在欧几里德平面内的Voronoi图中使用Range-k验证法来查找结果。即以点集中一点为中心，点到查询点的距离为半径生成一个判断圆来以此找出RNN。该方法只适用于对单色RkNN的查询，在双色RkNN查询时存在大量不必要的I/O操作。Maytham Safar则提出了网络Voronoi图的空间中进行RNN查询。方法适用于交通网络等方面，在查询对象频繁更换时效率很低。

Voronoi图是同给定的客体离散集（如点集）的距离确定的空间分解，特别是点集p={p1,p2,…,pn}的Voronoi图被定义为cell集。这里每个cell，V(pi)是一个空间区域，由距离pi比距离p中其他点更近的全部空间数据点组成。Voronoi图可以推广到k阶 Voronoi图（order k voronoi diagram，KVD），距离判断法是一种现有的Voronoi图的生成方法，图1为利用该方法生成的3阶 Voronoi图，图2为利用该方法生成的2阶3阶混合Voronoi图。在KVD中每个区域中的查询对象依据BRkNN的定义可知，就是当前区域的生成元的RkNN值。如图1所示，查找站点3的R3NN值：首先定位那些生成元所含站点3的Voronoi区域，有V(1,3,5)、V(1,3,4)、 V(1,3,6) 、V(1,2,3)四个。因此，这四个Voronoi区域内所包含的查询对象都是站点3的R3NN查询结果。

但是，现有的使用KVD执行BRkNN查询方法具有明显的缺点：

(1)高代价的预计算。KVD需要预计算所有的KVD的cell和与cell相关的所有信息如生成元、Voronoi边、Voronoi顶点等。

(2)不支持动态改变的k值。KVD仅能适应带有明确k值的RkNN查询，KVD适应k值不大于图的阶数的RkNN查询。因此，这个技术不适用于预先不知道k值或可能动态改变k值的情形。

(3)效率低下的更新操作。对于每个插入或删除操作，cell不得不重新计算。

发明内容

本发明针对上述问题及缺点，为了能够实现在单张k阶Voronoi图上查询多个k值的BRkNN结果，提供了一种基于Voronoi图的反k最近邻查询方法（BRKVD），来实现变化频繁的数据集下的双色RkNN查询，即在某一k阶Voronoi图上可以查询出R(k－1)NN、RkNN、R(k＋1)NN的结果。

本发明的目的是通过以下技术方案实现的：一种基于Voronoi图的反k最近邻查询方法，是采用过滤-提炼的框架模型。在过滤阶段，按k值调用所需要的Voronoi图，并以查询站点为依据在该 Voronoi图上确定由哪些Voronoi多边形组成查询范围，然后将查询范围内的所有查询对象定为候选集。在提炼阶段，以k值为标准，如果k值与调用的Voronoi图的阶数相同，那么候选集中所有的查询对象即为结果；如果不同，那么先将所有候选集中相同的查询对象筛选出来确定为结果，然后使用Range-k验证方法验证余下的候选对象，从而得到最终的查询结果，具体包括下述步骤：

步骤1：根据查询站点集，生成相应的Voronoi图，方法为：现有的Voronoi图生成方法；

步骤2：导入查询对象数据集，方法为：对数据文件进行读取，并显示数据；

步骤3：输入k值和查询点q的坐标，按k值采用步骤1所生成阶数为m的Voronoi图，得到RkNN查询结果，其中：

当k＝m时，所有包含站点q的多边形内的查询对象即为结果，

当k＜m时，查检所有包含站点q的多边形内的查询对象，当查询对象的位置在包含站点q的k－3阶Voronoi多边形内，即为结果；当不在时，以Range-k验证法确定结果，即以查询对象为圆心，到站点q的距离为半径做圆，当圆内及圆上所包含的站点数≤k，即为结果，反之则不是，

当k＞m时，所有包含站点q的Voronoi多边形内的查询对象即为结果；并且分别检查这些多边形的邻接多边形内的查询对象，以查询对象为圆心，到站点q的距离为半径做圆，当圆内及圆上所包含的站点数≤k＋1，即为结果，反之则不是；

步骤4：结束。

步骤1所述的根据查询站点集，生成相应的Voronoi图，能够查询出R(k－1)NN、RkNN、R(k＋1)NN的结果。

本发明与现有技术相比具有下列优点效果：实现了在单张k阶Voronoi图上查询多个k值的BRkNN结果。根据Voronoi图的性质可知R(k－1)NN是RkNN的一个子集，那么同理可以推出R(k－2)NN、R(k－3)NN也是RkNN的子集，而RkNN同样是R(k＋1)NN、R(k＋2)NN的子集。那么性质也同样可以延伸开来，在一张k阶Voronoi图上查询出R(k＋2)NN或者R(k－3)NN的结果。但要指出的是，只有当k值与Voronoi的阶数相同时，才能直接得到结果。当两个值不同时，实际上得到的只是一个缩小的查询范围或者说是一个结果候选集，而正确的结果还要经过再次的计算才能得到。如果在k阶Voronoi图上得到的查询范围很大，如R(k＋2)NN、R(k－3)NN。那么这就意味着得到的候选集也很大，即候选集中查询对象的个数会增多。这样就会给接下来的工作带来很大的计算量。因此并不是说在一张k阶Voronoi图上能查询的k值越多越好。本发明为了兼顾查询速度和磁盘存储量，所提出的方法只实现了在一张k阶Voronoi图上查询R(k－1)NN、RkNN、R(k＋1)NN三个结果。

目前较好的RkNN查询方法是Finch方法，将本发明所设计的BRKVD方法与Finch方法进行了比较，测试两种方法查询过程中访问索引结点次数（I/O次数）。主要比较在相同站点不同k值和不同站点相同k值两种情况下方法访问索引结点的次数。测试结果表明本发明减少了预计算量，并且查询效率与现有方法相比有较大提高，而且随着查询对象集数量的增大，这种优势也越明显，增强了Voronoi图的应用性。

附图说明  

图1为一种距离判断法生成的3阶Voronoi图形示意图；

图2为一种距离判断法生成的2阶3阶混合Voronoi图形示意图；

图3为本发明一种基于Voronoi图的反k最近邻查询方法人文景观站点数据集；

图4为本发明一种基于Voronoi图的反k最近邻查询方法生成Voronoi图数据文档；

图5为本发明一种基于Voronoi图的反k最近邻查询方法导入的查询对象；

图6为本发明一种基于Voronoi图的反k最近邻查询方法输入信息界面；

图7为本发明一种基于Voronoi图的反k最近邻查询方法查询结果；

图8为本发明一种基于Voronoi图的反k最近邻查询方法固定查询站点不同k值测试；

图9为本发明一种基于Voronoi图的反k最近邻查询方法固定k值不同查询站点测试。

图10为本发明一种基于Voronoi图的反k最近邻查询方法总流程图。

具体实施方式

下面结合具体实施例对本发明进行进一步详细说明，但本发明的保护范围不受具体的实施例所限制，以权利要求书为准。另外，以不违背本发明技术方案的前提下，对本发明所作的本领域普通技术人员容易实现的任何改动或改变都将落入本发明的权利要求范围之内。

实施例1 

一种基于Voronoi图的反k最近邻查询方法，包括下述步骤：

步骤1：根据查询站点集，生成相应的Voronoi图，方法为：现有的Voronoi图生成方法；因本发明中每张k阶Voronoi图能够查询R(k－1)NN、RkNN和R(k＋1)NN的结果，所以根据查询的需要生成1、3、6、9…阶Voronoi图；

步骤2：导入查询对象数据集，方法为：对数据文件进行读取，并显示数据；

步骤3：输入k值和查询点q的坐标，按k值调用步骤1所生成阶数为m 的Voronoi图，得到RkNN查询结果，其中：

当k＝m时，所有包含站点q的多边形内的查询对象即为结果，

当k＜m时，查检所有包含站点q的多边形内的查询对象，当查询对象的位置在包含站点q的k－3阶Voronoi多边形内，即为结果；当不在时，以Range-k验证法确定结果。即以查询对象为圆心，到站点q的距离为半径做圆，当圆内及圆上所包含的站点数≤k，即为结果，反之则不是，

当k＞m时，所有包含站点q的Voronoi多边形内的查询对象即为结果；并且分别检查这些多边形的邻接多边形内的查询对象，以查询对象为圆心，到站点q的距离为半径做圆，当圆内及圆上所包含的站点数≤k＋1，即为结果，反之则不是；

步骤4：结束。

实施例2

如图3所示以一个真实的人文景观地标数据集CD，来进一步说明本发明提出的基于Voronoi图的反k最近邻查询方法。包括以下步骤：

步骤1：根据CD人文景观站点集，生成Voronoi图形数据，并保存文档。

生成图形模块保存的文档如图4所示，图中数据为3阶 Voronoi图的数据。每一行数据可能描述一个Voronoi多边形。每行中的数据分为三部分，分别是生成元，Voronoi多边形的顶点和最小边界矩形MBR。每部分数据之间用“：”隔开。我们来看第一行数据，第一个“：”之前的6组数字为多边形的生成元。每二组数字表示一对坐标，因为是3阶多边形，3对坐标正好表示3个生成元。第二个“：”之前的数据表示多边形的顶点，同样也是每二组数字表示一对坐标。剩下的4组数据表示多边形的MBR，前两组表示MBR的左上角坐标，后两组表示MBR的右下角坐标。

步骤2： 导入查询对象。图5中小实心点为查询对象集，大实心点为站点集。

步骤3：输入信息进行查询，得到查询结果。如图6所示，分别输入要查询的k值，及查询站点的x，y坐标即可。图7中给出了为点(8770438,2050064)的R6NN结果。

步骤4：结束

本实施例采用VC++实现，实验在处理器为P4 2.4GHz，主存为1GB，操作系统为WindowsXP的微机上进行，本实施例数据集采用了真实的文化地标及居民点聚点的部分数据。CD数据集的站点数为2099，查询对象数为4994，其特点是站点集均匀分在国内全境，其中北部相对聚中，而查询对象集相对集中在北部。本实例将本发明与Finch方法进行了比较，测试两种方法查询过程中访问索引结点次数（I/O次数），实验结果如图8-9所示。

在图8中，点1、点2、点3是查询对象分布与站点分布相对集中的情形，可以看出两种方法在这种情况下所需要的I/O次数不相上下，都维持在较低的数据上。点4、点5、点7、点8是查询对象分布与站点分布相对均匀的情形，在这种情况下两种方法所需的I/O次数也相差不多，都维持在较高的数值上。点6和点9则是查询对象分布相对集中站点分布均匀的情况，这时Finch方法所需的I/O次数较高，而BRKVD方法所需的I/O次数相对较低。因此，在处理站点平均分布查询对象相对集中分布的数据集时，BRKVD方法在整体上要优于Finch方法。

在图9中，点1、点3、点7位于站点和查询对象都集中的地方。点2、点6位于站点分布均匀查询对象分布集中的地方。点4、点5位于站点分布集中查询对象分布均匀的地方。从图9中可以看出点1、点3、点7的情形时，BRKVD方法由于站点和查询对象分布的影响I/O次数有了明显的起伏。但数值维持在较低的位置且与Finch方法的I/O次数相差不大，且稍优于后者。在点2、点6的情形时，看出Finch方法由于受到查询对象分布的影响I/O次数快速增加。而BRKVD方法则I/O次数较低好于前者。在点4、点5的情形时，BRKVD方法受站点和查询对象分布的影响不大，I/O次数较低。Finch方法受查询对象分布的影响较大，I/O次数较BRKVD方法有了明显的增涨。从整体上看，图9显示BRKVD方法要好于Finch方法。