障礙環境下線段反k最近區域查詢方法研究*

張麗平，任玲玲，郝曉紅，李 松

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

1 引言

近年來，隨著智能識別系統、地理信息系統、交通網絡系統等的廣泛應用，空間數據查詢技術具有越來越重要的作用。近鄰查詢是空間數據庫中的重要查詢類型。近鄰查詢包括許多種類：最近鄰[1]（nearest neighbor，NN）查詢、k最近鄰[2-4]（knearest neighbor，kNN）查詢、反向最近鄰[5-6]（reverse nearest neighbor，RNN）查詢、線段最近鄰[7]（line nearest neighbor，LNN）查詢、組最近鄰[8]（group nearest neighbor，GNN）查詢等，研究成果解決了最近鄰查詢領域的一系列重要問題。

反k最近鄰[9]（reverseknearest neighbor，RkNN）查詢是k最近鄰查詢的一個重要變體，獲得將查詢對象作為k最近鄰的數據對象集合。RkNN查詢通常反映出查詢點對哪些空間數據點影響較大，因此一般用來評估查詢對象的影響力。例如，游客出去度假（多為海邊或是山等），可以根據對其周邊設施的反k最近鄰查詢，來獲得合理的旅游方案。由于山脈、海、湖泊等不適合抽象為點或線段，但可以抽象為不規則圖形。由于其他景點或道路形成的障礙，因此需要考慮障礙環境下的線段反k最近區域的查詢方法。

國內外對無障礙空間下的kNN查詢和RkNN查詢以及障礙空間的kNN和RkNN查詢進行了一些重要研究。針對于無障礙空間的kNN查詢問題，文獻[10]中為了有效查詢和更新給定點的最近鄰，研究了基于空間網格的Voronoi圖的方法，并提出了相關算法。文獻[11]進一步考慮查詢結果的可用性，制定一個新的查詢類型MkDNN（movingkdynamic nearest neighbor），并且提出了一種增量維護k多樣性最近鄰算法。文獻[12]利用Voronoi圖預計算的優勢，可以解決kNN查詢，并提高了用戶的查詢效率。針對無障礙空間的反向k最近鄰（RkNN）查詢問題，文獻[13]提出了反向最近鄰的搜索方法，考慮反方向的查詢對象和目標對象之間的位置。文獻[14]提出了基于距離的方法可以在高維環境中產生更多的對比離群分數。采用經典的k-NN的評價方法，提出了基于無監督距離的離群點檢測中的反向最近鄰。文獻[15]提出了一種新的剪枝方法，該方法使用了一個多邊形近似未被剪枝的區域。

針對障礙環境下的kNN查詢問題，文獻[16]提出了一個地區的障礙處理MkNN（movingknearest neighbor）查詢方法，介紹和采用高效MkNN處理算法。文獻[17]主要提出障礙空間中的連續反k近鄰查詢問題。通過定義控制點和分割點，提出了針對該問題的處理框架。進一步地，提出了一系列的過濾和求精算法，包括剪枝數據集、獲取障礙物、剪枝和計算控制點和更新結果集等處理策略。文獻[18]通過有效的對象之間的路徑，提出了障礙環境下的連續kNN查詢的優化方法。針對障礙空間下的RkNN查詢問題，文獻[19]提出了剪枝算法，優化障礙反向最近鄰查詢算法。文獻[20]提出了一種基于Voronoi圖的剪枝方法，根據Voronoi圖和障礙距離的特性，減少了數據點處理個數。

目前的空間查詢方法僅限于對象為點或是線段的近鄰查詢，并沒有涉及到障礙空間下的線段最近區域。因此，在障礙空間中，如何查詢反向線段最近區域是一個新問題。為了有效解決該問題，本文首次提出了障礙環境下的反k線段最近區域查詢方法。該方法首先對數據區域集進行約減，縮減了查詢的搜索范圍。然后根據剪枝過程所提定理對候選集進行過濾，獲得更精確的候選集。最后根據Voronoi圖的性質提出相關定理，精煉OLRkNR（obstacle line reverseknearest region）查詢的結果集。

