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

张丽平1刘 蕾1郝晓红1李 松1郝忠孝1,2

1(哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080)

2(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)

(zhanglptg@163.com)

为了解决已有研究成果无法有效处理障碍空间中的组反k最近邻查询问题,提出了障碍物环境中基于Voronoi图的OGRkNN查询方法,该方法获得的结果集是将一组查询点中任意一点作为障碍kNN的数据点集合,在实际应用中可以用来评估一组查询对象的影响力.依据障碍物集合是否发生变化提出了2种情况下的OGRkNN查询方法,一种是静态障碍物环境下的OGRkNN查询(简称STA_OGRkNN查询)方法,另一种是动态障碍物环境下的OGRkNN查询(简称DYN_OGRkNN查询)方法.其中STA_OGRkNN查询方法利用Voronoi图的邻接特性可以在剪枝阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,提高整个算法的查询效率,在精炼阶段有效地提高了算法的准确性.进一步给出了3种情况下的DYN_OGRkNN查询方法,分别为障碍物动态增加情况下的OGRkNN查询算法、障碍物动态减少情况下的OGRkNN查询算法以及障碍物动态移动情况下的OGRkNN查询算法.理论研究和实验结果表明所提算法具有较高效率.

关键词Voronoi图;组反k最近邻;障碍空间;空间数据库;动态查询

随着基于位置服务技术的广泛应用,空间数据库中的最近邻(nearest neighbor, NN[1])查询及它的变体查询成为热点问题.近年来,最近邻查询的研究进一步拓展到反向最近邻查询[2]、组最近邻查询[3]、可视最近邻查询[4]、可视反向k最近邻查询[5]、不确定数据集中的k最近邻查询[6]、强邻近对查询[7]、连续反k最近邻查询[8]、聚集最近邻查询[9-10]、双色数据集上的反向最近邻查询[11]、移动k最近邻查询[12]等方面.所取得的成果解决了最近邻查询领域的一些重要问题.

k最近邻(reverseknearest neighbor, RkNN[8])查询是空间数据库中的重要的查询之一,在空间决策支持、资源分配和数据挖掘方面有着广泛的应用.RkNN查询获得将查询对象作为k最近邻的数据对象集合,可以反映出该查询对象对哪些空间对象影响较大,所以一般用来评估查询对象的影响力.例如,在一家商场的选址工作中,需要评估该商场对附近哪些人群有影响力,该商场所吸引的顾客群就是RkNN查询所要找的影响集.由于此类查询可以支持高级的分析和预测应用,因此在实际应用中已经变得越来越重要.对于RkNN查询,文献[13]提出了一种新的双色反向最近邻查询,该查询利用基于网格的方法对空间对象进行聚类,同时利用B+树进行索引方向角,来达到有方向性的查询.根据实际需求,有时需要对一个商业区进行评估影响力,即查询一组查询对象的RkNN结果,因此宋晓宇等人提出了组反k最近邻(group reverseknearest neighbor, GRkNN[14])查询.该查询方法通过计算查询对象的最小覆盖圆,将圆中的对象作为一个整体来计算该组查询点RkNN的搜索区域.

以上查询均是在理想的欧氏空间中,但是现实空间中不可避免会有一些地理条件的限制(例如建筑、河流、山等),因此2个对象之间的最短距离必须考虑障碍物的因素.对于障碍空间中的查询,于晓楠等人[15]提出了一种障碍空间中的反k最近邻查询方法,该方法利用障碍Voronoi图的性质设计了高效的剪枝策略,可以大幅度地减少搜索障碍反k最近邻对象的时间和空间.Gao等人[16]引入一种新的边界区域的概念,可以有效地处理障碍反k最近邻查询.杨泽雪和郝忠孝[17]提出空间数据库中的组障碍最近邻查询.在障碍空间中,现有的空间查询研究成果只涉及到障碍最近邻查询、障碍反向最近邻查询、障碍组最近邻查询、障碍反k最近邻查询等方面,并没有涉及障碍组反k最近邻查询问题.因此,障碍空间中的组反k最近邻查询问题是一个新的需要解决的问题.

为了解决障碍空间中的组反k最近邻查询问题,基于Voronoi图,本文提出了障碍空间中的GRkNN查询方法(OGRkNN查询方法).该方法获得的结果集是将这组查询点中任意一点作为障碍k最近邻的数据点集合.查询中将GRkNN查询中的欧氏距离度量改为障碍距离度量.在实际应用中可以用来评估一组查询对象的影响力.本文依据障碍物集合是否发生变化分2种情况讨论OGRkNN查询方法:1)静态障碍物环境下的OGRkNN查询方法(简称STA_OGRkNN查询方法);2)动态障碍物环境下的OGRkNN查询方法(简称DYN_OGRkNN查询方法).其中STA_OGRkNN查询方法包括2个过程:剪枝过程和精炼过程.利用Voronoi图的邻接特性可以在剪枝阶段和精炼阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,提高整个算法的查询效率.进一步给出了3种情况下的DYN_OGRkNN查询方法.

1定义与定理

