2014, Vol. 25
2. 医学影像计算教育部重点实验室（东北大学）, 辽宁 沈阳 110819
2. Key Laboratory of Medical Image Computing of Ministry of Education (Northeastern University), Shenyang 110819, China
近年来,随着智能移动设备的快速发展,基于位置服务技术得到了广泛的应用.空间数据库作为重要的支撑技术[1],为各类位置相关的查询请求,例如k近邻查询[2, 3,4]、skyline查询[5, 6]和反k近邻查询[7, 8]等提供了高效的数据获取服务.特别地,在这些查询中,反k近邻查询用来搜索那些k近邻里面包含查询点q的空间数据点,从而反映了查询点对哪些空间数据点影响较大,被证实在空间决策支持、资源分配和数据挖掘方面有着广泛的应用.然而,之前的大多数空间查询工作往往考虑理想的欧式空间和路网空间.实际上,地面、室内甚至虚拟空间内移动的物体一般都会受到地理条件的限制(例如建筑、湖泊等),因此,准确的距离计算需要考虑障碍物的因素.
在各类空间查询中,连续的反k近邻查询是一类相对复杂的查询,可以支持高级的分析和预测应用.例如,在地震的救灾重建工作中,需要在灾区设置医疗和餐饮安置点,如果用户驾驶一辆载满配送药物和食物的车,查询从出发点到终止点的路线上,可以配送给哪些安置点药物和食物.显然,这些安置点需要距离查询线段比较近,也就是在安置点的k近邻范围内(否则,可以从其他安置点搬运物品),从而为优化配送做决策支持.类似的查询可以支持冰山碰撞预测、野生动物领袖发现和虚拟游戏伙伴邀请等应用场景.而在这些空间中,障碍物都是广泛存在的,准确地计算需要考虑障碍物的影响.从上面的例子可以看出:给定一个轨迹作为查询区间,连续反k近邻问题即连续地给出查询点在区间内的反k近邻数据对象.因为移动对象在查询区间上的反k近邻是分段变化的,因此该问题即转化为对查询区间进行合理的分割,使得每个分割的区间具有相同的反k近邻查询结果.
本文针对障碍空间数据库中的连续反k近邻查询进行研究,引入了控制点和分割点的概念,提出了剪枝数据集、获取障碍物、剪枝和计算控制点和更新结果集的一套高效处理策略,从而给出了障碍空间数据库中的连续反k近邻查询的解决方法.
本文第1节介绍相关工作.第2节定义障碍空间的连续RkNN查询和相关概念.第3节详细描述障碍空间中连续RkNN查询的处理过程,阐述剪枝和求精的方法.第4节给出实验结果以及分析.第5节给出总结.
1 相关工作对于无障碍空间RkNN查询,文献[7-9]提出了无需预计算的RkNN查询方法.Stanoi等人[7]给出了在查询点q处将空间划分成6等份(每份为60°)的方法,可以证明,在每一个区域离查询点q的第k个最近邻以外的区域都可以被剪枝,得到这些未被剪枝的区域里的数据点就成为RkNN查询的候选点.Tao等人[8]提出了使用中垂线性质剪枝搜索空间的方法,有效地剪枝那些处在k个以上中垂线的半区间的数据点.Wu等人[9]提出一种新的剪枝方法——FINCH算法,该方法使用一个多边形来近似未被剪枝区域.尽管这些方法能够高效地执行RkNN查询,但它们都是在理想的欧氏空间,即无障碍物空间中查询.Cheema等人[10]对欧式空间和路网空间内的连续反k近邻问题进行了系统的研究,提出了高效的空间剪枝方法.以上这些技术并不适合应用到障碍空间中.
近年来,障碍空间的kNN查询技术得到了广泛的研究.障碍空间中,kNN查询是获取在障碍距离上k个距离查询点q最近的空间数据点.Zhang等人[11]给出了在障碍空间中基于R-tree方法解决常见的空间查询,例如范围查询、最近邻查询、e-距离连接查询、最近对查询.Xia等人[12]提出了障碍最近邻查询方法,用增量的方式处理只与查询有关的数据点和障碍物,因此过滤掉了大量数据点和障碍物.Gao等人[13]通过有效的分割对象行进的路径,提出了障碍空间内连续kNN查询的优化方法.在文献[14]中,Gao又对文献[13]中提出的算法进行了扩展研究和理论分析.由于RkNN比起kNN查询更加复杂,因此,kNN查询的处理技术并不适合应用于RkNN查询.此外,有些工作关注了障碍空间内的可见k近邻搜索[4, 15],提出了有效的优化方法.但是,由于可见近邻只考虑那些没被障碍物遮挡的数据对象,从问题定义到解决方案与本文关注的基于障碍距离的查询方法完全不同.还有一些工作对障碍空间的数据挖掘问题进行了研究,例如,文献[16]研究了障碍空间内不确定数据的聚类算法.
在最近的一项工作中,我们给出一种基于障碍Voronoi图的高效搜索固定点RkNN对象的方法[17].通过有效的剪枝规则,减少查询处理反kNN的代价.同时,Gao等人提出了一种基于R-tree的障碍空间反最近邻(RNN)查询处理方法[18].该方法不需要预计算,通过引入边界区域的概念对查询结果进行高效的剪枝.这两项工作针对的是快照查询,与连续查询的侧重点不同.对于连续查询,如果周期性地采用快照查询,效率很低,需要提出高效的模型和算法来划分移动轨迹,从而提供实时的查询结果.
2 问题定义本节首先给出一些重要的定义.
定义1(可视区间(visible region)). 一个点p在查询区间q上的可视区间Rp,q由q上所有与p的连线均不与障碍物相交的点构成.
如图 1中在查询区间q上点p的可视区间Rp,q为[S,s1]È[s3,s1]È[s8,E],在这个区间上的每一个点p¢与p的连线均不会与空间内的任何障碍物相交.
 | Fig. 1 Illustration for obstructed control point图 1 障碍控制点示意图 |