2 定義及性質

在給定的數據空間內，存在著區域和障礙物，其中區域為不規則圖形，障礙物為線段形狀。設障礙線段為O={o1,o2,…,om}，區域集Rs={r1,r2,…,rn}以及一個查詢線段l。障礙物與區域之間不相交，即O={o1,o2,…,om|Oi=oi1oi2,oi1oi2?rj=? ,i∈[1,m]，j∈[1,n]}。

基于線段Voronoi圖[21]和點與線段之間的最近距離[22]的定義，本章進一步給出障礙線段反k最近區域查詢、線段區域最近距離和線段區域Voronoi圖等定義。

定義1（線段障礙最近距離）已知查詢線段L和障礙物O，點li,lj,l∈L，點oi,oj,o∈O，dist(l,o)表示點l到點o的距離，則線段L與線段O的最近鄰距離為dist(L,O)={dist(li,oi),dist(li,oi)≤dist(lj,oj)}。

定義2（線段與區域的可視性）給定一個查詢線段l，區域r∈Rs和障礙物集O，l和r是可視的當且僅當l的兩端點與r形成的不規則圖形與O中任何障礙都不相交，即o∈O，[l,r]?o=? 。

定義3（線段區域最近距離）障礙空間中存在查詢線段l，設其左右兩端分別為m和n。若線段與區域可視，則線段與區域的歐式距離即為最短可視距離distv(l,r)，則障礙距離等于線段與區域的最短可視化距離disto(l,r)=distv(l,r)；若兩線段之間完全不可視，則線段區域之間的障礙距離為線段區域繞過障礙物的最短距離。即disto(l,r)=min{dist(m,oi1)+dist(r,oi1)，dist(n,oi2)+dist(r,oi2)}。

定義4（障礙線段反k最近區域查詢，OLRkNR）在障礙空間中，給定一查詢線段l，互不相交的生成區域集合Rs={r1,r2,…,rn}和一個整數k，當一個對象r∈Rs在Rs上的kNN的結果包括L中的任意一個時，r是OLRkNR(Rs,L,k)的一個結果，具體形式為：OLRkNR(Rs,L,k)={?l∈L,?r∈Rs|l∈kNN(l,k,Rs)}。

定義5（線段區域Voronoi圖，line region Voronoi diagram，LRVD）給定一組互不相交的生成區域集合Rs={r1,r2,…,rn}和生成線段L={l1,l2,…,lm}，節點集合P={p1,p2,…,pi}，邊的集合E={e1,e2,…,ek}。令rj為不同于ri的生成區域，lj為不同于li的生成線段，線段區域Voronoi圖將平面分成若干區域，則線段li或區域ri所在的區域稱為LRVP（line region voronoi portion）。則LRVP(li,ri)可以形式化表示為：LRVP(li,ri)={l,r|r∈Rs,l∈L,dist(r,ri)≤dist(r,rj),dist(l,li)≤dist(l,lj)}。

若區域集合Rs中的每一個區域和數據線段集中的線段L都可以生成一個LRVP，則LRVD由n+m個LRVP組成，因此可以定義LRVD:LRVD(Rs,L)={LRVP(r1),LRVP(r2),…,LRVP(rn),LRVP(l1),LRVP(l2),…,LRVP(lm)}。

由線段區域Voronoi圖的結構和定義可以得出以下性質：

性質1（最近鄰特性）生成區域ri的最近鄰必存在于與LRVP(ri)鄰接的LRVP中。

性質2（線性特性）令生成區域ri，生成線段li和Voronoi棱的數量en，則en≤3(ri+li)-6。

根據區域Voronoi圖的定義及性質，進一步提出了線段區域Voronoi圖生成算法，如算法1所示。

算法1Create_LRVD(L,Rs,E,N)

輸入：區域集Rs，邊集合E，節點集合N，數據線段集L。

輸出：LRVD。

begin：

1.根據數據線段集L生成線段Voronoi圖;

2. 令l∈L，使l′//l且l′交ri于點q，設l′的左右端點分別為a、b;