定义1. Voronoi图[18].给定一组生成点P={p1,p2,…,pn},其中2<n<∞,且当ij时,pipj.其中,i,jIn={1,2,…,n}.Voronoi区域由公式给出:VP(pi)={p|dist(p,pi)≤dist(p,pj)}.式中jijIndist(p,pi)为ppi之间的最小距离.由pi所决定的区域为Voronoi多边形.而由VD(p)={VP(p1),VP(p2),…,VP(pn)}所定义的图形被称为Voronoi图.共享相同的边的Voronoi多边形被称为邻接多边形,它们的生成点被称为邻接生成点.

定义2. Voronoi图的k级邻接生成点[18].给定一组生成点P={p1,p2,…,pn},生成Voronoi图,其中2<n<∞,且当ijpipj.其中,i,jIn={1,2,…,n}.pik级邻接生成点定义如下:

1) 1级邻接生成点

AG1(pi)={pj|VP(pi)和VP(pj)有公共边};

2)k(k≥2)级邻接生成点

AGk(pi)={pj|VP(p)和VP(pj)有公共边,pAGk-1(pi)}.

定理1[18]. 点q为Voronoi单元VP(pi)内任一点,pk+1AGk+1(pi).那么必存在一点pkAGk(pi)使得dist(q,pk)≤dist(q,pk+1).

定理2[18]. 对于Voronoi多边形VP(pi)内任一点qqpik级邻接生成点的最小距离小于到任何pik+1级邻接生成点的距离(k为整数,k≥1).

定理3[18]. 对于Voronoi多边形VP(pi)内任一点qq的第k+1个最近邻qk+1qk+1AG1(p)∪AG2(p)∪…∪AGk(p)(k为整数,k≥1),即q的第k+1个最近邻在q的最近邻前k级邻接生成点中.

基于点与点的可视性[18]﹑点与点的障碍距离[19]和组反k最近邻查询[14]的基本概念,本文进一步提出了障碍组反k最近邻查询的定义如定义3所示.

定义3. 障碍组反k最近邻查询.在障碍空间中,给定一组查询点集Q={q1,q2,…,qn}和一个数据点集P={p1,p2,…,pm},在数据集P中查询那些k个最近邻中包含Q中任意一个查询点q的空间数据点,具体定义形式为

OGRkNN(Q,P,k,O)=
{∃qQ,∃pP|qOkNN(p,k,P,O)}.

2静态障碍物环境下的OGRkNN查询方法

本节提出的STA_OGRkNN查询方法主要分为剪枝过程和精炼过程2个步骤.首先通过剪枝可以过滤掉大量的非候选者以及对查询没有影响的障碍物,再对候选集进行精炼处理获得准确的结果集.

2.1剪枝过程

剪枝过程中首先计算查询点集Q的质心q,用质心q近似地代表查询点集整体.实际应用中,查询点集是一组邻近的对象,故可以用质心近似地代表查询点集.然后根据剪枝策略对数据点及障碍物进行剪枝,剩下的未被剪枝的数据点构成候选集,未被剪枝的障碍物构成新的障碍集.

定理4.q的RkNN只在NN(q)的前k级邻接生成点中,故NN(q)的第k级及k级以外的邻接生成点和障碍物被剪枝.

证明. 由定理3可知,q是Voronoi多边形内任意一点,设q的最近邻为p,则对q的第k+1个最近邻qk+1qk+1AG1(p)∪AG2(p)∪…∪AGk(p),(k为整数,k≥1),即q的第k+1个最近邻在p的前k级邻接生成点中.则显然有qkAG1(p)∪AG2(p)∪…∪AGk-1(p),即q的第k个最近邻在p的前k-1级邻接生成点中.故p的第k级及高于k级的邻接生成点中不可能存在qkNN.若pjAGn(p)(n>k),即pjp的高于k级的邻接生成点,则反过来同理,ppj的高于k级的邻接生成点.根据定理3,pjkNN不包括p,也就是q的RkNN不包括pj.当存在障碍物时,pjq的障碍距离一定大于等于它们之间的欧氏距离,故q的RkNN更不可能包括pj.因此,在障碍空间中,q的RkNN只在q的最近邻的前k级邻接生成点中,因此只保留q的最近邻的前k级邻接生成点及在前k级邻接区域内的障碍物.

证毕.

定理5. 设pNN(q)的第n级邻接生成点中,即pAGn(NN(q)).pq的路径上经过若干数据点pi,令单条路径上pi的总个数不大于n,将与p可视的pi总个数记作sumcount(p,q),如果sumcount(p,q)≥k,则数据点p被剪枝.

证明. 设p到查询点q的路径上经过的数据点为pi,当k=1时,则pq的路径最多只经过1个数据点pi,若ppi是可视的,则一定有diste(p,pi)<diste(p,q),即p的最近邻可能是pi而一定不是q;当k>1时,如果对p可视的pi的个数大于或等于k个,那么pk最近邻可能包括pi中的1~k个,但一定不包括q,故q应被剪枝.

证毕.

定理6. 若pSc且它的1级邻接生成点均被剪枝,则数据点p被剪枝.

证明. 设p为候选集合中的一点(pSc),ap的1级邻接生成点之一(aAG1(p)),且apq路径上经过的点.若p的1级邻接生成点均被剪枝,显然a也被剪枝,即sumcount(a,q)≥k,那么一定有sumcount(p,q)≥k+1.由于sumcount(p,q)>k,则根据定理5,p被剪枝.