定义2(障碍控制点(obstructed control point)). 在障碍空间中,给定数据点p,障碍物集合O,在p的可视区间内,p定义为控制点,可视区间定义为p的控制区间;在p的不可视区间内,障碍物端点cp定义为p在区间R上的一个障碍控制点,当且仅当点p到区间R的最短路径经过cp,且cp对于区间R内的每个点是可见的,此时,R定义为cp的控制区间.
如图 1所示,障碍物O1的左端点u就是控制区间[s1,s2]的控制点,记为áu,[s1,s2]ñ,也就是说,对于区间[s1,s2]上的任意一点p¢,从点p到p¢的最短路径一定经过点u,且这段距离dobs(p,p¢)等于dobs(p,u)与dobs(u,p¢)之和.
定义3(障碍分割点(obstructed split point)). 在障碍空间内,查询区间为q=[S,E],障碍物集合为O,给定区间[s1,m]和[m,s2](S≤s1≤m≤s2≤E),如果[s1,m]所有查询点的障碍反k近邻结果一样,记为P1,[m,s2]所有查询点的障碍反k近邻结果一样,记为P2,且P1!=P2,则点m即为障碍空间上关于查询区间q的障碍反k近邻查询的一个分割点.所有的分割点将查询区间分割成多个分割区间.每个分割区间内所有查询点的反k近邻查询结果保持不变.
例如,图 2中关于查询q的障碍分割点为{s2},即在区间[S,s2]上,点p为q的反最近邻;在区间[s2,E]上,点p不再是q的反最近邻,点p¢则成为q的反最近邻.因此在分割点s2处,查询结果有所改变.
 | Fig. 2 Illustration for obstructed split point图 2 障碍分割点示意图 |