3.過節點n做l′的垂線，垂足為o;

4.ifo∈rithen

5.dist(ni)=dist(ni,o);

6.elseo?ri

7.dist(ni)=dist(ni,q);

8.end if

9.ifdist(ni,ri)

10.ni∈LRVP(ri);

11.end if

12.for each(ni,nj)∈E

13. if(ri?rj=null)then

14. 計算LRVP(ri)與LRVP(rj)邊界點

15.h=(ni,nj|dist(ni)-dist(nj)-dist(ni,nj)/2)的位置;

16.end if

17.end for

18.return LRVD;

End

定理1算法Create_LRVD能正確地求出LRVD，其時間復雜度為O(nlgn)。

證明（正確性）令dist(ni,ri)為節點ni到區域ri的最短距離，其中ni存在于LRVP(li)中。當k=1時，有dist(ni,r1)≤dist(ni,ri)，則節點ni的反向最近區域RNR（reverse nearest region）為r1，即線段li的RNR為區域r1。當k>1時，令dist(ni,rk)≤dist(ni,ri)，0

（時間復雜度分析）該算法首先生成線段Voronoi圖的時間復雜度為O(nlgn)。for循環的執行次數為n次，時間復雜度為O(n)。該算法總的時間復雜度為O(nlgn+n)。故該算法的時間復雜度為O(nlgn)。 □

3 障礙環境下線段反k最近區域查詢方法

3.1 約減數據集

數據集包含區域集、障礙物集。基于Voronoi圖的性質和結構提出了定理2。根據定理2，去掉非候選者集合，獲得候選集合。該過程減少了大量的數據集合，縮小了查詢范圍。

定理2給定一組區域集Rs和查詢線段l，則計算出到查詢線段l經過的最少區域個數小于或等于k的區域ri存在于候選集中。

證明令count(r,l)為區域r到查詢線段l需要經過最少的區域個數。當k=1時，相當于查詢線段l的反向最近區域（RNR），則l的RNR的區域r是查詢線段l的Voronoi鄰居，即區域r滿足count(r,l)≤1；當k≥1時，令count(ri,l)≤i,0≤i≤k，則count(rk+1,l)≤k+1。根據線段Voronoi圖[21]定義可知，rk+1是ri∈{r1,r2,…,rk}中的一個Voronoi鄰居。即：count(rk+1,l)≤max(count(r,ri)+1)≤k+1，故定理2成立。 □

根據定理2，本節給出算法OLRkNR_Reduct，其主要思想為：將查詢線段l的前k級鄰接區域放入候選集Rl中，而高于k級的鄰接區域則約減。該過程首先根據障礙物集合生成線段Voronoi圖，判定l的位置。最后依據l的位置進行數據區域約減。

基于以上討論，本文進一步給出了約減數據集算法，如算法2所示。

算法2OLRkNR_Reduct(l,Rs,O,k)

輸入：查詢線段l，區域集Rs，障礙物集O，k值。

輸出：約減的區域候選集Rl。

begin:

1.Rl←null;/*初始化候選集Rl為空*/

2.Create_LRVD(l?O);

3.fori=1tokdo

4.ifl∈LRVP(ri)then

5.Rl←Rl+ri;/*將l的第一個反向最近區域加入到Rl中*/

6.end if

7.else ifri與l是鄰接的then

8.Rl←Rl+ri;

9.end if

10.ifcount(ri,l)≤kthen

11.Rl←Rl+ri;

12.end if

13.end for

14.returnRl;

End

定理3算法OLRkNR_Reduct是正確的，其時間復雜度為O(nlgn)。

證明（正確性）根據定理1，已經證明創建LRVD是正確的。假設查詢線段為l，令該算法返回的區域為ri，且ri不是l的反向最近區域對象。令rk(l)為線段l的反向最近區域對象，dist(rk(l),l)表示l的RNR的距離。如果ri不是l的RNR，則必有dist(rk(l),l)

（時間復雜度分析）該算法生成線段Voronoi圖的時間復雜度為O(nlgn)。for循環的執行過程是k次，k遠小于n，故算法2的時間復雜度為O(nlgn)。□