证毕.

本节提出的剪枝算法的主要思想为:通过定理4~6这3个剪枝策略,剪枝掉大量的非候选者以及对查询无影响的障碍物,获得候选集合Sc.这一过程中首先以数据点集P为生成点生成Voronoi图.然后计算查询点集Q的质心q,并用质心q近似地代表查询点集整体.再根据定理4,将NN(q)的前k级邻接生成点放入候选集合Sc中,高于k级的邻接生成点不可能是q的RkNN,因此被剪枝,进而获得初步的候选集,同时获得剪枝后的新障碍集.根据定理5,6对候选集中的数据点进行判断,满足条件的数据点被剪枝,剩下的未被剪枝的数据点构成更精确的候选集.基于以上讨论,进一步给出剪枝算法,如算法1所示:

算法1.STA_OGRkNN_Filter(Q,P,O,k).

输入:查询点集Q、数据点集P、障碍物集Ok值;

输出:候选集Sc、剪枝后的障碍集Onew.

Create_Voronoi(P);*以P中数据点为生成点创建Voronoi图*

Sc←∅;*初始化候选集Sc为空集*

oO

count←0;sumcount←0;

qCalculate_Centroid(Q);*计算查询点集Q的质心q*

ifqVP(p) then

NN(q)←p*q的最近邻是数据点p*

fori=1 tokdo

ScSc+AGi(p);*将p的第i级邻接生成点集加入Sc中*

endfor

endif

for eachp′∈Scdo

ifVP(p′)∩o≠∅ then

OnewOnew+o*剪枝障碍物*

endif

ifcountnthen

for eachpiPath(p′,q)*pip′到q路径上的点*

if [p′,pi]∩Onew=∅ do

sumcountsumcount+1;

endif

ifsumcountkthen

ScSc-p′;*定理5*

endif

endfor

endif

endfor

for eachp″∈Scdo

ifAG1(p″)∩Sc=∅ then

ScSc-p″;*定理6*

endif

endfor

returnScOnew.

2.2精炼过程

在精炼过程中,首先根据定理7对候选集Sc中的候选点进行精炼处理,得到更精确的候选集;再根据OGRkNN的定义对候选集中的点逐一排除,获得准确的结果集.

定理7. 当pScp对查询点q是可视的,则以p点为圆心、以diste(p,q)为半径画圆,将该判定圆内p可视的数据点的个数记作count_points,若count_pointsk,则数据点p被剪枝.当p对查询点q是不可视时,以p点为圆心、以distb(p,q)为半径画圆,同样,若count_pointsk,则数据点p被剪枝.

证明. 分2种情况:

1) 当pScp对查询点q是可视的时候,如图1所示.以p点为圆心、以diste(p,q)为半径画圆,则在判定圆内的数据点有{p1,p2,p3,p4,p5,p6,p7},其中{p1,p3,p6}对p是不可视的,{p2,p4,p5,p7}对p是可视的,则count_points=4.当k=4时,显然p的4NN是{p2,p4,p5,p7},而不包括q.当k<4时,由于数据点{p2,p4,p5,p7}到p的距离均小于qp的距离,故pkNN是{p2,p4,p5,p7}中的k个,一定不包括q,故q的RkNN一定不是数据点p,因此p被剪枝.

Fig. 1 Proof 1 of theorem 7
图1 定理7的证明情况1

2) 当pScp对查询点q是不可视的时候,如图2所示.以p点为圆心、以distb(p,q)为半径画圆,则在判定圆内的数据点有{p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13},其中{p1,p2,p4,p6,p12,p13}对p是不可视的,{p3,p5,p7,p8,p9,p10,p11}对p是可视的,则count_points=7.当k=7时,显然p的7NN是{p3,p5,p7,p8,p9,p10,p11},而不包括q.当k<7时,由于数据点{p3,p5,p7,p8,p9,p10,p11}到p的距离均小于qp的距离,故pkNN是{p3,p5,p7,p8,p9,p10,p11}中的k个,必不包括q,故qRkNN不是数据点p,因此p被剪枝.

证毕.

Fig. 2 Proof 2 of theorem 7
图2 定理7的证明情况2

本节提出的精炼算法的主要思想为:根据定理7对候选集Sc中的点进行判断,满足条件的候选点p被剪枝.获得更精确的候选集后再根据OGRkNN的定义分别求出候选集中点p到查询点q的障碍距离distb(p,q)以及p到它的第k个最近邻pk的障碍距离distb(p,pk).若distb(p,q)>distb(p,pk),说明候选点p不是q的障碍组反k最近邻,因此被排除.最后剩下的候选点构成正确的结果集.

下面给出精炼算法,如算法2所示.

算法2.STA_OGRkNN(Q,P,O,k).

输入:查询点集Q、数据点集P、障碍物集Ok值;

输出:静态障碍物环境下的查询结果集SR.

count_points←0;

oOnew

ScSTA_OGRkNN_Filter(Q,P,O,k);*调用算法1得到初步过滤后的候选集*

for eachpScdo

if [p,q]∩o=∅ then

CRCircle(p,diste(p,q));

else

CRCircle(p,distb(p,q));

endif

ifpointCRand [point,p]∩o=∅ then