定义4(障碍空间的连续反k近邻(continuous obstructed reverse k-nearest neighbor,简称CORkNN)查询). 在障碍空间中,给定数据点集P,障碍物集合O,查询区间q=[S,E],CORkNN即查询点在区间[S,E]上做连续查询,返回结果集为每个分割区间所对应的查询点的反k近邻数据对象.
3CORkNN查询处理过程本节提出连续障碍反k近邻查询的处理方法.通过剪枝数据点,对每个数据点求其对应的控制点和分割点,并在计算控制点的过程中加入剪枝求精的方法,减少了计算控制点的时间和空间代价,最后对结果集进行更新,得到最终结果.
3.1 剪枝数据集本节针对障碍空间中的反k近邻查询,将大量的空间数据点进行精简处理,从而减少数据点计算的个数,减少了后面小节中对每个数据点求解控制点的总计算代价.
定理1. 若数据点到查询可视区间的最短距离大于此数据点到其障碍k最近邻(OkNN)点的距离,则此数据点一定不是q的ORkNN.
证明:假设此数据点(设为点p)是q的ORkNN,且点p到其障碍k近邻点的距离大于点p到查询可视区间的最短距离,即dobs(p,OkNN(p))>dver(p,q).由垂线性质得到:dver(p,q)是p到查询q上的最短距离,即"piÎq,dver(p,q)≥deuc(p,pi),因此,dobs(p,OkNN(p))>deuc(p,pi).又因为deuc(p,pi)≤dobs(p,pi),所以dobs(p,OkNN(p))>dobs(p,pi),即查询q上的任意一点到p的距离都远于p的OkNN到p的距离.因此,查询q上的每个点都不能为点p的OkNN,所以点p也一定不会是q的ORkNN,定理得证.
如图 3所示,以p2为圆心、dobs(p2,OkNN(p2))为半径的圆没有与查询q=[S,E]相交,即dobs(p2,OkNN(p2))< dver(p2,q),那么点p2的OkNN一定不会是查询q上的点,即点p2一定不是q的ORkNN,因此p2可以被剪枝掉.
 | Fig. 3 Illustration for pruning datasets图 3 精简数据集示意图 |
基于定理1,本文提出针对CORkNN查询的精简数据集算法DPR.
DPR首先构建障碍Voronoi图,接着获得查询线段上经过的Voronoi单元(cell),进而对每一个单元对应的数据点都作为一个快照查询点,针对每个快照查询点作为文献[17]的数据集剪枝算法的输入,以得到初步的精简数据集.这个过程的耗时几乎是整个CORkNN算法的耗时,这阶段所用时间复杂度为O(n¢logn),其中,n¢为ORkNN算法通过剪枝后得到的数据点个数,n为空间中数据点个数,且n¢<<n.然后,对精简后的数据集从边界距离上进行剪枝,即定理1中所述,从而最后得到精简数据集.这一阶段时间复杂度为O(c),c为第1阶段ORkNN算法得到的候选集数据点个数,c远小于空间中数据点个数.
3.2 获取障碍物第3.1节中提出的精简数据集算法将障碍空间中的数据点集精简到成为结果集的最小范围,接着对每一个候选集中的每个数据点进行求解.本节解决求解的第1步——获取障碍物,即对每个数据点在查询范围q上的对计算有影响的障碍物,进而减少后面步骤涉及到障碍物的计算,极大地减少了计算量.
引理1. 对一个查询区间q=[S,E],一个数据点p,由数据点p和查询q围成的区域记为DpSE,那么对p有影响的障碍物就是那些和DpSE有交集的障碍物.
证明:对p有影响的障碍物即在后面计算控制点步骤时用的障碍物,在与DpSE有交集的障碍物中,点p到查询q的路径都有可能经过这些障碍物;在DpSE之外,即与之无交集的障碍物中,点p到查询q的路径都不可能经过这些障碍物.因此,仅仅是与DpSE有交集的障碍物才能对数据点p有影响.
由引理1可知,在考察数据点p及后面计算其对应的控制点及分割点时,仅需计算与DpSE有交集的障碍物即可,这些障碍物影响控制点和分割点的计算.
定理2. 假设数据点p到查询q的两个端点(S,E)的欧式距离为deuc(p,S)及deuc(p,E),那么到p的最小距离大于max{deuc(p,S),deuc(p,E)}的MBR所包含的障碍物一定不是对p有影响的障碍物.
证明:若这样的障碍物是对p有影响的,由引理1可知,这些障碍物一定在DpSE内或者与DpSE有交集,如图 4所示,设此MBR在DpSE内的一个点为p¢.那么,点p到此MBR的最短距离dmin(p,MBR)<deuc(p,p¢)成立,并且deuc(p,p¢)<max{deuc(p,S),deuc(p,E)}.因此可以得到dmin(p,MBR)<max{deuc(p,S),deuc(p,E)},这与已知条件矛盾,因此假设不成立,从而定理得证.
 | Fig. 4 Illustration for proof of Theorem 2图 4 定理2的证明示意图 |