3.2 剪枝過程

該過程主要對候選集Rl進行過濾，剪枝掉大量非候選集，獲得更精確的候選集。為了有效進行剪枝，提出了定理4、定理5。

定理4令區域r在查詢線段l的最近鄰的第n級鄰接生成區域中，且r到l的路徑上經過的區域個數小于等于n，即sumcount(r,l)≤n。若sumcount(r,l)≥k，則區域r被剪枝。

證明令ri為區域r到查詢線段l之間經過的若干對象。當區域r到查詢線段l之間不存在障礙物時，則可以知道ri到l一定比r到l的歐氏距離近；當區域r到查詢線段l之間存在障礙物時，那么ri到l的距離也一定比r到l的距離近。當k=1時，顯然dist(ri,l)≤dist(r,l)。當k>1時，ri的個數不小于k個，那么r的k最近鄰不包含l，即sumcount(r,l)≥k時，r一定不是候選集里的對象。 □

定理5給定任意r∈Rl，若r的Voronoi鄰居都被剪枝了，則區域r也被剪枝。

證明令r為候選集Rl中的任意區域且r的Voronoi鄰居都被剪枝。由線段Voronoi圖的性質可知，查詢線段l到r一定會經過r的Voronoi鄰居rv。若無障礙無環境下l到ri之間的區域數目為NoObs_Count(rv,l)≥k，因此NoObs_Count(r,l)≥k+1≥k。由定理4可知，區域r被剪枝。 □

根據定理4、定理5，進一步給出了剪枝算法Prune_Neighbor，如算法3所示。

算法3Prune_Neighbor(Rl,l)

輸入：候選集Rl，查詢線段l。

輸出：剪枝后的候選集Rl。

1.Rl←null;/*初始化候選集為空*/

2.Rl←OLRkNR_Reduct( )l,Rs,O,k;

3.PruneFlag=true;

4.for eachrjinRldo

5.for eachrj∈VN(ri)do

6. ifrj∈Rlthen

7. PruneFlag=false;

8. end if

9.end for

10.end for

11.if PruneFlag=true then

12.Rl←Rl-ri;

13.end if

14.end for

15.returnRl;

End

定理6算法Prune_Neighbor是正確的，其時間復雜度為O(nlgn)。

證明（正確性）該算法首先調用了算法2，定理3已經被證明是正確的。然后依據PruneFlag為true來標記對象是需要剪枝的。判斷區域rj是否在VN(ri)中，如果不在則直接剪枝掉。該算法可以正確找到剪枝后的候選集合。故該算法是正確的。

（時間復雜度分析）該算法執行算法2的時間復雜度為O(nlgn)。執行兩個嵌套for循環的最壞時間復雜度為O(mn)（m遠小于n），故該算法的時間復雜度為O(nlgn+mn)，化簡為O(nlgn)。 □

3.3 精煉過程

本文提出的精煉過程主要針對候選集Rl進行處理，得到最后的查詢結果。首先依據Voronoi圖的性質與定理提出了定理7。根據定理7對候選集中的區域進行處理。該過程可得到更精確的候選集。

定理7給定查詢線段l，區域r∈Rl，區域r的質心為m。當查詢線段l與r是可視的，則以查詢線段l的中點pmid為圓心，以diste(pmid,m)為半徑畫圓，將判定圓內r可視的數據點個數設為sum_regions，如果sum_regions≥k，則r被剪枝。當查詢線段l與r是不可視的，以查詢線段l的中點pmid為圓心，以disto(pmid,m)為半徑畫圓。同理，如果sum_regions≥k，則r被剪枝。

證明（1）當r∈Rl且r對查詢線段l可視時，首先設置OLRkNR中的k值為2。如圖1所示，以點pmid為圓心，以dist(pmid,m1)為半徑畫圓。其中，pmid為線段l的中點，m1為區域r3的質心。則由圖可看出，在判定圓中的區域有{r1,r2}，因此sum_regions=2=k，顯然r3的2NN是{r1,r2}，不包含查詢線段l，則查詢線段l的RkNR一定不包含r3，則r3被剪枝。