count_pointscount_points+1;

ifcount_pointskthen

*定理7*

endif

endif

endfor

for eachpindo

kNN(p)←{p1,p2,…,pk};

if[p,pi]∩o=∅ then

distb(p,pi)←diste(p,pi);

endif

fori=1 tokdo

ifdistb(p,pi)≥distthen

distdistb(p,pi);

pkpi*p的第k个最近邻为pk*

endif

endfor

ifdistb(p,q)>distb(p,pk) then

endif

endfor

returnSR.

3动态障碍物环境下的OGRkNN查询方法

由于现实生活中的障碍物不是静止不变的,所以本节进一步给出动态障碍物环境下的OGRkNN查询方法.

3.1障碍物动态增加情况下的OGRkNN查询方法

根据新增加的障碍物所在的位置,分2种情况讨论:1)新增加的障碍物对算法2的查询结果没有影响;2)有影响.根据定理4,q的最近邻的第k级及以外的邻接生成点和障碍物被剪枝,故将NN(q)的前k级邻接区域称为影响区域,用Affected_Area表示.设新增加的障碍物为o′,当o′∉Affected_Area时,由于在过滤过程中根据定理4会对影响区域以外的数据点以及障碍物进行剪枝,此时o′会一同被剪枝,所以o′对算法2的查询结果无影响.当o′∈Affected_Area时,设增加o′之前q的RkNN为{pi},若o′对[q,pi]造成阻断,则distb(q,pi)=diste(q,o′)+diste(o′,pi),显然有distb(q,pi)>diste(q,pi),故pi不再是q的RkNN;若o′对[q,pi]没有造成阻断,则o′对查询结果无影响.

基于以上讨论可得出判定规则1和判定规则2.

判定规则1. 设新增加的障碍物为o′,若o′∉Affected_Area,则对算法2的查询结果没有影响;若o′∈Affected_Area,则需要对算法2的查询结果集进行再判断.

判定规则2. 障碍物动态增加情况下的OGRkNN查询结果集一定是静态障碍物环境下的OGRkNN查询结果的子集.

根据判定规则1和判定规则2,本节提出的障碍物动态增加情况下的OGRkNN查询方法的主要思想为:首先判断新增加的障碍物的位置,然后计算受影响区域范围.根据判定规则1和判定规则2进行判断,若新增障碍物不在影响区域内,则返回静态障碍物环境下的查询结果;若新增障碍物在影响区域内,则对结果集中的数据点进行判断.若pq的障碍距离大于p到它的第k个最近邻的障碍距离,则说明在新增加障碍物之后p不再是q的反k最近邻,故p被删除,最后剩下的数据点就是障碍物动态增加情况下的查询结果.

基于以上讨论,进一步给出障碍物动态增加情况下的查询算法,如算法3所示.

算法3.DYN_ADD_OGRkNN(Q,P,O,k,o′).

输入:查询点集Q、数据点集P、障碍物集Ok值、新增加的障碍物o′;

输出:障碍物动态增加情况下的查询结果集Snew.

O′←Oo′;*O′为新增加障碍物之后的障碍集*

Affected_Area←∅;*受影响区域初始化*

SRSTA_OGRkNN(Q,P,O,k);

Judge_Position(o′);*判断新增加的障碍物的位置*

Af*受影响区域范围*

ifo′∩Affected_Area=∅ then*新增障碍物不在影响区域内*

SnewSR

else*新增障碍物在影响区域内*

for eachp′ inSRdo

if[p′,q]∩O′=∅ then

distb(p′,q)←diste(p′,q);

endif

SRSR-p′;

endif

endfor

SnewSR

endif

returnSnew.

3.2障碍物动态减少情况下的OGRkNN查询方法

根据减少的障碍物所在的位置,分2种情况讨论:1)新增加的障碍物对算法2的查询结果没有影响;2)有影响.设减少的障碍物为o′,当o′∉Affected_Area时,由于在过滤过程中根据定理4会对影响区域以外的数据点以及障碍物进行剪枝,此时o′会一同被剪枝,所以o′对算法2的查询结果无影响;当o′∈Affected_Area时,设减少o′之前q的RkNN为{pi},若[q,pi]原来是阻断的,减少o′之后变成可视的,则qpi之间的距离由障碍距离变成了欧氏距离,则有diste(q,pi)<distb(q,pi),故pi有可能变成是q的RkNN.若减少o′,[q,pi]仍是阻断的,则o′对查询结果无影响.

基于以上讨论给出判定规则3.

判定规则3. 设减少的障碍物为o′,若o′∉Affected_Area,则对算法2的查询结果没有影响;若o′∈Affected_Area,则需将障碍集去除o′后再进行查询.

基于判定规则3,本节提出的障碍物动态减少情况下的OGRkNN查询算法的主要思想为:首先判断减少的障碍物所在的位置,然后计算受影响区域范围,根据判定规则3,将减少的障碍物是否在影响区域内分为2种情况.若不在影响区域内,说明减少的障碍物对算法2的查询结果不构成影响;若在影响区域内,则将算法2中的障碍集替换成减少障碍物之后的新障碍集,最后通过调用算法2得到障碍物动态减少情况下的查询结果.

基于以上讨论,进一步给出障碍物动态减少情况下的查询算法,如算法4所示.

