張麗平 劉 蕾 郝曉紅 李 松 郝忠孝,2

1(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080)

2 (哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)

(zhanglptg@163.com)

隨著基于位置服務(wù)技術(shù)的廣泛應(yīng)用，空間數(shù)據(jù)庫(kù)中的最近鄰(nearest neighbor, NN[1])查詢及它的變體查詢成為熱點(diǎn)問題.近年來，最近鄰查詢的研究進(jìn)一步拓展到反向最近鄰查詢[2]、組最近鄰查詢[3]、可視最近鄰查詢[4]、可視反向k最近鄰查詢[5]、不確定數(shù)據(jù)集中的k最近鄰查詢[6]、強(qiáng)鄰近對(duì)查詢[7]、連續(xù)反k最近鄰查詢[8]、聚集最近鄰查詢[9-10]、雙色數(shù)據(jù)集上的反向最近鄰查詢[11]、移動(dòng)k最近鄰查詢[12]等方面.所取得的成果解決了最近鄰查詢領(lǐng)域的一些重要問題.

反k最近鄰(reverseknearest neighbor, RkNN[8])查詢是空間數(shù)據(jù)庫(kù)中的重要的查詢之一，在空間決策支持、資源分配和數(shù)據(jù)挖掘方面有著廣泛的應(yīng)用.RkNN查詢獲得將查詢對(duì)象作為k最近鄰的數(shù)據(jù)對(duì)象集合，可以反映出該查詢對(duì)象對(duì)哪些空間對(duì)象影響較大，所以一般用來評(píng)估查詢對(duì)象的影響力.例如，在一家商場(chǎng)的選址工作中，需要評(píng)估該商場(chǎng)對(duì)附近哪些人群有影響力，該商場(chǎng)所吸引的顧客群就是RkNN查詢所要找的影響集.由于此類查詢可以支持高級(jí)的分析和預(yù)測(cè)應(yīng)用，因此在實(shí)際應(yīng)用中已經(jīng)變得越來越重要.對(duì)于RkNN查詢，文獻(xiàn)[13]提出了一種新的雙色反向最近鄰查詢，該查詢利用基于網(wǎng)格的方法對(duì)空間對(duì)象進(jìn)行聚類，同時(shí)利用B+樹進(jìn)行索引方向角，來達(dá)到有方向性的查詢.根據(jù)實(shí)際需求，有時(shí)需要對(duì)一個(gè)商業(yè)區(qū)進(jìn)行評(píng)估影響力，即查詢一組查詢對(duì)象的RkNN結(jié)果，因此宋曉宇等人提出了組反k最近鄰(group reverseknearest neighbor, GRkNN[14])查詢.該查詢方法通過計(jì)算查詢對(duì)象的最小覆蓋圓，將圓中的對(duì)象作為一個(gè)整體來計(jì)算該組查詢點(diǎn)RkNN的搜索區(qū)域.

以上查詢均是在理想的歐氏空間中，但是現(xiàn)實(shí)空間中不可避免會(huì)有一些地理?xiàng)l件的限制(例如建筑、河流、山等)，因此2個(gè)對(duì)象之間的最短距離必須考慮障礙物的因素.對(duì)于障礙空間中的查詢，于曉楠等人[15]提出了一種障礙空間中的反k最近鄰查詢方法，該方法利用障礙Voronoi圖的性質(zhì)設(shè)計(jì)了高效的剪枝策略，可以大幅度地減少搜索障礙反k最近鄰對(duì)象的時(shí)間和空間.Gao等人[16]引入一種新的邊界區(qū)域的概念，可以有效地處理障礙反k最近鄰查詢.楊澤雪和郝忠孝[17]提出空間數(shù)據(jù)庫(kù)中的組障礙最近鄰查詢.在障礙空間中，現(xiàn)有的空間查詢研究成果只涉及到障礙最近鄰查詢、障礙反向最近鄰查詢、障礙組最近鄰查詢、障礙反k最近鄰查詢等方面，并沒有涉及障礙組反k最近鄰查詢問題.因此，障礙空間中的組反k最近鄰查詢問題是一個(gè)新的需要解決的問題.

為了解決障礙空間中的組反k最近鄰查詢問題，基于Voronoi圖，本文提出了障礙空間中的GRkNN查詢方法(OGRkNN查詢方法).該方法獲得的結(jié)果集是將這組查詢點(diǎn)中任意一點(diǎn)作為障礙k最近鄰的數(shù)據(jù)點(diǎn)集合.查詢中將GRkNN查詢中的歐氏距離度量改為障礙距離度量.在實(shí)際應(yīng)用中可以用來評(píng)估一組查詢對(duì)象的影響力.本文依據(jù)障礙物集合是否發(fā)生變化分2種情況討論OGRkNN查詢方法:1)靜態(tài)障礙物環(huán)境下的OGRkNN查詢方法(簡(jiǎn)稱STA_OGRkNN查詢方法);2)動(dòng)態(tài)障礙物環(huán)境下的OGRkNN查詢方法(簡(jiǎn)稱DYN_OGRkNN查詢方法).其中STA_OGRkNN查詢方法包括2個(gè)過程：剪枝過程和精煉過程.利用Voronoi圖的鄰接特性可以在剪枝階段和精煉階段有效地過濾掉大量的非候選者，快速地縮小查詢范圍，提高整個(gè)算法的查詢效率.進(jìn)一步給出了3種情況下的DYN_OGRkNN查詢方法.

1 定義與定理