Fig.1 Example of proof 1 based on theorem 7圖1 基于定理7證明情況1的示例

（2）當r∈Rl且r對查詢線段l1不可視時，如圖2所示。以查詢線段l1的中點pmid為圓心，以disto(pmid,m1)為半徑畫圓，則在判定圓中的區域有{r1,r2,r4}且對查詢線段l1都是可視的，則sum_count=3。當k=3時，顯然r3的3NN是{r1,r2,r4}，不包含線段l1。當k<3時，區域{r1,r2,r4}到r3的距離一定小于查詢線段l1到r3的距離，故r3的kNN是{r1,r2,r4}中的k個，一定不包含查詢線段l1。故查詢線段l1的RkNR一定不包含區域r3，因此將r3剪枝。 □

Fig.2 Example of proof 2 based on theorem 7圖2 基于定理7證明情況2的示例

根據定理7，提出了精煉算法Refine_OLRkNR，該方法查看區域集Rs中的ri和查詢線段l。當r與l之間有大于k個無障礙物的對象，那么r被剪枝。

基于以上論述，進一步給出了精煉算法，如算法4所示。

算法4Refine_OLRkNR(Rl,l,O,k)

輸入：候選集Rl，查詢線段l，障礙物集O，OLRkNR中的k值。

輸出：約減的候選集Rl。

begin:

1.Rl←null;/*初始化候選集為空*/

2.Rl←Prune_Neighbor(Rl,l);

3.sumcount=0;

4.令m為區域r的質心，pmid為查詢線段l的中點;

5.令C(r)以dist(pmid,m)為半徑的圓

6.for eachriinRldo

7.for eachrjinRl?C(r)do

8. ifrj與l之間無障礙物then

9.sumcount←sumcount+1;

10. end if

11. else ifrj與l存在障礙物且大于kthen

12.Rl←Rl-r;

13. end if

14.end for

15.end for

16.returnRl;

End

定理8算法Refine_OLRkNR是正確的，其算法復雜度為O(nlgn)。

證明（正確性）該算法首先調用算法3，根據定理6可知，算法3是正確的。然后對于候選集中的每個區域r，以區域r中的質心m為圓心。令查詢線段中點pmid，則dist(pmid,m)為半徑的圓C(r)。如果在候選集中的區域r也在這個圓中，那么判斷l與r之間是否存在障礙物。若對于r與l之間有多于k個障礙物，則r被剪枝。故該算法是正確的。

（時間復雜度分析）該算法執行算法Prune_Neighbor的時間復雜度是O(nlgn)，執行兩個嵌套for循環的最壞時間復雜度為O(nlgn)，故該算法的時間復雜度為O(2nlgn)，化簡為O(nlgn)。 □

4 實驗與分析

本章通過實驗對算法Refine_OLRkNR進行性能分析。由于已有的研究成果無法直接處理障礙環境下的線段反k最近區域查詢問題，為了得到比較算法，分別對文獻[20]所提的RkNNobs算法、文獻[23]提出的LNN_Search算法以及文獻[24]提出的STA_RVLRkNN（static_road voronoi line reverseknearest neighbor）算法為基礎，將這3種算法進行適當的調整。根據文獻[20]設計了第一個較為基礎的算法RkNNobs_Basic，將該算法中的輸入查詢點、障礙物集合調整為線段輸入，將對象點集合調整為不規則圖形輸入。文獻[23]設計了第二個基礎的算法LNN_Basic，反復調用LNN_Search算法，并在Voronoi圖中隨機生成區域集合。根據文獻[24]設計了RVLRkNN_Basic算法，在Voronoi圖中隨機生成區域集合并在線段集合中隨機設定為障礙集合。

