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

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

1 引言

近年來(lái)，隨著智能識(shí)別系統(tǒng)、地理信息系統(tǒng)、交通網(wǎng)絡(luò)系統(tǒng)等的廣泛應(yīng)用，空間數(shù)據(jù)查詢技術(shù)具有越來(lái)越重要的作用。近鄰查詢是空間數(shù)據(jù)庫(kù)中的重要查詢類型。近鄰查詢包括許多種類：最近鄰[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）查詢等，研究成果解決了最近鄰查詢領(lǐng)域的一系列重要問(wèn)題。

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

國(guó)內(nèi)外對(duì)無(wú)障礙空間下的kNN查詢和RkNN查詢以及障礙空間的kNN和RkNN查詢進(jìn)行了一些重要研究。針對(duì)于無(wú)障礙空間的kNN查詢問(wèn)題，文獻(xiàn)[10]中為了有效查詢和更新給定點(diǎn)的最近鄰，研究了基于空間網(wǎng)格的Voronoi圖的方法，并提出了相關(guān)算法。文獻(xiàn)[11]進(jìn)一步考慮查詢結(jié)果的可用性，制定一個(gè)新的查詢類型MkDNN（movingkdynamic nearest neighbor），并且提出了一種增量維護(hù)k多樣性最近鄰算法。文獻(xiàn)[12]利用Voronoi圖預(yù)計(jì)算的優(yōu)勢(shì)，可以解決kNN查詢，并提高了用戶的查詢效率。針對(duì)無(wú)障礙空間的反向k最近鄰（RkNN）查詢問(wèn)題，文獻(xiàn)[13]提出了反向最近鄰的搜索方法，考慮反方向的查詢對(duì)象和目標(biāo)對(duì)象之間的位置。文獻(xiàn)[14]提出了基于距離的方法可以在高維環(huán)境中產(chǎn)生更多的對(duì)比離群分?jǐn)?shù)。采用經(jīng)典的k-NN的評(píng)價(jià)方法，提出了基于無(wú)監(jiān)督距離的離群點(diǎn)檢測(cè)中的反向最近鄰。文獻(xiàn)[15]提出了一種新的剪枝方法，該方法使用了一個(gè)多邊形近似未被剪枝的區(qū)域。

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

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

2 定義及性質(zhì)

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

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

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

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

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

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

定義5（線段區(qū)域Voronoi圖，line region Voronoi diagram，LRVD）給定一組互不相交的生成區(qū)域集合Rs={r1,r2,…,rn}和生成線段L={l1,l2,…,lm}，節(jié)點(diǎn)集合P={p1,p2,…,pi}，邊的集合E={e1,e2,…,ek}。令rj為不同于ri的生成區(qū)域，lj為不同于li的生成線段，線段區(qū)域Voronoi圖將平面分成若干區(qū)域，則線段li或區(qū)域ri所在的區(qū)域稱為L(zhǎng)RVP（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)}。

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

由線段區(qū)域Voronoi圖的結(jié)構(gòu)和定義可以得出以下性質(zhì)：

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

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

根據(jù)區(qū)域Voronoi圖的定義及性質(zhì)，進(jìn)一步提出了線段區(qū)域Voronoi圖生成算法，如算法1所示。

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

輸入：區(qū)域集Rs，邊集合E，節(jié)點(diǎn)集合N，數(shù)據(jù)線段集L。

輸出：LRVD。

begin：

1.根據(jù)數(shù)據(jù)線段集L生成線段Voronoi圖;

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

3.過(guò)節(jié)點(diǎn)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. 計(jì)算LRVP(ri)與LRVP(rj)邊界點(diǎn)

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，其時(shí)間復(fù)雜度為O(nlgn)。

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

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

3 障礙環(huán)境下線段反k最近區(qū)域查詢方法

3.1 約減數(shù)據(jù)集

數(shù)據(jù)集包含區(qū)域集、障礙物集?；赩oronoi圖的性質(zhì)和結(jié)構(gòu)提出了定理2。根據(jù)定理2，去掉非候選者集合，獲得候選集合。該過(guò)程減少了大量的數(shù)據(jù)集合，縮小了查詢范圍。

