障礙空間中基于Voronoi圖的組反k最近鄰查詢研究

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

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

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

(zhanglptg@163.com)

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

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

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

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

1 定義與定理

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

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

1) 1級鄰接生成點

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

2)k(k≥2)級鄰接生成點

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

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

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

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

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

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

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個步驟.首先通過剪枝可以過濾掉大量的非候選者以及對查詢沒有影響的障礙物，再對候選集進行精煉處理獲得準確的結(jié)果集.

2.1 剪枝過程

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

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

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

證畢.

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

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

證畢.

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

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

證畢.

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

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

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

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

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

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

o∈O；

count←0；sumcount←0；

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

ifq∈VP(p) then

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

fori=1 tokdo

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

endfor

endif

for eachp′∈Scdo

ifVP(p′)∩o≠? then

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

endif

ifcount≤nthen

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

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對候選集Sc中的候選點進行精煉處理，得到更精確的候選集;再根據(jù)OGRkNN的定義對候選集中的點逐一排除，獲得準確的結(jié)果集.

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

證明. 分2種情況：

1) 當p∈Sc且p對查詢點q是可視的時候，如圖1所示.以p點為圓心、以diste(p,q)為半徑畫圓，則在判定圓內(nèi)的數(shù)據(jù)點有{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時，由于數(shù)據(jù)點{p2,p4,p5,p7}到p的距離均小于q到p的距離，故p的kNN是{p2,p4,p5,p7}中的k個，一定不包括q，故q的RkNN一定不是數(shù)據(jù)點p，因此p被剪枝.

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

2) 當p∈Sc且p對查詢點q是不可視的時候，如圖2所示.以p點為圓心、以distb(p,q)為半徑畫圓，則在判定圓內(nèi)的數(shù)據(jù)點有{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時，由于數(shù)據(jù)點{p3,p5,p7,p8,p9,p10,p11}到p的距離均小于q到p的距離，故p的kNN是{p3,p5,p7,p8,p9,p10,p11}中的k個，必不包括q，故q的RkNN不是數(shù)據(jù)點p，因此p被剪枝.

證畢.

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

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

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

輸入:查詢點集Q、數(shù)據(jù)點集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個最近鄰為pk*

endif

endfor

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

endif

endfor

returnSR.

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

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

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

根據(jù)新增加的障礙物所在的位置，分2種情況討論:1)新增加的障礙物對算法2的查詢結(jié)果沒有影響;2)有影響.根據(jù)定理4，q的最近鄰的第k級及以外的鄰接生成點和障礙物被剪枝，故將NN(q)的前k級鄰接區(qū)域稱為影響區(qū)域，用Affected_Area表示.設(shè)新增加的障礙物為o′，當o′?Affected_Area時，由于在過濾過程中根據(jù)定理4會對影響區(qū)域以外的數(shù)據(jù)點以及障礙物進行剪枝，此時o′會一同被剪枝，所以o′對算法2的查詢結(jié)果無影響.當o′∈Affected_Area時，設(shè)增加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′對查詢結(jié)果無影響.

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

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

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

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

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

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

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

輸出:障礙物動態(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 障礙物動態(tài)減少情況下的OGRkNN查詢方法

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

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

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

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

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

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

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

輸出: 障礙物動態(tài)減少時的查詢結(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);*更新障礙集后再進行查詢*

endif

Snew←SR；

returnSnew.

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

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

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

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

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

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

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

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

Fig. 4 Example of obstacle movement圖4 障礙物移動的示例

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

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

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

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

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

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

obef∈O;*移動前的障礙物屬于原障礙集O

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

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

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

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 實驗比較與分析

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

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

Fig. 5 Effect of k on runtime圖5 k值對CPU時間的影響

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

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

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

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

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

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

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

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

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

Table 1 Performance Comparison Between DYN_ADD_OGRkNN and Other Algorithms

Table 2 Performance Comparison Between DYN_DEL_OGRkNN and Other Algorithms

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

Table 3 Performance Comparison Between DYN_MOVE_OGRkNN and Other Algorithms

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

5 結(jié)束語

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