本實驗環境設置：2.0GHzCPU，4GB內存，500GB硬盤，Windows 7操作系統。實驗采用的數據是美國舊金山和加州的路網信息[25]，該實驗數據集包含1955206個節點，2766607條無向邊，其中交叉點和端點由節點表示，連接這些交叉點或道路端點則由無向邊表示。實驗中，對數據分布進行了適當調整，障礙集O和區域集Rs是由隨機生成器產生的均勻分布的線段以及不規則圖形數據。此外，用A表示子區域占整個路網的百分比。參數F表示邊的權值與實際長度的偏離程度，F=權值/歐氏距離。在默認情況下，每次查詢5的倍數個查詢區域，分布在A=5%的路網中，目標區域的密度P=0.05，參數F=2。實驗測試的指標為CPU時間、I/O代價影響以及準確率，并取200次查詢的平均結果。

如圖3所示，首先分析k值對CPU時間的影響。實驗采用的是真實數據集，查詢線段數量為50，區域數量為5000，障礙物數量為1000。圖3給出了4種算法的CPU時間隨著k值變化的對比結果。隨著k值的不斷變大，算法的CPU時間均呈上升趨勢。LNN_Basic算法需要對區域集中的每個區域都計算它的kNN，隨著k的增加，造成了搜索區域大量重疊的情況，從而使得查詢時間較長。RkNNobs_Basic算法將空間分為6等份，然而某些區域可能橫跨兩個空間，則會造成搜索區域的重疊，降低了查詢性能。RVLRkNN_Basic算法并不能優化障礙物集合，這使得k值在增加時，搜索過程中障礙物的數量會增加，降低了查詢速度。而本文提出的OLRkNR查詢算法在約減數據集過程中就排除了大量的非候選數據集，之后又通過剪枝過程和精煉過程得到了精確的查詢結果，有效縮小了查詢范圍。因此查詢所用時間比其他3組對比算法要少。

Fig.3 Effect of k on CPU time圖3 k值對CPU時間的影響

進一步分析k值的變化對算法I/O代價的影響。如圖4所示，3種對比算法的I/O代價隨著k值的增長，上升趨勢比較顯著，而OLRkNR算法相對來說I/O代價趨勢較為平緩。這是因為LNN_Basic算法需要計算每一條線段的線段最近區域，隨著k值的增加算法在查詢過程中所要訪問的區域也逐漸增多，從而造成算法的I/O代價較高。RkNNobs_Basic算法在將空間劃分為6等份后，隨著k值的增加，在查詢過程中重復搜索的區域也會變多，這就造成了算法的I/O代價升高。RVLRkNN_Basic算法隨著k值的逐漸增加，搜索區域中的障礙物也會增加，這也會造成I/O代價較高。對于OLRkNR算法，由于在數據集約減過程中將大量的非候選集過濾掉，又通過剪枝過程得到了更精確的候選集，因此降低了查詢算法的I/O代價。

Fig.4 Effect of k on I/O cost圖4 k值對I/O代價的影響

在其他條件不變的情況下，實驗設定k=15，障礙物數量為1000，區域數量為5000。測試在不同數量的查詢線段環境下對算法CPU時間的影響。如圖5所示，這4組算法的CPU時間均隨著查詢線段數量增加呈上升趨勢。但本文所提算法OLRkNR的上升趨勢較為平緩，而其他3組算法的變化在達到一定程度時上升迅速。這是由于OLRkNR算法有效利用過濾過程和剪枝策略，提高了查詢效率。而LNN_Basic算法隨著查詢線段增加，所要訪問的區域數量也隨之增加，這樣浪費了大量的時間。RVLRkNN_Basic算法對查詢線段集中每條線段都要搜索它的kLNR（kline nearest region），從而降低了查詢效率。RkNNobs_Basic算法隨著查詢線段數量增加，區域重疊現象嚴重，這種情況會使CPU時間增加。故在其他條件相同時，只考慮對CPU時間的影響，OLRkNR算法較優。

Fig.5 Effect of query lines number on CPU time圖5 查詢線段數量對CPU時間的影響

進一步分析不同數量的查詢線段對I/O代價的影響。如圖6所示，4組算法的I/O代價呈上升趨勢，OLRkNR算法上升趨勢較其他3組對比算法平緩。這是因為OLRkNR算法在過濾過程篩選掉大量非候選者，降低了I/O代價。故其他條件相同時，只考慮I/O代價的影響，OLRkNR算法性能較優。