算法4.DYN_DEL_OGRkNN(Q,P,O,k,o′).

输入: 查询点集Q、数据点集P、障碍物集Ok值、减少的障碍物o′;

输出: 障碍物动态减少时的查询结果集Snew.

O′←O-o′;*O′为减少障碍物之后的新障碍集*

Affected_Area←∅;*受影响区域初始化*

Judge_Position(o′);*判断减少的障碍物的位置*

Af*确定受影响区域范围*

ifo′∩Affected_Area=∅ then*减少的障碍物不在影响区域内*

SRSTA_OGRkNN(Q,P,O,k);

else*减少的障碍物在影响区域内*

SRSTA_OGRkNN(Q,P,O′,k);*更新障碍集后再进行查询*

endif

SnewSR

returnSnew.

3.3障碍物动态移动情况下的OGRkNN查询方法

本节主要研究的是障碍物动态移动情况下的OGRkNN查询方法.如图3所示,虚线箭头指向的是移动方向,原障碍集为{o1,o2,o3,obef},obef为发生移动的障碍物.在obef移动之前,q的R6NN包括p而不包括p12;障碍物obef移动之后,障碍集变为{o1,o2,o3,oaft},oaft为移动之后的障碍物,q的R6NN包括p12而不包括p.在障碍物移动前后的OGRkNN查询结果发生变化,故障碍物动态移动情况下的OGRkNN查询方法具有较高的研究价值.

Fig. 3 Example about dynamically moving obstacles
图3 障碍物动态移动示例

为了判断移动的障碍物对查询结果是否产生影响,首先判断发生移动的障碍物移动前后所在的位置,分别记为obefoaft;然后根据obefoaft的位置是否在影响区域内分为4种情况:

1) 障碍物在影响区域外发生移动,即obefoaft均在Affected_Area外.例如图4中o3移动到o4.

2) 障碍物在影响区域内发生移动,即obefoaft均在Affected_Area内.例如图4中o1移动到o2.

3) 障碍物从影响区域内移动到影响区域外,即obefAffected_Area内,oaftAffected_Area外.例如图4中o2移动到o3.

4) 障碍物从影响区域外移动到影响区域内,即obefAffected_Area外,oaftAffected_Area内.例如图4中o4移动到o1.

Fig. 4 Example of obstacle movement
图4 障碍物移动的示例

情况1中的obefoaft均在Affected_Area外,根据定理4会对Affected_Area以外的数据点以及障碍物进行剪枝,此时obefoaft会一同被剪枝,所以情况1对STA_OGRkNN查询结果无影响.情况2中的obefoaft均在Affected_Area内,设障碍物移动前q的RkNN为{pi},pm,pn∈{pi},若[q,pm]原来是阻断的,[q,pn]是可视的,障碍物移动之后[q,pm]变成可视的,[q,pn]变成阻断的,则pm有可能不再是q的RkNN,而pn有可能变成q的RkNN,说明障碍物移动后会对查询结果产生影响.若障碍物的移动对[q,pi]的可视性不产生影响,则对查询结果无影响.由于情况2的不确定性,故需更新障碍集后再进行查询.情况3中obefAffected_Area内,同情况2一样对查询结果可能有影响,oaftAffected_Area外,对查询结果无影响,故也需更新障碍集.同理,情况4需要更新障碍集再进行查询.

基于以上4种情况的讨论给出判定规则4.

判定规则4. 情况1中的障碍物发生移动对查询结果不产生影响;情况2中obefoaft均在Affected_Area内,需要将障碍集更新为O-obef+oaft;情况3中obefAffected_Area内,需要将障碍集更新为O-obef;情况4中oaftAffected_Area内,需要将障碍集更新为O+oaft.

基于判定规则4,本节提出的障碍物动态移动情况下的OGRkNN查询算法的主要思想为:首先判断发生移动的障碍物移动前后所在的位置;然后计算受影响区域范围;再根据判定规则4分别对4种情况进行处理;最后得到障碍物移动情况下的OGRkNN查询结果.基于以上讨论,进一步给出障碍物动态移动情况下的查询算法,如算法5所示.

算法5.DYN_MOVE_OGRkNN(Q,P,O,k,obef,oaft).

输入:查询点集Q、数据点集P、原障碍集Ok值、移动前的障碍物obef、移动后的障碍物oaft

输出:障碍物动态移动时的查询结果集Snew.

obefO;*移动前的障碍物属于原障碍集O

Affected_Area←∅;*受影响区域初始化*

Judge_Position(obef);*判断障碍物移动前的位置*

Judge_Position(oaft);*判断障碍物移动后的位置*

ifobef,oaftAffected_Areathen*情况1*

SRSTA_OGRkNN(Q,P,O,k);

else ifobef,oaftAffected_Areathen*情况2)*

O′←O-obef

O′←O′+oaft

SRSTA_OGRkNN(Q,P,O′,k);

else ifobefAffected_AreaandoaftAffected_Areathen*情况3*

O′←O-obef

SRSTA_OGRkNN(Q,P,O′,k);

elseobefAffected_AreaandoaftAffected_Areathen*情况4*

O′←O+oaft

SRSTA_OGRkNN(Q,P,O′,k);

endif

SnewSR