根据引理1和定理2对获取障碍物求解的方法,本文提出获取有效障碍物的算法OSR.该算法通过剪枝的方法获取每个数据点在查询范围q上对计算有影响的障碍物,极大地减少了计算代价.该算法的基本想法是:用R-tree的数据结构将障碍物索引,以到数据点p的最小欧式距离递增的顺序访问障碍物.对于查询q,数据点p的查询范围即为查询端点与p这3个点组成的三角形.凡是与这个三角形相交的障碍物,都是对p有影响的障碍物.这里可以进行进一步剪枝,如果p到某个障碍物MBR的最短距离都大于这个三角形中以p为顶点的两条边的长度,则这个MBR被剪枝,即其不会影响到点p;反之,还需要继续判断此障碍物是否与三角形相交,如果确实有交集,则将此障碍物放入对p有影响的障碍物集合Op中,并将此障碍物顶点放入可视图VG中供后面使用. OSR算法的时间复杂度为O(mn²),m为空间中障碍物的个数,n²为DPR算法剪枝后候选集中数据点个数.
例如,如图 5所示,查询q=[S,E],数据点为p,障碍物由R-tree索引.对于点p,其查询空间范围为DpSE,p到q的两个端点的最大距离max{deuc(p,S),deuc(p,E)}作为后面障碍物MBR剪枝的界限.遍历障碍物R-tree从N1和N2开始,此时,最小堆HO为((N2,dmin(p,N2)),(N1,dmin(p,N1))).由于p到节点N2的最短距离dmin(p,N2)小于dmax,因此将N2从最小堆移除,将其孩子节点(N5,N6)及其到p的欧式距离作为key加入最小堆HO.从HO移除堆顶N1,并将其孩子节点(N3,N4)加入HO.依此方法遍历R-tree,得到对于p的障碍物结果集Op=(O3,O4,O5,O6).因为满足剪枝条件,原来R-tree里的叶子节点O1,O2组成的节点N3被剪枝.此外,O7,O8 在DpSE之外,所以这两个障碍物也不会产生影响.
 | Fig. 5 Illustration for retrieving obstacles Op which have effects on p图 5 获取对点p有影响的障碍物Op示意图 |
上面的方法能够获取一个数据点p的所有有效障碍物及其对应的可视图VG,接下来需要找出点p在q上的障碍控制点集合.基本方法是:从p对q的查询范围内的可视图里的障碍物集合Op端点中找出对查询q可见的点,如果这些点在q上的可见区间Rp,q有交集,则需要更新.对于控制点的高效计算.本文首先使用了文献[13]提出的两种基本剪枝方法,在此不做详细介绍.在此基础上,本文提出了另一种剪枝方法.
定理3. 若一个数据点对应的控制点到查询区间的最短距离大于此数据点到其OkNN点的距离与此数据点到此控制点之间的障碍距离的差值,则此控制点无效.
证明:假设此控制点是有效的,那么由障碍控制点定义可知,此控制点一定对应一段查询区间,此查询区间是由此控制点所控制.那么,当这段查询区间内的任意一点(如p¢)为查询点时,此数据点(如p)为查询点的ORkNN结果的一部分,即点p¢到点p的距离一定小于或者等于点p到p的OkNN的距离,这与定理的假设矛盾,从而定理得证.
如图 6所示,点p为空间中的一个数据点,点p1为p的障碍第k近邻点,障碍物为O1=O11O12.
 | Fig. 6 Illustration for control points pruning图 6 控制点剪枝示意图 |