Fig.6 Effect of query lines number on I/O cost圖6 查詢線段數量對I/O代價的影響

Fig.7 Effect of region set size on CPU time圖7 區域集規模對CPU時間的影響

圖7給出了區域集規模對CPU時間的影響。實驗設定k=15，查詢線段數量為50，障礙物數量為1000。從圖中可以看出隨著區域集數量的增加，4種算法的CPU時間均呈現上升趨勢，但本文提出的OLRkNR算法的上升趨勢較為平緩，其余3種對比算法的變化趨勢比較顯著。這是由于OLRkNR算法利用了剪枝過程，縮小了查詢范圍，從而降低了查詢時間。對于LNN_Basic算法來說，該算法需要對數據集中的每個區域進行搜索，浪費大量時間，因此它的上升趨勢最為明顯。故在其他條件相同時，只考慮CPU時間的影響，OLRkNR算法較優。

Fig.8 Effect of region set size on I/O cost圖8 區域集規模對I/O代價的影響

在實驗設定條件不變的情況下，進一步測試在不同大小的區域集環境下對算法I/O代價的影響，實驗結果如圖8所示。從圖中可以看出OLRkNR算法的變化趨勢較為緩慢，而其他3組對比算法增長變化的趨勢較為明顯。這是因為LNN_Basic算法中需要計算每一區域的k級最近鄰，由于區域集數量越多，造成查詢過程中無關數據訪問量越多，從而導致I/O代價不斷變大。RVLRkNN_Basic算法隨著區域數量增多，障礙物的搜索數量也逐漸增多，則會造成算法I/O代價較高。RkNNobs_Basic算法可以將空間分成6等份，則在區域集數量增多的情況下，搜索區域頻繁重疊的現象也會增加，使得算法I/O代價升高。因此在其他條件不變的情況下，只考慮對I/O代價的影響，OLRkNR算法更優。

接下來測試障礙物數量對算法CPU時間的影響。實驗設定k=15，查詢線段數量為50，區域數量為5000。實驗結果如圖9所示，4種算法的CPU時間隨著障礙物的增加均有所增加。OLRkNR算法受障礙物數量改變的影響較小，這是因為算法中有針對障礙物剪枝過程，在查詢過程中只需要考慮有效障礙物對查詢的影響即可，減少查詢的運行時間。

Fig.9 Effect of obstacles number on CPU time圖9 障礙物數量對CPU時間的影響

改變障礙物數量測試4種算法隨著障礙物數量增加I/O代價變化情況。如圖10所示，3組對比算法I/O代價增幅較大。這是因為LNN_Basic算法需要對數據集中的每個區域進行搜索，浪費大量時間，所以它的上升趨勢最為明顯。RVLRkNN_Basic算法隨著障礙物數量的增多，它所要搜索的數據就會增加，那么就會造成I/O代價升高。RkNNobs_Basic算法將數據空間分成6等份，那么隨著障礙物增加，重疊區域就會增加，這樣就造成I/O代價逐漸增加。故OLRkNR算法較優。

Fig.10 Effect of obstacles number on I/O cost圖10 障礙物數量對I/O代價的影響

5 結束語

本文提出了障礙環境下的線段反k最近區域查詢方法。解決了在障礙環境之下的線段到區域的近鄰問題。本文的查詢過程主要分為數據約減階段、剪枝過程以及精煉過程。在數據約減過程中，結合線段Voronoi圖的定義與性質，障礙環境下的線段最近區域定義以及線段障礙距離的定義，提出了針對區域集合和障礙物集合的剪枝策略，給出了相應的剪枝算法。在精煉過程中，主要針對剪枝過程后的數據候選集進行篩選，得到更為精確的查詢結果，并給出了相應的精煉定理和算法。通過實驗證明本文所提的算法具有較高的效率。未來研究重點集中在路網環境下的組k最近區域查詢方法。