定理2給定一組區(qū)域集Rs和查詢線段l，則計(jì)算出到查詢線段l經(jīng)過(guò)的最少區(qū)域個(gè)數(shù)小于或等于k的區(qū)域ri存在于候選集中。

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

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

基于以上討論，本文進(jìn)一步給出了約減數(shù)據(jù)集算法，如算法2所示。

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

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

輸出：約減的區(qū)域候選集Rl。

begin:

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

2.Create_LRVD(l?O);

3.fori=1tokdo

4.ifl∈LRVP(ri)then

5.Rl←Rl+ri;/*將l的第一個(gè)反向最近區(qū)域加入到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是正確的，其時(shí)間復(fù)雜度為O(nlgn)。

證明（正確性）根據(jù)定理1，已經(jīng)證明創(chuàng)建LRVD是正確的。假設(shè)查詢線段為l，令該算法返回的區(qū)域?yàn)閞i，且ri不是l的反向最近區(qū)域?qū)ο?。令rk(l)為線段l的反向最近區(qū)域?qū)ο?，dist(rk(l),l)表示l的RNR的距離。如果ri不是l的RNR，則必有dist(rk(l),l)

（時(shí)間復(fù)雜度分析）該算法生成線段Voronoi圖的時(shí)間復(fù)雜度為O(nlgn)。for循環(huán)的執(zhí)行過(guò)程是k次，k遠(yuǎn)小于n，故算法2的時(shí)間復(fù)雜度為O(nlgn)。□

3.2 剪枝過(guò)程

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

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

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

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

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

根據(jù)定理4、定理5，進(jìn)一步給出了剪枝算法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是正確的，其時(shí)間復(fù)雜度為O(nlgn)。

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

（時(shí)間復(fù)雜度分析）該算法執(zhí)行算法2的時(shí)間復(fù)雜度為O(nlgn)。執(zhí)行兩個(gè)嵌套for循環(huán)的最壞時(shí)間復(fù)雜度為O(mn)（m遠(yuǎn)小于n），故該算法的時(shí)間復(fù)雜度為O(nlgn+mn)，化簡(jiǎn)為O(nlgn)。 □

3.3 精煉過(guò)程

本文提出的精煉過(guò)程主要針對(duì)候選集Rl進(jìn)行處理，得到最后的查詢結(jié)果。首先依據(jù)Voronoi圖的性質(zhì)與定理提出了定理7。根據(jù)定理7對(duì)候選集中的區(qū)域進(jìn)行處理。該過(guò)程可得到更精確的候選集。

定理7給定查詢線段l，區(qū)域r∈Rl，區(qū)域r的質(zhì)心為m。當(dāng)查詢線段l與r是可視的，則以查詢線段l的中點(diǎn)pmid為圓心，以diste(pmid,m)為半徑畫(huà)圓，將判定圓內(nèi)r可視的數(shù)據(jù)點(diǎn)個(gè)數(shù)設(shè)為sum_regions，如果sum_regions≥k，則r被剪枝。當(dāng)查詢線段l與r是不可視的，以查詢線段l的中點(diǎn)pmid為圓心，以disto(pmid,m)為半徑畫(huà)圓。同理，如果sum_regions≥k，則r被剪枝。

證明（1）當(dāng)r∈Rl且r對(duì)查詢線段l可視時(shí)，首先設(shè)置OLRkNR中的k值為2。如圖1所示，以點(diǎn)pmid為圓心，以dist(pmid,m1)為半徑畫(huà)圓。其中，pmid為線段l的中點(diǎn)，m1為區(qū)域r3的質(zhì)心。則由圖可看出，在判定圓中的區(qū)域有{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）當(dāng)r∈Rl且r對(duì)查詢線段l1不可視時(shí)，如圖2所示。以查詢線段l1的中點(diǎn)pmid為圓心，以disto(pmid,m1)為半徑畫(huà)圓，則在判定圓中的區(qū)域有{r1,r2,r4}且對(duì)查詢線段l1都是可視的，則sum_count=3。當(dāng)k=3時(shí)，顯然r3的3NN是{r1,r2,r4}，不包含線段l1。當(dāng)k<3時(shí)，區(qū)域{r1,r2,r4}到r3的距離一定小于查詢線段l1到r3的距離，故r3的kNN是{r1,r2,r4}中的k個(gè)，一定不包含查詢線段l1。故查詢線段l1的RkNR一定不包含區(qū)域r3，因此將r3剪枝。 □

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

根據(jù)定理7，提出了精煉算法Refine_OLRkNR，該方法查看區(qū)域集Rs中的ri和查詢線段l。當(dāng)r與l之間有大于k個(gè)無(wú)障礙物的對(duì)象，那么r被剪枝。

基于以上論述，進(jìn)一步給出了精煉算法，如算法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為區(qū)域r的質(zhì)心，pmid為查詢線段l的中點(diǎn);

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

6.for eachriinRldo

7.for eachrjinRl?C(r)do

8. ifrj與l之間無(wú)障礙物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是正確的，其算法復(fù)雜度為O(nlgn)。

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

（時(shí)間復(fù)雜度分析）該算法執(zhí)行算法Prune_Neighbor的時(shí)間復(fù)雜度是O(nlgn)，執(zhí)行兩個(gè)嵌套for循環(huán)的最壞時(shí)間復(fù)雜度為O(nlgn)，故該算法的時(shí)間復(fù)雜度為O(2nlgn)，化簡(jiǎn)為O(nlgn)。 □

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

本章通過(guò)實(shí)驗(yàn)對(duì)算法Refine_OLRkNR進(jìn)行性能分析。由于已有的研究成果無(wú)法直接處理障礙環(huán)境下的線段反k最近區(qū)域查詢問(wèn)題，為了得到比較算法，分別對(duì)文獻(xiàn)[20]所提的RkNNobs算法、文獻(xiàn)[23]提出的LNN_Search算法以及文獻(xiàn)[24]提出的STA_RVLRkNN（static_road voronoi line reverseknearest neighbor）算法為基礎(chǔ)，將這3種算法進(jìn)行適當(dāng)?shù)恼{(diào)整。根據(jù)文獻(xiàn)[20]設(shè)計(jì)了第一個(gè)較為基礎(chǔ)的算法RkNNobs_Basic，將該算法中的輸入查詢點(diǎn)、障礙物集合調(diào)整為線段輸入，將對(duì)象點(diǎn)集合調(diào)整為不規(guī)則圖形輸入。文獻(xiàn)[23]設(shè)計(jì)了第二個(gè)基礎(chǔ)的算法LNN_Basic，反復(fù)調(diào)用LNN_Search算法，并在Voronoi圖中隨機(jī)生成區(qū)域集合。根據(jù)文獻(xiàn)[24]設(shè)計(jì)了RVLRkNN_Basic算法，在Voronoi圖中隨機(jī)生成區(qū)域集合并在線段集合中隨機(jī)設(shè)定為障礙集合。

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

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

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

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

Fig.4 Effect of k on I/O cost圖4 k值對(duì)I/O代價(jià)的影響

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

Fig.5 Effect of query lines number on CPU time圖5 查詢線段數(shù)量對(duì)CPU時(shí)間的影響

進(jìn)一步分析不同數(shù)量的查詢線段對(duì)I/O代價(jià)的影響。如圖6所示，4組算法的I/O代價(jià)呈上升趨勢(shì)，OLRkNR算法上升趨勢(shì)較其他3組對(duì)比算法平緩。這是因?yàn)镺LRkNR算法在過(guò)濾過(guò)程篩選掉大量非候選者，降低了I/O代價(jià)。故其他條件相同時(shí)，只考慮I/O代價(jià)的影響，OLRkNR算法性能較優(yōu)。

Fig.6 Effect of query lines number on I/O cost圖6 查詢線段數(shù)量對(duì)I/O代價(jià)的影響

Fig.7 Effect of region set size on CPU time圖7 區(qū)域集規(guī)模對(duì)CPU時(shí)間的影響

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

Fig.8 Effect of region set size on I/O cost圖8 區(qū)域集規(guī)模對(duì)I/O代價(jià)的影響

在實(shí)驗(yàn)設(shè)定條件不變的情況下，進(jìn)一步測(cè)試在不同大小的區(qū)域集環(huán)境下對(duì)算法I/O代價(jià)的影響，實(shí)驗(yàn)結(jié)果如圖8所示。從圖中可以看出OLRkNR算法的變化趨勢(shì)較為緩慢，而其他3組對(duì)比算法增長(zhǎng)變化的趨勢(shì)較為明顯。這是因?yàn)長(zhǎng)NN_Basic算法中需要計(jì)算每一區(qū)域的k級(jí)最近鄰，由于區(qū)域集數(shù)量越多，造成查詢過(guò)程中無(wú)關(guān)數(shù)據(jù)訪問(wèn)量越多，從而導(dǎo)致I/O代價(jià)不斷變大。RVLRkNN_Basic算法隨著區(qū)域數(shù)量增多，障礙物的搜索數(shù)量也逐漸增多，則會(huì)造成算法I/O代價(jià)較高。RkNNobs_Basic算法可以將空間分成6等份，則在區(qū)域集數(shù)量增多的情況下，搜索區(qū)域頻繁重疊的現(xiàn)象也會(huì)增加，使得算法I/O代價(jià)升高。因此在其他條件不變的情況下，只考慮對(duì)I/O代價(jià)的影響，OLRkNR算法更優(yōu)。

接下來(lái)測(cè)試障礙物數(shù)量對(duì)算法CPU時(shí)間的影響。實(shí)驗(yàn)設(shè)定k=15，查詢線段數(shù)量為50，區(qū)域數(shù)量為5000。實(shí)驗(yàn)結(jié)果如圖9所示，4種算法的CPU時(shí)間隨著障礙物的增加均有所增加。OLRkNR算法受障礙物數(shù)量改變的影響較小，這是因?yàn)樗惴ㄖ杏嗅槍?duì)障礙物剪枝過(guò)程，在查詢過(guò)程中只需要考慮有效障礙物對(duì)查詢的影響即可，減少查詢的運(yùn)行時(shí)間。

Fig.9 Effect of obstacles number on CPU time圖9 障礙物數(shù)量對(duì)CPU時(shí)間的影響

改變障礙物數(shù)量測(cè)試4種算法隨著障礙物數(shù)量增加I/O代價(jià)變化情況。如圖10所示，3組對(duì)比算法I/O代價(jià)增幅較大。這是因?yàn)長(zhǎng)NN_Basic算法需要對(duì)數(shù)據(jù)集中的每個(gè)區(qū)域進(jìn)行搜索，浪費(fèi)大量時(shí)間，所以它的上升趨勢(shì)最為明顯。RVLRkNN_Basic算法隨著障礙物數(shù)量的增多，它所要搜索的數(shù)據(jù)就會(huì)增加，那么就會(huì)造成I/O代價(jià)升高。RkNNobs_Basic算法將數(shù)據(jù)空間分成6等份，那么隨著障礙物增加，重疊區(qū)域就會(huì)增加，這樣就造成I/O代價(jià)逐漸增加。故OLRkNR算法較優(yōu)。

Fig.10 Effect of obstacles number on I/O cost圖10 障礙物數(shù)量對(duì)I/O代價(jià)的影響

5 結(jié)束語(yǔ)

本文提出了障礙環(huán)境下的線段反k最近區(qū)域查詢方法。解決了在障礙環(huán)境之下的線段到區(qū)域的近鄰問(wèn)題。本文的查詢過(guò)程主要分為數(shù)據(jù)約減階段、剪枝過(guò)程以及精煉過(guò)程。在數(shù)據(jù)約減過(guò)程中，結(jié)合線段Voronoi圖的定義與性質(zhì)，障礙環(huán)境下的線段最近區(qū)域定義以及線段障礙距離的定義，提出了針對(duì)區(qū)域集合和障礙物集合的剪枝策略，給出了相應(yīng)的剪枝算法。在精煉過(guò)程中，主要針對(duì)剪枝過(guò)程后的數(shù)據(jù)候選集進(jìn)行篩選，得到更為精確的查詢結(jié)果，并給出了相應(yīng)的精煉定理和算法。通過(guò)實(shí)驗(yàn)證明本文所提的算法具有較高的效率。未來(lái)研究重點(diǎn)集中在路網(wǎng)環(huán)境下的組k最近區(qū)域查詢方法。