returnSnew.

4实验比较与分析

本节通过实验对所提算法进行性能分析.由于已有的研究成果无法直接处理障碍空间中的组反k最近邻查询问题,故我们对文献[15-16]提出的障碍反k最近邻查询算法采用反复调用的方式应用于一组查询点中,形成对比算法.我们将反复调用形成的对比算法分别称作GRkNNobs算法和GORkNN算法.2个对比算法的主要思想为:将已有的针对一个查询对象的障碍反k最近邻查询算法应用到一组查询对象的情况中,也就是采用反复调用的方式对一组对象中的每个对象成员进行障碍反k最近邻查询,所有查询结果的并集就是障碍组反k最近邻查询的结果.

实验平台配置如下:2.0 GHz CPU,4 GB内存,500 GB硬盘,Windows 7操作系统上用Microsoft Visual Studio 2005实现.本文使用的数据集是从美国加利福尼亚州的道路网络中的数据对象集抽取出来的80 000个节点对象和5 000个线段对象.查询点集Q是在节点对象集中随机抽出的n个点的集合.实验测试的指标为运行时间,并取执行100次查询的平均值.实验首先对STA_OGRkNN算法进行测试,分别测试k值、查询点数量、数据点集大小、障碍物个数对于运行时间的影响,然后对动态障碍物环境中的查询方法的3个算法分别进行测试.

Fig. 5 Effect of k on runtime
图5 k值对CPU时间的影响

如图5所示,首先分析k值对运行时间的影响.实验规模为80 000,查询点的数量为10,障碍物的数量为1 000.图5给出了3个算法的运行时间随着k值变化的对比结果.随着k值的不断变大,算法的CPU时间均呈上升趋势.由于GRkNNobs算法和GORkNN算法需要对每一个查询点计算它的反k最近邻,这样就造成了搜索区域的频繁重叠情况,k值越大,搜索区域重叠的面积越大,从而花费的查询时间越多.本文提出的STA_OGRkNN算法分别对查询点集和数据点集进行了预处理,缩小了查询范围,同时利用Voronoi图的特性进行高效地剪枝和精炼,当k值越大时,该算法的优势越明显.

图6给出了查询点数量对运行时间的影响.实验设定k值为10,数据点集的规模设置为80 000,障碍物的数量为1 000.从图6中可以看出GRkNNobs算法的运行时间上升趋势明显,其次为GORkNN算法,因为这2个算法都需要对每一个查询点计算它的障碍反k最近邻,当查询点数量增长时,算法所用的查询时间也会大幅增长;而STA_OGRkNN算法的查询时间的上升趋势较为平缓,因为算法中有对查询点集的处理过程,所以当查询点数量呈倍数增长时,对算法的性能影响不大.

Fig. 6 Effect of query points number on runtime
图6 查询点数量对查询时间的影响

Fig. 7 Effect of dataset scale on runtime
图7 数据点集规模对CPU时间的影响

图7给出了数据点集规模对算法运行时间的影响.实验设定k值为10,查询点的数量为10,障碍物的数量为1 000.随着数据点集规模的变大,3个算法的运行时间均呈上升趋势.GRkNNobs算法和GORkNN算法在计算一组查询点中每个查询点的障碍反k最近邻时,消耗大量查询时间;而STA_OGRkNN算法首先对查询点集进行优化处理,避免了搜索区域频繁重叠的现象,然后利用Voronoi图的邻接特性在剪枝阶段和精炼阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,故该算法随着数据集的增大所花费的运行时间较少.

接下来分析障碍物的个数对运行时间的影响,实验设定k=10,查询点的数量为10,数据点集的规模为80 000.如图8所示,随着障碍物的数量增加,运行时间越长.GRkNNobs算法和GORkNN算法需要计算每一个查询点的障碍RkNN,这一过程中计算障碍距离的时间花费较大;而STA_OGRkNN算法在剪枝阶段对没有影响的障碍物进行剪枝,故随着障碍物数量的增加,该算法的运行时间增加幅度缓慢.

Fig. 8 Effect of obstacal number on runtime
图8 障碍物的个数对CPU时间的影响

最后测试动态障碍物环境的OGRkNN查询方法的性能.对GRkNNobs算法和GORkNN算法采取重新调用的方式应用于动态障碍物环境中,形成对比算法.表1反映了本文提出的DYN_ADD_OGRkNN算法与对比算法在障碍物动态增加时的性能对比.实验设定k=10,查询点的数量为10,数据点集的规模为80 000.测试的指标为查询时间,并取执行1 000次查询的平均值.为了方便研究,以每次增加1个障碍物的方式进行测试.如表1所示,当障碍物数量从2 000变成3 000时,DYN_ADD_OGRkNN算法的平均查询时间变化不大,而GRkNNobs算法和GORkNN算法的查询时间几乎呈倍数增长.

表2显示的是当障碍物动态减少时DYN_DEL_OGRkNN算法与对比算法的查询时间比较.对GRkNNobs算法和GORkNN算法采用重新调用的方式应用于障碍物动态减少环境中,此时对比算法的主要思想为:使用减少障碍物之后的新障碍集作为参数,重新执行一遍算法得出结果.如表2所示,GRkNNobs和GORkNN算法的查询时间远远多于DYN_DEL_OGRkNN算法,这是由于2个对比算法只是单纯地重复执行一次;而DYN_DEL_OGRkNN算法会判断减少的障碍物所在的位置,再分别采取不同的方法,这样就避免了很多冗余计算.