定義1. Voronoi圖[18].給定一組生成點(diǎn)P={p1,p2,…,pn}，其中2

定義2. Voronoi圖的k級(jí)鄰接生成點(diǎn)[18].給定一組生成點(diǎn)P={p1,p2,…,pn}，生成Voronoi圖，其中2

1) 1級(jí)鄰接生成點(diǎn)

AG1(pi)={pj|VP(pi)和VP(pj)有公共邊}；

2)k(k≥2)級(jí)鄰接生成點(diǎn)

AGk(pi)={pj|VP(p)和VP(pj)有公共邊，p∈AGk-1(pi)}.

定理1[18]. 點(diǎn)q為Voronoi單元VP(pi)內(nèi)任一點(diǎn)，pk+1∈AGk+1(pi).那么必存在一點(diǎn)pk∈AGk(pi)使得dist(q,pk)≤dist(q,pk+1).

定理2[18]. 對(duì)于Voronoi多邊形VP(pi)內(nèi)任一點(diǎn)q，q到pi的k級(jí)鄰接生成點(diǎn)的最小距離小于到任何pi的k+1級(jí)鄰接生成點(diǎn)的距離(k為整數(shù)，k≥1).

定理3[18]. 對(duì)于Voronoi多邊形VP(pi)內(nèi)任一點(diǎn)q，q的第k+1個(gè)最近鄰qk+1有qk+1∈AG1(p)∪AG2(p)∪…∪AGk(p)(k為整數(shù)，k≥1)，即q的第k+1個(gè)最近鄰在q的最近鄰前k級(jí)鄰接生成點(diǎn)中.

基于點(diǎn)與點(diǎn)的可視性[18]﹑點(diǎn)與點(diǎn)的障礙距離[19]和組反k最近鄰查詢[14]的基本概念，本文進(jìn)一步提出了障礙組反k最近鄰查詢的定義如定義3所示.

定義3. 障礙組反k最近鄰查詢.在障礙空間中，給定一組查詢點(diǎn)集Q={q1,q2,…,qn}和一個(gè)數(shù)據(jù)點(diǎn)集P={p1,p2,…,pm}，在數(shù)據(jù)集P中查詢那些k個(gè)最近鄰中包含Q中任意一個(gè)查詢點(diǎn)q的空間數(shù)據(jù)點(diǎn)，具體定義形式為

OGRkNN(Q,P,k,O)=
{?q∈Q,?p∈P|q∈OkNN(p,k,P,O)}.

2 靜態(tài)障礙物環(huán)境下的OGRkNN查詢方法

本節(jié)提出的STA_OGRkNN查詢方法主要分為剪枝過程和精煉過程2個(gè)步驟.首先通過剪枝可以過濾掉大量的非候選者以及對(duì)查詢沒有影響的障礙物，再對(duì)候選集進(jìn)行精煉處理獲得準(zhǔn)確的結(jié)果集.

2.1 剪枝過程

剪枝過程中首先計(jì)算查詢點(diǎn)集Q的質(zhì)心q，用質(zhì)心q近似地代表查詢點(diǎn)集整體.實(shí)際應(yīng)用中，查詢點(diǎn)集是一組鄰近的對(duì)象，故可以用質(zhì)心近似地代表查詢點(diǎn)集.然后根據(jù)剪枝策略對(duì)數(shù)據(jù)點(diǎn)及障礙物進(jìn)行剪枝，剩下的未被剪枝的數(shù)據(jù)點(diǎn)構(gòu)成候選集，未被剪枝的障礙物構(gòu)成新的障礙集.

定理4.q的RkNN只在NN(q)的前k級(jí)鄰接生成點(diǎn)中，故NN(q)的第k級(jí)及k級(jí)以外的鄰接生成點(diǎn)和障礙物被剪枝.

證明. 由定理3可知，q是Voronoi多邊形內(nèi)任意一點(diǎn)，設(shè)q的最近鄰為p，則對(duì)q的第k+1個(gè)最近鄰qk+1有qk+1∈AG1(p)∪AG2(p)∪…∪AGk(p)，(k為整數(shù)，k≥1)，即q的第k+1個(gè)最近鄰在p的前k級(jí)鄰接生成點(diǎn)中.則顯然有qk∈AG1(p)∪AG2(p)∪…∪AGk-1(p)，即q的第k個(gè)最近鄰在p的前k-1級(jí)鄰接生成點(diǎn)中.故p的第k級(jí)及高于k級(jí)的鄰接生成點(diǎn)中不可能存在q的kNN.若pj∈AGn(p)(n>k)，即pj是p的高于k級(jí)的鄰接生成點(diǎn)，則反過來同理，p是pj的高于k級(jí)的鄰接生成點(diǎn).根據(jù)定理3，pj的kNN不包括p，也就是q的RkNN不包括pj.當(dāng)存在障礙物時(shí)，pj到q的障礙距離一定大于等于它們之間的歐氏距離，故q的RkNN更不可能包括pj.因此，在障礙空間中，q的RkNN只在q的最近鄰的前k級(jí)鄰接生成點(diǎn)中，因此只保留q的最近鄰的前k級(jí)鄰接生成點(diǎn)及在前k級(jí)鄰接區(qū)域內(nèi)的障礙物.

證畢.

定理5. 設(shè)p在NN(q)的第n級(jí)鄰接生成點(diǎn)中，即p∈AGn(NN(q)).p到q的路徑上經(jīng)過若干數(shù)據(jù)點(diǎn)pi，令單條路徑上pi的總個(gè)數(shù)不大于n，將與p可視的pi總個(gè)數(shù)記作sumcount(p,q)，如果sumcount(p,q)≥k，則數(shù)據(jù)點(diǎn)p被剪枝.

