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

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

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

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

(zhanglptg@163.com)

隨著基于位置服務技術的廣泛應用，空間數據庫中的最近鄰(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

定義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)內任一點，pk+1∈AGk+1(pi).那么必存在一點pk∈AGk(pi)使得dist(q,pk)≤dist(q,pk+1).

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

定理3[18]. 對于Voronoi多邊形VP(pi)內任一點q，q的第k+1個最近鄰qk+1有qk+1∈AG1(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)=
{?q∈Q,?p∈P|q∈OkNN(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+1有qk+1∈AG1(p)∪AG2(p)∪…∪AGk(p)，(k為整數，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級的鄰接生成點.根據定理3，pj的kNN不包括p，也就是q的RkNN不包括pj.當存在障礙物時，pj到q的障礙距離一定大于等于它們之間的歐氏距離，故q的RkNN更不可能包括pj.因此，在障礙空間中，q的RkNN只在q的最近鄰的前k級鄰接生成點中，因此只保留q的最近鄰的前k級鄰接生成點及在前k級鄰接區域內的障礙物.

證畢.

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

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

證畢.

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

證明. 設p為候選集合中的一點(p∈Sc)，a為p的1級鄰接生成點之一(a∈AG1(p))，且a是p到q路徑上經過的點.若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、障礙物集O、k值；

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

Create_Voronoi(P)；*以P中數據點為生成點創建Voronoi圖*

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

o∈O；

count←0；sumcount←0；

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

ifq∈VP(p) then

NN(q)←p；*q的最近鄰是數據點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 精煉過程

在精煉過程中，首先根據定理7對候選集Sc中的候選點進行精煉處理，得到更精確的候選集;再根據OGRkNN的定義對候選集中的點逐一排除，獲得準確的結果集.

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

證明. 分2種情況：

1) 當p∈Sc且p對查詢點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的距離均小于q到p的距離，故p的kNN是{p2,p4,p5,p7}中的k個，一定不包括q，故q的RkNN一定不是數據點p，因此p被剪枝.

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

2) 當p∈Sc且p對查詢點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的距離均小于q到p的距離，故p的kNN是{p3,p5,p7,p8,p9,p10,p11}中的k個，必不包括q，故q的RkNN不是數據點p，因此p被剪枝.

證畢.

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

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

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

輸入:查詢點集Q、數據點集P、障礙物集O、k值；

輸出:靜態障礙物環境下的查詢結果集SR.

count_points←0；

o∈Onew；

Sc←STA_OGRkNN_Filter(Q,P,O,k)；*調用算法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 動態障礙物環境下的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進行判斷，若新增障礙物不在影響區域內，則返回靜態障礙物環境下的查詢結果；若新增障礙物在影響區域內，則對結果集中的數據點進行判斷.若p到q的障礙距離大于p到它的第k個最近鄰的障礙距離，則說明在新增加障礙物之后p不再是q的反k最近鄰，故p被刪除，最后剩下的數據點就是障礙物動態增加情況下的查詢結果.

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

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

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

輸出:障礙物動態增加情況下的查詢結果集Snew.

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

Affected_Area←?;*受影響區域初始化*

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

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

ifo′∩Affected_Area=? then*新增障礙物不在影響區域內*

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 障礙物動態減少情況下的OGRkNN查詢方法

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

基于以上討論給出判定規則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、障礙物集O、k值、減少的障礙物o′；

輸出: 障礙物動態減少時的查詢結果集Snew.

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

Affected_Area←?;*受影響區域初始化*

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

ifo′∩Affected_Area=? then*減少的障礙物不在影響區域內*

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

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

endif

Snew←SR；

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 障礙物動態移動示例

為了判斷移動的障礙物對查詢結果是否產生影響，首先判斷發生移動的障礙物移動前后所在的位置，分別記為obef和oaft；然后根據obef和oaft的位置是否在影響區域內分為4種情況：

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

2) 障礙物在影響區域內發生移動，即obef和oaft均在Affected_Area內.例如圖4中o1移動到o2.

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

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

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

情況1中的obef和oaft均在Affected_Area外，根據定理4會對Affected_Area以外的數據點以及障礙物進行剪枝，此時obef和oaft會一同被剪枝，所以情況1對STA_OGRkNN查詢結果無影響.情況2中的obef和oaft均在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中obef在Affected_Area內，同情況2一樣對查詢結果可能有影響，oaft在Affected_Area外，對查詢結果無影響，故也需更新障礙集.同理，情況4需要更新障礙集再進行查詢.

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

判定規則4. 情況1中的障礙物發生移動對查詢結果不產生影響；情況2中obef和oaft均在Affected_Area內，需要將障礙集更新為O-obef+oaft；情況3中obef在Affected_Area內，需要將障礙集更新為O-obef；情況4中oaft在Affected_Area內，需要將障礙集更新為O+oaft.

基于判定規則4，本節提出的障礙物動態移動情況下的OGRkNN查詢算法的主要思想為：首先判斷發生移動的障礙物移動前后所在的位置；然后計算受影響區域范圍；再根據判定規則4分別對4種情況進行處理；最后得到障礙物移動情況下的OGRkNN查詢結果.基于以上討論，進一步給出障礙物動態移動情況下的查詢算法，如算法5所示.

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

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

輸出:障礙物動態移動時的查詢結果集Snew.

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

Affected_Area←?;*受影響區域初始化*

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

本節通過實驗對所提算法進行性能分析.由于已有的研究成果無法直接處理障礙空間中的組反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算法會判斷減少的障礙物所在的位置，再分別采取不同的方法，這樣就避免了很多冗余計算.

Table 1 Performance Comparison Between DYN_ADD_OGRkNN and Other Algorithms

Table 2 Performance Comparison Between DYN_DEL_OGRkNN and Other Algorithms

表3顯示的是當障礙物動態移動時DYN_MOVE_OGRkNN算法與對比算法的平均查詢時間比較情況.對GRkNNobs算法和GORkNN算法采用重新調用的方式應用于障礙物動態移動環境中.

Table 3 Performance Comparison Between DYN_MOVE_OGRkNN and Other Algorithms

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

5 結束語

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