Table1PerformanceComparisonBetweenDYN_ADD_OGRkNNandOtherAlgorithms

表1DYN_ADD_OGRkNN与对比算法性能比较

AlgorithmsObstacal NumberQuery Time∕sDYN_ADD_OGRkNN20000.882GORkNN20001.191GRkNNobs20001.338DYN_ADD_OGRkNN30000.963GORkNN30002.257GRkNNobs30002.642

Table2PerformanceComparisonBetweenDYN_DEL_OGRkNNandOtherAlgorithms

表2DYN_DEL_OGRkNN与对比算法性能比较

AlgorithmsObstacal NumberQuery Time∕sDYN_DEL_OGRkNN20000.831GORkNN20001.106GRkNNobs20001.295DYN_DEL_OGRkNN10000.993GORkNN10002.384GRkNNobs10002.615

表3显示的是当障碍物动态移动时DYN_MOVE_OGRkNN算法与对比算法的平均查询时间比较情况.对GRkNNobs算法和GORkNN算法采用重新调用的方式应用于障碍物动态移动环境中.

Table3PerformanceComparisonBetweenDYN_MOVE_OGRkNNandOtherAlgorithms

表3DYN_MOVE_OGRkNN与对比算法性能比较

AlgorithmsOld Obstacal Set Query Time∕sDYN_MOVE_OGRkNNO0.863GORkNNO1.158GRkNNobsO1.325DYN_MOVE_OGRkNNO'0.925GORkNNO'2.363GRkNNobsO'2.752

如表3所示,当障碍物发生移动时,GRkNNobs和GORkNN算法的执行时间远多于DYN_MOVE_OGRkNN算法.

5结束语

本文基于Voronoi图的邻接特性提出了处理障碍空间中组反k最近邻查询的方法,解决了针对静态障碍物环境以及动态障碍物环境下的组反k最近邻查询的问题.给出OGRkNN查询的定义和实现算法.解决该问题的难点在于如何快速准确地获得查询结果,为此提出高效的剪枝规则.在剪枝阶段利用剪枝策略对数据集进行剪枝,过滤掉大量的非候选者,快速地缩小查询范围.在精炼阶段对候选集进行精炼处理提高了算法的准确性.在STA_OGRkNN查询基础上给出障碍物动态增加情况下的OGRkNN查询方法、障碍物动态减少情况下的OGRkNN查询方法以及障碍物动态移动情况下的OGRkNN查询方法.理论研究和实验表明,所提算法具有较好的性能.未来的研究重点主要集中在障碍空间中针对不确定数据的组反k最近邻查询方面.

参考文献

[1]Zhang Liping, Zhao Jiqiao, Li Song, et al. Research on methods of construction of Voronoi diagram and nearest neighbor query in constrained regions[J]. Computer Science, 2014, 41(9): 220-224 (in Chinese)(张丽平, 赵纪桥, 李松. Voronoi图的构建与受限区域内的最近邻查询方法研究[J]. 计算机科学, 2014, 41(9): 220-224)>

[2]Tao Yulei, Yiu M L, Mamoulis N. Reverse nearest neighbor search in metric spaces[J]. IEEE Trans on Knowledge Data Engineering, 2006, 18(9): 1239-1252>

[3]Papadias D, Shen Q, Tao Y, et al. Group nearest neighbor queries[C]Proc of the 20th Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Socity, 2004: 301-312>

[4]Samna N, Eqemen T, Zhang Rui. Incremental evaluation of visible nearest neighbor queries[J]. IEEE Trans on Knowledge Engineering, 2010, 22(4): 665-681>

[5]Cao Y, Zheng B, Chen G, et al. Visible reversek-nearest neighbor query processing in spatial databases[J]. IEEE Trans on Knowledge Engineering, 2009, 21(9): 1314-1327>

[6]Zhang Y, Lin X, Zhu G, et al. Efficient rank basedkNN query processing over uncertain data[C]Proc of the 26th Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2010: 28-39>

[7]Li Song, Zhang Liping, Hao Zhongxiao. Strong neighborhood pair query in dynamic dataset[J]. Journal of Computer Research and Development, 2015, 52(3): 749- 759 (in Chinese)(李松, 张丽平, 郝忠孝. 动态数据集环境下的强邻近对查询[J]. 计算机研究与发展, 2015, 52(3): 749-759)>

[8]Cheema M A, Zhang Wenjie, Lin Xuemin, et al. Continuous reverseknearest neighbors queries in euclidean space and in spatial networks[J]. The VLDB Journal, 2012, 21(1): 69-95>

[9]Liu Zhang, Wang Chaokun, Wang Jianmin. Aggregate nearest neighbor queries in uncertain graphs[J]. World Wide Web, 2014, 17 (1): 161-188>

[10]Hicham G E, Mohamed F M, Walid G A. Continuous aggregate nearest neighbor queries[J]. GeoInformatica, 2013, 17(1): 63-95>