由于一个数据点p对应的控制点O12到查询区间[S,E]的最短距离大于此数据点p到其OkNN点p1的距离与点p到此控制点之间的障碍距离的差值,即dver(O12,q)≥dobs(p,OkNN(p))-dobs(p,O12),那么由定理3可知,控制点O12被移出控制点集.
基于定理3,本文提出计算某一个数据点在查询q下的控制点算法CPLC.CPLC首先求出此数据点p在查询q上的可视区间,记为Vis.接着求出p为圆心、d为半径的圆与区间Vis的相交区间.如果p的可视区间是整个查询区间,则此相交区间即为以p为控制点的控制区间.反之,先更新控制点集,然后对控制点集中的每个控制点应用定理3进行判断:如果该控制点到查询q的垂直距离比p与其障碍k近邻点的距离与p到此控制点的障碍距离的差值还大,那么从控制点集中移除此无效控制点;反之,求以控制点为圆心的圆与不可见区间的交点区间作为此控制点的控制区间,并加入结果集.CPLC算法时间复杂度为O(mn²),m为空间中障碍物的个数,n²为剪枝后候选集中数据点个数.
下面通过一个具体例子来解释算法CPLC.
如图 7所示,图中已知点p2,求p2关于查询q的分割点及结果集.
 | Fig. 7 Illustration for control points computation图 7 控制点计算示意图 |
首先,求出p2的最近邻为p1,d=dobs(p1,p2).因为dver(p2,q)<dobs(p1,p2),所以点p2可能会是结果.画出点p2的可视区间为Vis=[S,a]È[b,E]且a¹b;Cir(p2,d)与可视区间有交点s1,则将áp2,p2,[s1,a]ñ加入结果集.控制点集合CPL={O11,O12}.对于每个控制点进行考察:
· 对于点O11,因为dver(O11,q)<dobs(p1,p2)-dobs(p2,O11),因此计算Cir(O11,dobs(p1,p2)-dobs(p2,O11))与不可视区间q-Vis的交点(记为s2),因此,将áp2,O11,[a,s2]ñ加入结果集;
· 对于点O12,因为dver(O12,q)<dobs(p1,p2)-dobs(p2,O12),因此计算Cir(O11,dobs(p1,p2)-dobs(p2,O12))与不可视区间q-Vis的交点(记为s3,s4),且s2<s3,因此,将áp2,O12,[s3,s4]ñ加入结果集.
3.4 更新结果集前面一节介绍了对于每个数据点的控制点的计算方法,这样,在查询q上对某个数据点的控制点集已经获得,下一步就是要评估此数据点对于当前结果集的影响.更新结果集算法RLU的基本想法就是在结果集上的查询区间与此数据点对应的控制区间合并.具体来说,RLU将数据点p得到的结果集中的每个分割区间Rpi与CORkNN查询结果集的每个分割区间Ri进行逐个判断,如果Rpi为当前查询结果集的分割区间的子集,即可将此数据点p加入到结果集对应区间结果里;反之,求Rpi与查询结果集分割区间能够相交的区间Ri并求其交集,即将结果集分割区间细划分,交集部分对应的数据点集为p和Ri的数据点集的并集,其他两部分的结果分别为原查询分割区间对应结果点集和点p.此算法的时间复杂度为O(n²n²),n²为剪枝后候选集中数据点个数.
3.5CORkNN查询算法前面4小节介绍了在求解障碍连续反k近邻查询中每个关键问题的求解算法.这些算法可以构成完整的CORkNN查询算法.CORkNN查询算法首先根据数据点和障碍物的R-tree构造障碍Voronoi图;接着用前面所述的DPR算法精简数据点,对于得到的精简后的数据点中的每个点(如点p),求其OkNN,以dobs(p,OkNN(p))作为key值建立最小堆;对于堆中的每个数据点进行计算,使用OSR算法获取有效障碍物,接着使用CPLC算法计算此点p对应的控制点,得到点p的结果集;最后,根据算法RLU更新结果集.
4 实验结果与分析在这一节里,我们进行详细的实验评估.所有的实验都是在C++环境下实现的,实验运行环境为Inter Core4 i7-2600 3.40GHz CPU,8.00GB内存和运行64位Windows操作系统.
4.1 实验设置实验分别基于真实数据和模拟数据的数据集.真实数据集使用两组数据,分别来自hypsogr和utility**.
Hypsogr包含代表在德国76999MBRs的2D高度数据,utility包含代表在德国17790MBRs的2D公用网络数据.模拟数据集的大小和真实数据集的大小相似,并服从正态分布(N)、Zipf分布(Z)和均匀分布(U).
因为障碍空间的RkNN查询包括一个数据集P和一个障碍物集合O,真实数据集分别表示这两种数据集,即(P,O)=(hypsogr,utility).此外，我们使用6种不同的分布组合(N,Z),(N,U),(Z,U),(Z,N),(U,N),(U,Z)来模拟数据集P和障碍物集合O.
所有的数据点和障碍物都由一棵R-tree索引,节点大小设为4KB,k值缺省设为5,查询长度设为数据集大小的百分比默认为4%.为了详细测试算法的性能,选用了不同的测试参数,详见表 1.
|
Table 1 Parameter range and default values 表1 参数范围和默认值 |
在这一节中,实验评估和分析本文所提出的算法CORkNN的CPU处理时间和I/O代价.由于本文算法首次针对障碍空间数据库中的连续反k近邻查询进行了研究,现有的相关算法(例如障碍空间连续kNN查询等)也无法通过修改来解决该问题,因此首先设计一种基本方法(Basic方法)作为对比算法.Basic算法连续查询障碍空间RkNN对象,即求出每个点的障碍kNN,再找出这些kNN里与查询线段q有相交的区间的数据点进行比较.
首先评估k值的变化对CPU时间和磁盘I/O代价的影响.从图 8可以看出:在k值从1变化到9的过程中, CPU时间随着k值的增加而增加.提出的CORkNN算法的CPU占用时间明显比传统方法Basic要少,而且两者方法的CPU时间差距较大,因此用对时间取对数的方法表示.实验结果表明,本文所提出的CORkNN方法明显好于传统Basic方法.
 | Fig. 8 Effects of k on CPU time图 8 k值对CPU时间的影响 |