證明. 設(shè)p到查詢點(diǎn)q的路徑上經(jīng)過的數(shù)據(jù)點(diǎn)為pi，當(dāng)k=1時(shí)，則p到q的路徑最多只經(jīng)過1個(gè)數(shù)據(jù)點(diǎn)pi，若p對(duì)pi是可視的，則一定有diste(p,pi)1時(shí)，如果對(duì)p可視的pi的個(gè)數(shù)大于或等于k個(gè)，那么p的k最近鄰可能包括pi中的1～k個(gè)，但一定不包括q，故q應(yīng)被剪枝.

證畢.

定理6. 若p∈Sc且它的1級(jí)鄰接生成點(diǎn)均被剪枝，則數(shù)據(jù)點(diǎn)p被剪枝.

證明. 設(shè)p為候選集合中的一點(diǎn)(p∈Sc)，a為p的1級(jí)鄰接生成點(diǎn)之一(a∈AG1(p))，且a是p到q路徑上經(jīng)過的點(diǎn).若p的1級(jí)鄰接生成點(diǎn)均被剪枝，顯然a也被剪枝，即sumcount(a,q)≥k，那么一定有sumcount(p,q)≥k+1.由于sumcount(p,q)>k，則根據(jù)定理5，p被剪枝.

證畢.

本節(jié)提出的剪枝算法的主要思想為：通過定理4～6這3個(gè)剪枝策略，剪枝掉大量的非候選者以及對(duì)查詢無影響的障礙物，獲得候選集合Sc.這一過程中首先以數(shù)據(jù)點(diǎn)集P為生成點(diǎn)生成Voronoi圖.然后計(jì)算查詢點(diǎn)集Q的質(zhì)心q，并用質(zhì)心q近似地代表查詢點(diǎn)集整體.再根據(jù)定理4，將NN(q)的前k級(jí)鄰接生成點(diǎn)放入候選集合Sc中，高于k級(jí)的鄰接生成點(diǎn)不可能是q的RkNN，因此被剪枝，進(jìn)而獲得初步的候選集，同時(shí)獲得剪枝后的新障礙集.根據(jù)定理5,6對(duì)候選集中的數(shù)據(jù)點(diǎn)進(jìn)行判斷，滿足條件的數(shù)據(jù)點(diǎn)被剪枝，剩下的未被剪枝的數(shù)據(jù)點(diǎn)構(gòu)成更精確的候選集.基于以上討論，進(jìn)一步給出剪枝算法，如算法1所示：

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

輸入:查詢點(diǎn)集Q、數(shù)據(jù)點(diǎn)集P、障礙物集O、k值；

輸出:候選集Sc、剪枝后的障礙集Onew.

Create_Voronoi(P)；*以P中數(shù)據(jù)點(diǎn)為生成點(diǎn)創(chuàng)建Voronoi圖*

Sc←?；*初始化候選集Sc為空集*

o∈O；

count←0；sumcount←0；

q←Calculate_Centroid(Q)；*計(jì)算查詢點(diǎn)集Q的質(zhì)心q*

ifq∈VP(p) then

NN(q)←p；*q的最近鄰是數(shù)據(jù)點(diǎn)p*

fori=1 tokdo

Sc←Sc+AGi(p)；*將p的第i級(jí)鄰接生成點(diǎn)集加入Sc中*

endfor

endif

for eachp′∈Scdo

ifVP(p′)∩o≠? then

Onew←Onew+o；*剪枝障礙物*

endif

ifcount≤nthen

for eachpi∈Path(p′,q)*pi是p′到q路徑上的點(diǎn)*

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

sumcount←sumcount+1；

endif

ifsumcount≥kthen

Sc←Sc-p′；*定理5*

endif

endfor

endif

endfor

for eachp″∈Scdo

ifAG1(p″)∩Sc=? then

Sc←Sc-p″；*定理6*

endif

endfor

returnSc，Onew.

2.2 精煉過程

在精煉過程中，首先根據(jù)定理7對(duì)候選集Sc中的候選點(diǎn)進(jìn)行精煉處理，得到更精確的候選集;再根據(jù)OGRkNN的定義對(duì)候選集中的點(diǎn)逐一排除，獲得準(zhǔn)確的結(jié)果集.

定理7. 當(dāng)p∈Sc且p對(duì)查詢點(diǎn)q是可視的，則以p點(diǎn)為圓心、以diste(p,q)為半徑畫圓，將該判定圓內(nèi)p可視的數(shù)據(jù)點(diǎn)的個(gè)數(shù)記作count_points，若count_points≥k，則數(shù)據(jù)點(diǎn)p被剪枝.當(dāng)p對(duì)查詢點(diǎn)q是不可視時(shí)，以p點(diǎn)為圓心、以distb(p,q)為半徑畫圓，同樣，若count_points≥k，則數(shù)據(jù)點(diǎn)p被剪枝.

證明. 分2種情況：