[11]Wang Li, Qin Xiaolin, Shi Changyue. Bichromatic reverse nearest neighbor queries in indoor space[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(3): 310-320 (in Chinese)(王丽, 秦小麟, 施常月. 室内双色数据集上的反向最近邻查询[J]. 计算机科学与探索, 2015, 9(3): 310-320)>

[12]Tanzima H, Lars K, Zhang Rui. Countering overlapping rectangle privacy attack for movingkNN queries[J]. Information Systems, 2013, 38(3): 430-453>

[13]Lee K W, Choi D W, Chung C W. Direction-aware bichromatic reverseknearest neighbor query processing in spatial databases[J]. Journal of Intelligent Information Systems, 2014, 43(2): 349-377>

[14]Song Xiaoyu, Yu Chengcheng, Sun Huanliang, et al. GRkNN: Group reversek-nearest-neighbor query in spatial databases[J]. Chinese Journal of Computers, 2010, 33(12): 2229-2238 (in Chinese)(宋晓宇, 于程程, 孙焕良, 等. GRkNN: 空间数据库中组反k最近邻查询[J]. 计算机学报, 2010, 33(12): 2229-2238)>

[15]Yu Xiaonan, Gu Yu, Zhang Tiancheng, et al. A method for reversek-nearest-neighbor queries in obstructed spaces[J]. Chinese Journal of Computers, 2011, 34(10): 1917-1925 (in Chinese)(于晓楠, 谷峪, 张天成, 等. 一种障碍空间中的反k最近邻查询方法[J]. 计算机学报, 2011, 34(10): 1917-1925)>

[16] GaoYunjun, Liu Qing, Miao Xiaoye, et al. Reversek-nearest neighbor search in the presence of obstacles[J]. Information Sciences, 2016, 330: 274-292>

[17]Yang Zexue, Hao Zhongxiao. Group obstacal nearest neighbor query in spatial database[J]. Journal of Computer Research and Development, 2013, 50(11): 2455-2462 (in Chinese)(杨泽雪, 郝忠孝. 空间数据库中的组障碍最近邻查询研究[J]. 计算机研究与发展, 2013, 50(11): 2455-2462)

[18]Hao Zhongxiao. Spatial Databases Theoretical Basis[M]. Beijing: Science Press, 2013 (in Chinese)(郝忠孝. 空间数据库理论基础[M]. 北京: 科学出版社, 2013)>

[19]Zhang J, Papadias D, Mouratidis K, et al. Spatial queries in the presence of obstacles[C]Proc of the 9th Int Conf on Extending Database Technology. Berlin: Springer, 2004: 366-384

Voronoi-BasedGroupReversekNearestNeighborQueryinObstructedSpace

Zhang Liping1, Liu Lei1, Hao Xiaohong1, Li Song1, Hao Zhongxiao1,2

1(SchoolofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080)2(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)

AbstractIn order to solve the problem that the existing methods can not deal with the group reverseknearest neighbor (GRkNN) query in obstructed space, the group reverseknearest neighbor query method (OGRkNN) in obstructed space based on Voronoi diagram is put forward. The method finds data points that take any point in the query objects set as one of their obstacleknearest neighbors. In the practical application, OGRkNN query can be used to evaluate the influence of a group of query objects. According to the changes of the obstacle set, the OGRkNN query in static obstacle environment (STA_OGRkNN query) and the OGRkNN query in dynamic obstacle environment (DYN_OGRkNN query) are given. The STA_OGRkNN query method greatly reduces the number of non-candidates by the properties of Voronoi diagram in pruning stage, and reduces the searching ranges quickly, which improves query efficiency. It also improves the accuracy of the algorithm in refining stage. Then three DYN_OGRkNN query algorithms are given. They are the OGRkNN query algorithm under the condition of dynamically increasing obstacles, the OGRkNN query algorithm under the condition of dynamically reducing obstacles and the OGRkNN query algorithm under the condition of dynamically moving obstacles. Theoretical study and experiments show that the proposed algorithms have extremely high efficiency.

KeywordsVoronoi diagram; group reverseknearest neighbor (GRkNN); obstructed space; spatial database; dynamic query

This work was supported by the National Natural Science Foundation of China (61370084), the Natural Science Foundation of Heilongjiang Province (F201302), and the Science and Technology Research Project of Heilongjiang Provincial Education Department (12531z004).

基金项目国家自然科学基金项目(61370084);黑龙江省自然科学基金项目(F201302);黑龙江省教育厅科学技术研究项目(12531z004)

修回日期:20161010

收稿日期20151222;

中图法分类号TP311.13

ZhangLiping, born in 1976. Master. Associate professor in the School of Computer Science and Technology, Harbin University of Science and Technology. Member of CCF. Her main research interests include the spatial and spatio-temporal database, information data security.

LiuLei, born in 1990. Master. Her main research interest is the spatial database.

HaoXiaohong, born in 1969. Master. Her main research interest is the spatial database.

LiSong, born in 1977. PhD. Associate professor in the School of Computer Science and Technology, Harbin University of Science and Technology. His main research interests include the spatial and spatio-temporal database, data mining, information data security.

HaoZhongxiao, born in 1940. Professor and PhD supervisor in the Harbin Institute of Technology and Harbin University of Science and Technology. His main research interests include relational database, null database, acyclic database, active database, spatial database and temporal database.