图 9给出了k值的增加对磁盘I/O代价的影响,纵坐标为需要访问的R树节点数目.可以发现:随着k值的增加,需要访问的数据点越多,CPU处理占用的时间越多,磁盘I/O代价越大;而且由于本文的CORkNN方法仅仅需要访问离查询线段较近的数据点,因此其磁盘I/O代价要小很多.
 | Fig. 9 Effects of k on I/O costs图 9 k值对I/O代价的影响 |
下面评估数据点个数对CPU执行性能和I/O代价的影响.从图 10可以发现:随着数据点数量的增加, CORkNN方法的CPU用时下降,而传统的方法的CPU用时增加,而且CORkNN方法比传统方法的耗时要少.这是因为对于CORkNN方法,数据点越密集,查询点与其障碍Voronoi邻居越近,计算障碍距离的时候大多数只需要计算欧氏距离;而且获得最小候选集后,对每个数据点计算其有效障碍物时,由于数据点密度加大,需要处理的障碍物也相对较少,因此计算控制点的时间大幅度减少.而传统Basic方法需要计算每一个数据点的连续障碍反kNN,因此对于Basic方法,数据点越多,CPU用时越多.
 | Fig. 10 Effects of data point number on CPU time图 10 数据点的个数对CPU时间的影响 |
图 11反映了随着数据点数量的增加,传统Basic方法的磁盘I/O代价随之增加,而我们的CORkNN方法的I/O代价则降低.这是由于Basic方法需要计算每一个数据点,因而数据点越多,计算的数据点越多.而对于CORkNN方法,数据点越密集,需要访问的障碍物越少,因而在每个区间里剪枝掉的数据点越多,并且计算控制点时访问的节点个数也越少,所以CORkNN方法的磁盘I/O代价随着数据点个数的增加而减少.
 | Fig. 11 Effects of data point number on I/O costs图 11 数据点的个数对I/O代价的影响 |
我们来进一步地评价障碍物密度的变化对执行效率的影响.由图 12可知:障碍物密度越大,CPU执行时间越长,而且CORkNN方法明显好于传统方法.这是由于障碍物个数越多,需要计算的障碍距离越多,CPU执行时间越长.而计算障碍距离比计算欧氏距离用时更多,传统Basic方法需要计算每一个数据点的障碍距离,比CORkNN方法需要计算的障碍距离要大,因此它所耗用的CPU时间更多.
 | Fig. 12 Effects of obstacle number on CPU time图 12 障碍物的个数对CPU时间的影响 |