1) 當(dāng)p∈Sc且p對(duì)查詢點(diǎn)q是可視的時(shí)候，如圖1所示.以p點(diǎn)為圓心、以diste(p,q)為半徑畫圓，則在判定圓內(nèi)的數(shù)據(jù)點(diǎn)有{p1,p2,p3,p4,p5,p6,p7}，其中{p1,p3,p6}對(duì)p是不可視的，{p2,p4,p5,p7}對(duì)p是可視的，則count_points=4.當(dāng)k=4時(shí)，顯然p的4NN是{p2,p4,p5,p7}，而不包括q.當(dāng)k<4時(shí)，由于數(shù)據(jù)點(diǎn){p2,p4,p5,p7}到p的距離均小于q到p的距離，故p的kNN是{p2,p4,p5,p7}中的k個(gè)，一定不包括q，故q的RkNN一定不是數(shù)據(jù)點(diǎn)p，因此p被剪枝.

Fig. 1 Proof 1 of theorem 7圖1 定理7的證明情況1

2) 當(dāng)p∈Sc且p對(duì)查詢點(diǎn)q是不可視的時(shí)候，如圖2所示.以p點(diǎn)為圓心、以distb(p,q)為半徑畫圓，則在判定圓內(nèi)的數(shù)據(jù)點(diǎn)有{p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13}，其中{p1,p2,p4,p6,p12,p13}對(duì)p是不可視的，{p3,p5,p7,p8,p9,p10,p11}對(duì)p是可視的，則count_points=7.當(dāng)k=7時(shí)，顯然p的7NN是{p3,p5,p7,p8,p9,p10,p11}，而不包括q.當(dāng)k<7時(shí)，由于數(shù)據(jù)點(diǎn){p3,p5,p7,p8,p9,p10,p11}到p的距離均小于q到p的距離，故p的kNN是{p3,p5,p7,p8,p9,p10,p11}中的k個(gè)，必不包括q，故q的RkNN不是數(shù)據(jù)點(diǎn)p，因此p被剪枝.

證畢.

Fig. 2 Proof 2 of theorem 7圖2 定理7的證明情況2

下面給出精煉算法，如算法2所示.

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

輸入:查詢點(diǎn)集Q、數(shù)據(jù)點(diǎn)集P、障礙物集O、k值；

輸出:靜態(tài)障礙物環(huán)境下的查詢結(jié)果集SR.

count_points←0；

o∈Onew；

Sc←STA_OGRkNN_Filter(Q,P,O,k)；*調(diào)用算法1得到初步過濾后的候選集*

for eachp∈Scdo

if [p,q]∩o=? then

CR←Circle(p,diste(p,q))；

else

CR←Circle(p,distb(p,q))；

endif

ifpoint∈CRand [point,p]∩o=? then

count_points←count_points+1；

ifcount_points≥kthen

endif

endif

endfor

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

if[p,pi]∩o=? then

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

endif

fori=1 tokdo

ifdistb(p,pi)≥distthen

dist←distb(p,pi)；

pk←pi；*p的第k個(gè)最近鄰為pk*

endif

endfor

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

endif

endfor

returnSR.

3 動(dòng)態(tài)障礙物環(huán)境下的OGRkNN查詢方法

由于現(xiàn)實(shí)生活中的障礙物不是靜止不變的，所以本節(jié)進(jìn)一步給出動(dòng)態(tài)障礙物環(huán)境下的OGRkNN查詢方法.

3.1 障礙物動(dòng)態(tài)增加情況下的OGRkNN查詢方法

根據(jù)新增加的障礙物所在的位置，分2種情況討論:1)新增加的障礙物對(duì)算法2的查詢結(jié)果沒有影響;2)有影響.根據(jù)定理4，q的最近鄰的第k級(jí)及以外的鄰接生成點(diǎn)和障礙物被剪枝，故將NN(q)的前k級(jí)鄰接區(qū)域稱為影響區(qū)域，用Affected_Area表示.設(shè)新增加的障礙物為o′，當(dāng)o′?Affected_Area時(shí)，由于在過濾過程中根據(jù)定理4會(huì)對(duì)影響區(qū)域以外的數(shù)據(jù)點(diǎn)以及障礙物進(jìn)行剪枝，此時(shí)o′會(huì)一同被剪枝，所以o′對(duì)算法2的查詢結(jié)果無影響.當(dāng)o′∈Affected_Area時(shí)，設(shè)增加o′之前q的RkNN為{pi}，若o′對(duì)[q,pi]造成阻斷，則distb(q,pi)=diste(q,o′)+diste(o′,pi)，顯然有distb(q,pi)>diste(q,pi)，故pi不再是q的RkNN;若o′對(duì)[q,pi]沒有造成阻斷，則o′對(duì)查詢結(jié)果無影響.

基于以上討論可得出判定規(guī)則1和判定規(guī)則2.

判定規(guī)則1. 設(shè)新增加的障礙物為o′，若o′?Affected_Area，則對(duì)算法2的查詢結(jié)果沒有影響;若o′∈Affected_Area，則需要對(duì)算法2的查詢結(jié)果集進(jìn)行再判斷.

判定規(guī)則2. 障礙物動(dòng)態(tài)增加情況下的OGRkNN查詢結(jié)果集一定是靜態(tài)障礙物環(huán)境下的OGRkNN查詢結(jié)果的子集.

根據(jù)判定規(guī)則1和判定規(guī)則2，本節(jié)提出的障礙物動(dòng)態(tài)增加情況下的OGRkNN查詢方法的主要思想為：首先判斷新增加的障礙物的位置，然后計(jì)算受影響區(qū)域范圍.根據(jù)判定規(guī)則1和判定規(guī)則2進(jìn)行判斷，若新增障礙物不在影響區(qū)域內(nèi)，則返回靜態(tài)障礙物環(huán)境下的查詢結(jié)果；若新增障礙物在影響區(qū)域內(nèi)，則對(duì)結(jié)果集中的數(shù)據(jù)點(diǎn)進(jìn)行判斷.若p到q的障礙距離大于p到它的第k個(gè)最近鄰的障礙距離，則說明在新增加障礙物之后p不再是q的反k最近鄰，故p被刪除，最后剩下的數(shù)據(jù)點(diǎn)就是障礙物動(dòng)態(tài)增加情況下的查詢結(jié)果.

基于以上討論，進(jìn)一步給出障礙物動(dòng)態(tài)增加情況下的查詢算法，如算法3所示.

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

輸入:查詢點(diǎn)集Q、數(shù)據(jù)點(diǎn)集P、障礙物集O、k值、新增加的障礙物o′；

輸出:障礙物動(dòng)態(tài)增加情況下的查詢結(jié)果集Snew.

O′←O∪o′;*O′為新增加障礙物之后的障礙集*

Affected_Area←?;*受影響區(qū)域初始化*

SR←STA_OGRkNN(Q,P,O,k)；

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

ifo′∩Affected_Area=? then*新增障礙物不在影響區(qū)域內(nèi)*

Snew←SR；

for eachp′ inSRdo

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

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

endif

SR←SR-p′；

endif

endfor

Snew←SR；

endif

returnSnew.

3.2 障礙物動(dòng)態(tài)減少情況下的OGRkNN查詢方法

根據(jù)減少的障礙物所在的位置，分2種情況討論:1)新增加的障礙物對(duì)算法2的查詢結(jié)果沒有影響;2)有影響.設(shè)減少的障礙物為o′，當(dāng)o′?Affected_Area時(shí)，由于在過濾過程中根據(jù)定理4會(huì)對(duì)影響區(qū)域以外的數(shù)據(jù)點(diǎn)以及障礙物進(jìn)行剪枝，此時(shí)o′會(huì)一同被剪枝，所以o′對(duì)算法2的查詢結(jié)果無影響;當(dāng)o′∈Affected_Area時(shí)，設(shè)減少o′之前q的RkNN為{pi}，若[q,pi]原來是阻斷的，減少o′之后變成可視的，則q和pi之間的距離由障礙距離變成了歐氏距離，則有diste(q,pi)

基于以上討論給出判定規(guī)則3.

判定規(guī)則3. 設(shè)減少的障礙物為o′，若o′?Affected_Area，則對(duì)算法2的查詢結(jié)果沒有影響;若o′∈Affected_Area，則需將障礙集去除o′后再進(jìn)行查詢.

基于判定規(guī)則3，本節(jié)提出的障礙物動(dòng)態(tài)減少情況下的OGRkNN查詢算法的主要思想為：首先判斷減少的障礙物所在的位置，然后計(jì)算受影響區(qū)域范圍，根據(jù)判定規(guī)則3，將減少的障礙物是否在影響區(qū)域內(nèi)分為2種情況.若不在影響區(qū)域內(nèi)，說明減少的障礙物對(duì)算法2的查詢結(jié)果不構(gòu)成影響；若在影響區(qū)域內(nèi)，則將算法2中的障礙集替換成減少障礙物之后的新障礙集，最后通過調(diào)用算法2得到障礙物動(dòng)態(tài)減少情況下的查詢結(jié)果.

基于以上討論，進(jìn)一步給出障礙物動(dòng)態(tài)減少情況下的查詢算法，如算法4所示.

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

輸入: 查詢點(diǎn)集Q、數(shù)據(jù)點(diǎn)集P、障礙物集O、k值、減少的障礙物o′；

輸出: 障礙物動(dòng)態(tài)減少時(shí)的查詢結(jié)果集Snew.

O′←O-o′;*O′為減少障礙物之后的新障礙集*

Affected_Area←?;*受影響區(qū)域初始化*

Judge_Position(o′);*判斷減少的障礙物的位置*

ifo′∩Affected_Area=? then*減少的障礙物不在影響區(qū)域內(nèi)*

SR←STA_OGRkNN(Q,P,O,k)；

SR←STA_OGRkNN(Q,P,O′,k);*更新障礙集后再進(jìn)行查詢*

endif

Snew←SR；

returnSnew.

3.3 障礙物動(dòng)態(tài)移動(dòng)情況下的OGRkNN查詢方法

本節(jié)主要研究的是障礙物動(dòng)態(tài)移動(dòng)情況下的OGRkNN查詢方法.如圖3所示，虛線箭頭指向的是移動(dòng)方向，原障礙集為{o1,o2,o3,obef}，obef為發(fā)生移動(dòng)的障礙物.在obef移動(dòng)之前，q的R6NN包括p而不包括p12；障礙物obef移動(dòng)之后，障礙集變?yōu)閧o1,o2,o3,oaft}，oaft為移動(dòng)之后的障礙物，q的R6NN包括p12而不包括p.在障礙物移動(dòng)前后的OGRkNN查詢結(jié)果發(fā)生變化，故障礙物動(dòng)態(tài)移動(dòng)情況下的OGRkNN查詢方法具有較高的研究?jī)r(jià)值.

Fig. 3 Example about dynamically moving obstacles圖3 障礙物動(dòng)態(tài)移動(dòng)示例

為了判斷移動(dòng)的障礙物對(duì)查詢結(jié)果是否產(chǎn)生影響，首先判斷發(fā)生移動(dòng)的障礙物移動(dòng)前后所在的位置，分別記為obef和oaft；然后根據(jù)obef和oaft的位置是否在影響區(qū)域內(nèi)分為4種情況：