图 13给出了不同数据量的障碍物对磁盘I/O代价的影响.随着障碍物个数的增加,两种方法的I/O代价都随之增加.但是CORkNN方法有效的剪枝策略极大地减少了障碍物的访问数量,因此磁盘I/O代价明显比传统的Basic方法的代价要小很多.
 | Fig. 13 Effects of obstacle number on I/O costs图 13 障碍物的个数对I/O代价的影响 |
图 14和图 15分别给出了两种算法不同数据分布的影响的实验结果.横坐标1,2,…,6分别代表数据点和障碍物分布(数据点分布,障碍物分布)的不同组合,分别对应为(P,O)=(N,Z),(N,U),(Z,U),(Z,N),(U,N),(U,Z).其中, P,O分别服从正态分布(N)、Zipf分布(Z)和均匀分布(U).例如,(N,Z)代表数据点服从均匀分布,障碍物服从Zipf分布.
 | Fig. 14 Effects of data distribution on CPU time图 14 数据的分布对CPU时间的影响 |
 | Fig. 15 Effects of data distribution on I/O costs图 15 数据的分布对I/O代价的影响 |
图 14给出了数据点和障碍物服从于不同的数据分布对CPU执行时间的影响情况.可以看出:数据分布的变化对CPU执行时间的影响不大,但是CORkNN方法由于访问数据比Basic方法要少,因此在CPU时间上优于传统方法.
图 15给出了不同的数据分布组合对于数据点和障碍物在磁盘I/O代价上的影响.可以发现,数据分布的不同对磁盘I/O代价影响不大.CORkNN方法由于包含高效的剪枝方法,减少了大量访问数据点和障碍物的个数,降低了磁盘I/O代价.
最后,用实验验证研究查询长度ql(查询占数据空间的百分比)的影响.图 16和图 17显示了当ql作为变量,将k值固定在k=5时,CORkNN算法在CPU占用时间和磁盘I/O代价上的有效性.
 | Fig. 16 Effects of query length on CPU time图 16 查询长度对CPU时间的影响 |
 | Fig. 17 Effects of query length on I/O costs图 17 查询长度对I/O代价的影响 |