1) 障礙物在影響區(qū)域外發(fā)生移動(dòng)，即obef和oaft均在Affected_Area外.例如圖4中o3移動(dòng)到o4.

2) 障礙物在影響區(qū)域內(nèi)發(fā)生移動(dòng)，即obef和oaft均在Affected_Area內(nèi).例如圖4中o1移動(dòng)到o2.

3) 障礙物從影響區(qū)域內(nèi)移動(dòng)到影響區(qū)域外，即obef在Affected_Area內(nèi)，oaft在Affected_Area外.例如圖4中o2移動(dòng)到o3.

4) 障礙物從影響區(qū)域外移動(dòng)到影響區(qū)域內(nèi)，即obef在Affected_Area外，oaft在Affected_Area內(nèi).例如圖4中o4移動(dòng)到o1.

Fig. 4 Example of obstacle movement圖4 障礙物移動(dòng)的示例

情況1中的obef和oaft均在Affected_Area外，根據(jù)定理4會(huì)對(duì)Affected_Area以外的數(shù)據(jù)點(diǎn)以及障礙物進(jìn)行剪枝，此時(shí)obef和oaft會(huì)一同被剪枝，所以情況1對(duì)STA_OGRkNN查詢結(jié)果無影響.情況2中的obef和oaft均在Affected_Area內(nèi)，設(shè)障礙物移動(dòng)前q的RkNN為{pi}，pm,pn∈{pi}，若[q,pm]原來是阻斷的，[q,pn]是可視的，障礙物移動(dòng)之后[q,pm]變成可視的，[q,pn]變成阻斷的，則pm有可能不再是q的RkNN，而pn有可能變成q的RkNN，說明障礙物移動(dòng)后會(huì)對(duì)查詢結(jié)果產(chǎn)生影響.若障礙物的移動(dòng)對(duì)[q,pi]的可視性不產(chǎn)生影響，則對(duì)查詢結(jié)果無影響.由于情況2的不確定性，故需更新障礙集后再進(jìn)行查詢.情況3中obef在Affected_Area內(nèi)，同情況2一樣對(duì)查詢結(jié)果可能有影響，oaft在Affected_Area外，對(duì)查詢結(jié)果無影響，故也需更新障礙集.同理，情況4需要更新障礙集再進(jìn)行查詢.

基于以上4種情況的討論給出判定規(guī)則4.

判定規(guī)則4. 情況1中的障礙物發(fā)生移動(dòng)對(duì)查詢結(jié)果不產(chǎn)生影響；情況2中obef和oaft均在Affected_Area內(nèi)，需要將障礙集更新為O-obef+oaft；情況3中obef在Affected_Area內(nèi)，需要將障礙集更新為O-obef；情況4中oaft在Affected_Area內(nèi)，需要將障礙集更新為O+oaft.

基于判定規(guī)則4，本節(jié)提出的障礙物動(dòng)態(tài)移動(dòng)情況下的OGRkNN查詢算法的主要思想為：首先判斷發(fā)生移動(dòng)的障礙物移動(dòng)前后所在的位置；然后計(jì)算受影響區(qū)域范圍；再根據(jù)判定規(guī)則4分別對(duì)4種情況進(jìn)行處理；最后得到障礙物移動(dòng)情況下的OGRkNN查詢結(jié)果.基于以上討論，進(jìn)一步給出障礙物動(dòng)態(tài)移動(dòng)情況下的查詢算法，如算法5所示.

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

輸入:查詢點(diǎn)集Q、數(shù)據(jù)點(diǎn)集P、原障礙集O、k值、移動(dòng)前的障礙物obef、移動(dòng)后的障礙物oaft；

輸出:障礙物動(dòng)態(tài)移動(dòng)時(shí)的查詢結(jié)果集Snew.

obef∈O;*移動(dòng)前的障礙物屬于原障礙集O

Affected_Area←?;*受影響區(qū)域初始化*

Judge_Position(obef);*判斷障礙物移動(dòng)前的位置*

Judge_Position(oaft);*判斷障礙物移動(dòng)后的位置*

ifobef,oaft?Affected_Areathen*情況1*

SR←STA_OGRkNN(Q,P,O,k)；

else ifobef,oaft∈Affected_Areathen*情況2)*

O′←O-obef；

O′←O′+oaft；

SR←STA_OGRkNN(Q,P,O′,k)；

else ifobef∈Affected_Areaandoaft?Affected_Areathen*情況3*

O′←O-obef；

SR←STA_OGRkNN(Q,P,O′,k)；

elseobef?Affected_Areaandoaft∈Affected_Areathen*情況4*

O′←O+oaft；

SR←STA_OGRkNN(Q,P,O′,k)；

endif

Snew←SR；

returnSnew.

4 實(shí)驗(yàn)比較與分析

本節(jié)通過實(shí)驗(yàn)對(duì)所提算法進(jìn)行性能分析.由于已有的研究成果無法直接處理障礙空間中的組反k最近鄰查詢問題，故我們對(duì)文獻(xiàn)[15-16]提出的障礙反k最近鄰查詢算法采用反復(fù)調(diào)用的方式應(yīng)用于一組查詢點(diǎn)中，形成對(duì)比算法.我們將反復(fù)調(diào)用形成的對(duì)比算法分別稱作GRkNNobs算法和GORkNN算法.2個(gè)對(duì)比算法的主要思想為：將已有的針對(duì)一個(gè)查詢對(duì)象的障礙反k最近鄰查詢算法應(yīng)用到一組查詢對(duì)象的情況中，也就是采用反復(fù)調(diào)用的方式對(duì)一組對(duì)象中的每個(gè)對(duì)象成員進(jìn)行障礙反k最近鄰查詢，所有查詢結(jié)果的并集就是障礙組反k最近鄰查詢的結(jié)果.

實(shí)驗(yàn)平臺(tái)配置如下：2.0 GHz CPU，4 GB內(nèi)存，500 GB硬盤，Windows 7操作系統(tǒng)上用Microsoft Visual Studio 2005實(shí)現(xiàn).本文使用的數(shù)據(jù)集是從美國(guó)加利福尼亞州的道路網(wǎng)絡(luò)中的數(shù)據(jù)對(duì)象集抽取出來的80 000個(gè)節(jié)點(diǎn)對(duì)象和5 000個(gè)線段對(duì)象.查詢點(diǎn)集Q是在節(jié)點(diǎn)對(duì)象集中隨機(jī)抽出的n個(gè)點(diǎn)的集合.實(shí)驗(yàn)測(cè)試的指標(biāo)為運(yùn)行時(shí)間，并取執(zhí)行100次查詢的平均值.實(shí)驗(yàn)首先對(duì)STA_OGRkNN算法進(jìn)行測(cè)試，分別測(cè)試k值、查詢點(diǎn)數(shù)量、數(shù)據(jù)點(diǎn)集大小、障礙物個(gè)數(shù)對(duì)于運(yùn)行時(shí)間的影響，然后對(duì)動(dòng)態(tài)障礙物環(huán)境中的查詢方法的3個(gè)算法分別進(jìn)行測(cè)試.

Fig. 5 Effect of k on runtime圖5 k值對(duì)CPU時(shí)間的影響

如圖5所示，首先分析k值對(duì)運(yùn)行時(shí)間的影響.實(shí)驗(yàn)規(guī)模為80 000，查詢點(diǎn)的數(shù)量為10，障礙物的數(shù)量為1 000.圖5給出了3個(gè)算法的運(yùn)行時(shí)間隨著k值變化的對(duì)比結(jié)果.隨著k值的不斷變大，算法的CPU時(shí)間均呈上升趨勢(shì).由于GRkNNobs算法和GORkNN算法需要對(duì)每一個(gè)查詢點(diǎn)計(jì)算它的反k最近鄰，這樣就造成了搜索區(qū)域的頻繁重疊情況，k值越大，搜索區(qū)域重疊的面積越大，從而花費(fèi)的查詢時(shí)間越多.本文提出的STA_OGRkNN算法分別對(duì)查詢點(diǎn)集和數(shù)據(jù)點(diǎn)集進(jìn)行了預(yù)處理，縮小了查詢范圍，同時(shí)利用Voronoi圖的特性進(jìn)行高效地剪枝和精煉，當(dāng)k值越大時(shí)，該算法的優(yōu)勢(shì)越明顯.

圖6給出了查詢點(diǎn)數(shù)量對(duì)運(yùn)行時(shí)間的影響.實(shí)驗(yàn)設(shè)定k值為10，數(shù)據(jù)點(diǎn)集的規(guī)模設(shè)置為80 000，障礙物的數(shù)量為1 000.從圖6中可以看出GRkNNobs算法的運(yùn)行時(shí)間上升趨勢(shì)明顯，其次為GORkNN算法，因?yàn)檫@2個(gè)算法都需要對(duì)每一個(gè)查詢點(diǎn)計(jì)算它的障礙反k最近鄰，當(dāng)查詢點(diǎn)數(shù)量增長(zhǎng)時(shí)，算法所用的查詢時(shí)間也會(huì)大幅增長(zhǎng)；而STA_OGRkNN算法的查詢時(shí)間的上升趨勢(shì)較為平緩，因?yàn)樗惴ㄖ杏袑?duì)查詢點(diǎn)集的處理過程，所以當(dāng)查詢點(diǎn)數(shù)量呈倍數(shù)增長(zhǎng)時(shí)，對(duì)算法的性能影響不大.

Fig. 6 Effect of query points number on runtime圖6 查詢點(diǎn)數(shù)量對(duì)查詢時(shí)間的影響

Fig. 7 Effect of dataset scale on runtime圖7 數(shù)據(jù)點(diǎn)集規(guī)模對(duì)CPU時(shí)間的影響

圖7給出了數(shù)據(jù)點(diǎn)集規(guī)模對(duì)算法運(yùn)行時(shí)間的影響.實(shí)驗(yàn)設(shè)定k值為10，查詢點(diǎn)的數(shù)量為10，障礙物的數(shù)量為1 000.隨著數(shù)據(jù)點(diǎn)集規(guī)模的變大，3個(gè)算法的運(yùn)行時(shí)間均呈上升趨勢(shì).GRkNNobs算法和GORkNN算法在計(jì)算一組查詢點(diǎn)中每個(gè)查詢點(diǎn)的障礙反k最近鄰時(shí)，消耗大量查詢時(shí)間;而STA_OGRkNN算法首先對(duì)查詢點(diǎn)集進(jìn)行優(yōu)化處理，避免了搜索區(qū)域頻繁重疊的現(xiàn)象，然后利用Voronoi圖的鄰接特性在剪枝階段和精煉階段有效地過濾掉大量的非候選者，快速地縮小查詢范圍，故該算法隨著數(shù)據(jù)集的增大所花費(fèi)的運(yùn)行時(shí)間較少.