由图 16可以观察到,CORkNN算法的查询时间随着查询线段的长度的增加而增加.这是由于查询长度越大,需要获取的数据点越多、搜索障碍物范围越大、计算分割点的时间增加以及需要更新的结果集增大;而原始Basic方法由于对每个数据点都进行连续障碍kNN查询,与查询线段长度关系不大,因此其所占用的CPU时间不变.
图 17给出了查询长度的变化对磁盘I/O代价的影响情况.可以看出:随着查询长度ql的增加,传统Basic方法对磁盘I/O代价的影响几乎为0.这是由于传统方法对每个数据点都需要计算,查询长度的改变对其计算涉及到的数据点个数没有影响;而CORkNN算法由于在查询线段附近计算需要有更多的计算,因此对磁盘I/O代价的影响随着查询线段长度的增加而增加.
5 结 论本文对障碍空间数据库中的连续反k近邻查询问题进行定义,然后提出了解决CORkNN查询的所需要的剪枝数据集、获取障碍物、计算控制点和更新结果集各个步骤的优化技术和完整的CORkNN算法.通过多种数据集上的测试,验证了所提出的算法与基本方法相比,在处理效率上有大幅度的提高.
| [1] | Zhang J, Zhu ML, Papadias D, Tao YF, Lee DL. Location-Based spatial queries. In: Proc. of the 2003 ACM SIGMOD Int’l Conf. on Management of Data. San Diego: ACM Press, 2003. 443-454 . |
| [2] | Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries. In: Proc. of the ’95 ACM SIGMOD Int’l Conf. on Management of Data. San Jose: ACM Press, 1995.71-79 . |
| [3] | Berchtold S, Ertl B, Keim DA, Kriegel HP, Seidl T. Fast nearest neighbor search in high-dimensional space. In: Proc. of the 14th Int’l Conf. on Data Engineering. Orlando: IEEE Computer Society, 1998.209-218 . |
| [4] | Gao YJ, Zheng BH, Chen GC, Li Q, Guo XF. Continuous visible nearest neighbor query processing in spatial databases. VLDB Journal, 2011,20(3):371-396 . |
| [5] | Sharifzadeh M, Shahabi C. The spatial skyline queries. In: Proc. of the 32nd Int’l Conf. on Very Large Data Bases. Seoul: ACM Press, 2006. 751-762. |
| [6] | Lee KCK, Lee WC, Zheng BH, Li HJ, Tian Y. Z-SKY: An efficient skyline query processing framework based on Z-order. VLDB Journal, 2010,19(3):333-362 . |
| [7] | Stanoi I, Agrawal D, Abbadi AE. Reverse nearest neighbor queries for dynamic databases. In: Proc. of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 2000. 44-53. |
| [8] | Tao YF, Papadias D, Lian X. Reverse kNN search in arbitrary dimensionality. In: Proc. of the 30th Int’l Conf. on Very Large Data Bases. Toronto: Morgan Kaufmann Publishers, 2004. 744-755. |
| [9] | Wu W, Yang F, Chan CY, Tan KL. Finch: Evaluating reverse k-nearest-neighbor queries on location data. Proc. of the VLDB Endowment, 2008,1(1):1056-1067. |
| [10] | Cheema MA, Zhang WJ, Lin XM, Zhang Y, Li XF. Continuously reverse k nearest neighbors queries in euclidean space and in spatial networks. VLDB Journal, 2012,21(1):69-95 . |
| [11] | Zhang J, Papadias D, Mouratidis K, Zhu ML. Spatial queries in the presence of obstacles. In: Proc. of the 9th Int’l Conf. on Extending Database Technology. LNCS 2992, Heidelberg: Springer-Verlag, 2004.366-384 . |
| [12] | Xia CY, Hsu D, Tung AKH. A fast filter for obstructed nearest neighbor queries. In: Proc. of the 21st British National Conf. on Databases. LNCS 3112, Edinburgh: Springer-Verlag, 2004.203-215 . |
| [13] | Gao YJ, Zheng BH. Continuous obstructed nearest neighbor queries in spatial databases. In: Proc. of the 28th ACM SIGMOD Int’l Conf. of Management of Data. Providence: ACM Press, 2009. 577-590. |
| [14] | Gao YJ, Zheng BH, Chen G, Chen C, Li Q. Continuous nearest-neighbor search in the presence of obstacles. ACM Trans. on Database System, 2011,36(2):Article 9 . |
| [15] | Wang YF, Gao YJ, Chen L, Chen G, Li Q. All-Visible-k-Nearest-Neighbor queries. In: Proc. of the 23rd Int’l Conf. on Database and Expert Systems Applications. LN CS 7447, Vienna: Springer-Verlag, 2012.392-407 . |
| [16] | Cao KY, Wang GR, Han DH, Yuan Y, Hu YC, Qi BL. Clustering algorithm of uncertain data in obstacle space. Journal of Frontiers of Compter Science and Technology, 2012,6(12):35-45 (in Chinese with English abstract). |
| [17] | Yu XN, Gu Y, Zhang TC, Yu G. A method for reverse k-nearest-neighbor queries in obstructed space. Chinese Journal of Computers, 2011,34(10):1917-1925 (in Chinese with English abstract) . |
| [18] | Gao YJ, Yang JC, Chen G, Zheng BH, Chen C. On efficient obstructed reverse nearest neighbor query processing. In: Proc. of the 19th Int’l Conf. on Advances in Geographic Information Systems. Chicago: ACM Press, 2011. 191-120. |
| [16] | 曹科研,王国仁,韩东红,袁野,胡雅超,齐宝雷.障碍空间中的不确定数据聚类算法.计算机科学与探索,2012,6(12):35-45. |
| [17] | 于晓楠,谷峪,张天成,于戈.一种障碍空间中的反k最近邻查询方法.计算机学报,2011,34(10):1917-1925 . |