接下來分析障礙物的個(gè)數(shù)對(duì)運(yùn)行時(shí)間的影響，實(shí)驗(yàn)設(shè)定k=10，查詢點(diǎn)的數(shù)量為10，數(shù)據(jù)點(diǎn)集的規(guī)模為80 000.如圖8所示，隨著障礙物的數(shù)量增加，運(yùn)行時(shí)間越長(zhǎng).GRkNNobs算法和GORkNN算法需要計(jì)算每一個(gè)查詢點(diǎn)的障礙RkNN，這一過程中計(jì)算障礙距離的時(shí)間花費(fèi)較大;而STA_OGRkNN算法在剪枝階段對(duì)沒有影響的障礙物進(jìn)行剪枝，故隨著障礙物數(shù)量的增加，該算法的運(yùn)行時(shí)間增加幅度緩慢.

Fig. 8 Effect of obstacal number on runtime圖8 障礙物的個(gè)數(shù)對(duì)CPU時(shí)間的影響

最后測(cè)試動(dòng)態(tài)障礙物環(huán)境的OGRkNN查詢方法的性能.對(duì)GRkNNobs算法和GORkNN算法采取重新調(diào)用的方式應(yīng)用于動(dòng)態(tài)障礙物環(huán)境中，形成對(duì)比算法.表1反映了本文提出的DYN_ADD_OGRkNN算法與對(duì)比算法在障礙物動(dòng)態(tài)增加時(shí)的性能對(duì)比.實(shí)驗(yàn)設(shè)定k=10，查詢點(diǎn)的數(shù)量為10，數(shù)據(jù)點(diǎn)集的規(guī)模為80 000.測(cè)試的指標(biāo)為查詢時(shí)間，并取執(zhí)行1 000次查詢的平均值.為了方便研究，以每次增加1個(gè)障礙物的方式進(jìn)行測(cè)試.如表1所示，當(dāng)障礙物數(shù)量從2 000變成3 000時(shí)，DYN_ADD_OGRkNN算法的平均查詢時(shí)間變化不大，而GRkNNobs算法和GORkNN算法的查詢時(shí)間幾乎呈倍數(shù)增長(zhǎng).

表2顯示的是當(dāng)障礙物動(dòng)態(tài)減少時(shí)DYN_DEL_OGRkNN算法與對(duì)比算法的查詢時(shí)間比較.對(duì)GRkNNobs算法和GORkNN算法采用重新調(diào)用的方式應(yīng)用于障礙物動(dòng)態(tài)減少環(huán)境中，此時(shí)對(duì)比算法的主要思想為：使用減少障礙物之后的新障礙集作為參數(shù)，重新執(zhí)行一遍算法得出結(jié)果.如表2所示，GRkNNobs和GORkNN算法的查詢時(shí)間遠(yuǎn)遠(yuǎn)多于DYN_DEL_OGRkNN算法，這是由于2個(gè)對(duì)比算法只是單純地重復(fù)執(zhí)行一次；而DYN_DEL_OGRkNN算法會(huì)判斷減少的障礙物所在的位置，再分別采取不同的方法，這樣就避免了很多冗余計(jì)算.

Table 1 Performance Comparison Between DYN_ADD_OGRkNN and Other Algorithms

Table 2 Performance Comparison Between DYN_DEL_OGRkNN and Other Algorithms

表3顯示的是當(dāng)障礙物動(dòng)態(tài)移動(dòng)時(shí)DYN_MOVE_OGRkNN算法與對(duì)比算法的平均查詢時(shí)間比較情況.對(duì)GRkNNobs算法和GORkNN算法采用重新調(diào)用的方式應(yīng)用于障礙物動(dòng)態(tài)移動(dòng)環(huán)境中.

Table 3 Performance Comparison Between DYN_MOVE_OGRkNN and Other Algorithms

如表3所示，當(dāng)障礙物發(fā)生移動(dòng)時(shí)，GRkNNobs和GORkNN算法的執(zhí)行時(shí)間遠(yuǎn)多于DYN_MOVE_OGRkNN算法.

5 結(jié)束語

本文基于Voronoi圖的鄰接特性提出了處理障礙空間中組反k最近鄰查詢的方法，解決了針對(duì)靜態(tài)障礙物環(huán)境以及動(dòng)態(tài)障礙物環(huán)境下的組反k最近鄰查詢的問題.給出OGRkNN查詢的定義和實(shí)現(xiàn)算法.解決該問題的難點(diǎn)在于如何快速準(zhǔn)確地獲得查詢結(jié)果，為此提出高效的剪枝規(guī)則.在剪枝階段利用剪枝策略對(duì)數(shù)據(jù)集進(jìn)行剪枝，過濾掉大量的非候選者，快速地縮小查詢范圍.在精煉階段對(duì)候選集進(jìn)行精煉處理提高了算法的準(zhǔn)確性.在STA_OGRkNN查詢基礎(chǔ)上給出障礙物動(dòng)態(tài)增加情況下的OGRkNN查詢方法、障礙物動(dòng)態(tài)減少情況下的OGRkNN查詢方法以及障礙物動(dòng)態(tài)移動(dòng)情況下的OGRkNN查詢方法.理論研究和實(shí)驗(yàn)表明，所提算法具有較好的性能.未來的研究重點(diǎn)主要集中在障礙空間中針對(duì)不確定數(shù)據(jù)的組反k最近鄰查詢方面.