張麗平，郭瑩瑩，李 松，李 爽，樊瑞光

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

路網(wǎng)中線段反k最近鄰查詢研究*

張麗平+，郭瑩瑩，李 松，李 爽，樊瑞光

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

ZHANG Liping,GUO Yingying,LI Song,et al.Line reverseknearest neighbor query in road network.Journal of Frontiers of Computer Science and Technology,2017,11(6)：908-920.

為了彌補(bǔ)現(xiàn)有的研究成果無法有效地處理路網(wǎng)環(huán)境下基于線段的反k最近鄰問題的不足，提出了在路網(wǎng)環(huán)境下線段反k最近鄰查詢方法。該查詢方法主要應(yīng)用于評(píng)估查詢對(duì)象的影響范圍。根據(jù)路網(wǎng)及Voronoi圖的特點(diǎn)提出了網(wǎng)絡(luò)線段Voronoi圖的概念。在靜態(tài)數(shù)據(jù)集情況下利用網(wǎng)絡(luò)線段Voronoi圖的性質(zhì)提出了STA_RVLRkNN算法，查詢包括過濾過程和精煉過程兩大部分。進(jìn)一步，在動(dòng)態(tài)數(shù)據(jù)集的情況下提出了DYN_ RVLRkNN算法，查詢分為空間線段對(duì)象增加和刪除兩種情況，并對(duì)不同的情況給出了相應(yīng)的算法，得到查詢結(jié)果集。理論研究和實(shí)驗(yàn)表明，所提算法能有效地處理路網(wǎng)中基于線段的反k最近鄰問題。

路網(wǎng)；網(wǎng)絡(luò)線段Voronoi圖；反k最近鄰

1 引言

空間數(shù)據(jù)庫是數(shù)據(jù)庫領(lǐng)域的重要分支，它在許多領(lǐng)域都有著廣泛的應(yīng)用，例如地理信息系統(tǒng)[1]、決策支持系統(tǒng)[2]、交通路網(wǎng)系統(tǒng)[3]等。傳統(tǒng)的近鄰查詢研究主要是在歐式空間環(huán)境下進(jìn)行的，然而相較于歐式空間中的近鄰查詢而言，在路網(wǎng)環(huán)境下的最近鄰查詢更符合現(xiàn)實(shí)生活中的相關(guān)應(yīng)用。路網(wǎng)環(huán)境與歐式空間最大不同點(diǎn)在于，在路網(wǎng)中所有的查詢點(diǎn)和空間對(duì)象都局限在路網(wǎng)的路徑上，并且兩點(diǎn)之間的最短距離是最短路徑和的距離，而在歐氏空間中最短距離為兩點(diǎn)的直線距離。

近鄰查詢是空間數(shù)據(jù)庫中的重要查詢類型之一。近鄰查詢包含多種類型：最近鄰（nearest neighbor，NN）查詢[4-6]、k最近鄰（knearest neighbor，kNN）查詢[7-9]、反向最近鄰（reverse nearest neighbor，RNN）查詢[10-12]、反k最近鄰（reverseknearest neighbor，RkNN）查詢[13]等。最近鄰查詢是空間數(shù)據(jù)庫中最為傳統(tǒng)的一種查詢類型，k最近鄰查詢是最近鄰查詢更為一般化的擴(kuò)展。kNN查詢應(yīng)用的一個(gè)常見場(chǎng)景就是，交通道路上的出租車尋找離自己最近的加油站。反k最近鄰查詢研究類似于人們生活中常遇到的查找影響范圍的問題。例如，一家連鎖超市在道路網(wǎng)絡(luò)上的某一地點(diǎn)打算投資一個(gè)新的超市點(diǎn)（假設(shè)人們?cè)谫徺I商品時(shí)一般采取就近原則），那么這必然會(huì)對(duì)附近同類型的超市帶來商業(yè)上的影響，而受其影響較大的那些超市，就是反向k最近鄰查詢的結(jié)果。

近年來，在對(duì)反k最近鄰查詢問題的研究中，國內(nèi)外學(xué)者已經(jīng)提出了多種解決方案。文獻(xiàn)[14]針對(duì)移動(dòng)物體延遲更新和隱私保護(hù)等問題造成的數(shù)據(jù)的不確定性給出了有效的解決方法。另外在實(shí)際路網(wǎng)中，由于移動(dòng)數(shù)據(jù)對(duì)象的種類多種多樣，單色反向最近鄰查詢有時(shí)并不能完全滿足要求。文獻(xiàn)[15]通過PMR四叉樹索引路網(wǎng)，實(shí)現(xiàn)對(duì)路網(wǎng)的連續(xù)監(jiān)控。文獻(xiàn)[16]提出了一種基于障礙空間的反k最近鄰查詢方法，利用障礙Voronoi圖的高效剪枝方法，大幅度減少了處理點(diǎn)的個(gè)數(shù)。文獻(xiàn)[17]提出了一種基于第三方可靠服務(wù)器的方法，確保用戶在享受基于位置服務(wù)所提供的實(shí)際準(zhǔn)確答案的同時(shí)，其位置信息不被泄露。

在實(shí)際生活中探索查詢問題時(shí)，許多空間對(duì)象如果抽象成點(diǎn)進(jìn)行研究將會(huì)對(duì)查詢結(jié)果的精度造成影響。例如，山脈、河流、軌道等在研究過程中都不適合抽象為點(diǎn)。為了提升查詢的效果可以將其抽象為線段，因此文獻(xiàn)[18]提出了解決平面線段之間的最近鄰問題，以及基于線段最近鄰的概念和相關(guān)查詢算法。文獻(xiàn)[19]提出了基于移動(dòng)線段k最近鄰查詢問題。文獻(xiàn)[20]以基于線段的索引結(jié)構(gòu)（SI-樹）為基礎(chǔ)提出了新的剪枝規(guī)則，加快了查詢速度?，F(xiàn)階段在路網(wǎng)環(huán)境下的近鄰研究都是以點(diǎn)為對(duì)象進(jìn)行研究的，沒有考慮路網(wǎng)條件下基于線段的近鄰研究，且相較于歐式空間而言，路網(wǎng)環(huán)境下的研究更貼近人們的生活。因此，本文所提出的路網(wǎng)環(huán)境下線段反k最近鄰查詢問題是一個(gè)新的需要解決的問題。例如，在城市中某一大樓發(fā)生火災(zāi)事故時(shí)，為了采取一種最快捷有效的方式處理火災(zāi)事故，消防人員可以利用路網(wǎng)環(huán)境下線段的反向k最近鄰查詢技術(shù)確定受火災(zāi)影響的范圍。又如，居民在購買住房選址時(shí)，難免會(huì)考慮到高速公路或者火車軌道所帶來的噪聲影響，因此可以通過路網(wǎng)環(huán)境下線段的反向k最近鄰查詢技術(shù)判斷受噪聲影響的范圍，更好地選擇自己滿意的居住位置。

本文所提出的路網(wǎng)中線段反k最近鄰查詢方法，用于處理不相交的線段。分別討論了靜態(tài)數(shù)據(jù)集和動(dòng)態(tài)數(shù)據(jù)集兩種情況下的線段反k最近鄰查詢。靜態(tài)數(shù)據(jù)集情況下查詢分為過濾過程和精煉過程兩個(gè)階段。動(dòng)態(tài)數(shù)據(jù)情況分為數(shù)據(jù)線段的增加和刪除兩種情況，通過相對(duì)應(yīng)的算法思想對(duì)新的數(shù)據(jù)線段集進(jìn)行查詢得到新的查詢結(jié)果集。

2 基礎(chǔ)定義與性質(zhì)

定義1（線段Voronoi圖[21]）給定一組互不相交的生成線段L={l1,l2,…,ln}，每一線段的兩個(gè)端點(diǎn)已知，其中2

定義2（線段之間的最近距離[18]）已知線段L和線段K，點(diǎn)l,li,lj∈L,點(diǎn)k,ki,kj∈K,dist(l,k)表示點(diǎn)l到點(diǎn)k的距離，設(shè)線段L與線段K的最近鄰距離為dist(L,K)={dist(li,ki),dist(li,ki)≤dist(lj,kj)}。由定理可知，dist(L,K)=dist(K,L)。若兩條線段相交，則它們最近距離為0。

定義3（點(diǎn)到線段的最近距離[18]）已知點(diǎn)q和線段L，點(diǎn)li,lj∈L，設(shè)點(diǎn)q與線段L的最近距離為dist(q,L)，則dist(q,L)={dist(q,L)|dist(q,li)≤dist(q,lj)}。

定義4（線段反k最近鄰查詢）給定一個(gè)互不相交線段集L，查詢線段lq和一個(gè)整數(shù)k，在數(shù)據(jù)集L中找到集合LR，使LR中的線段到lq的距離小于到L中其他任意線段的距離，則稱LR為lq的線段反k最近鄰，具體定義形式如下：

LRkNN(LR)={li|li∈LR,1≤i≤k,d(li,lq)≤d(li,lj)}

進(jìn)一步，本文所提出的網(wǎng)絡(luò)線段Voronoi圖（network line Voronoi diagram，NLVD）如定義5所示。

定義5（網(wǎng)絡(luò)線段Voronoi圖）給定一組互不相交的生成線段集合L={l1,l2,…,ln}，節(jié)點(diǎn)集合N={n1,n2,…,ni},邊的集合E={e1,e2,…,ek}。假設(shè)lj為不同于li的生成線段，網(wǎng)絡(luò)線段Voronoi圖將平面分成若干區(qū)域，線段li所在的區(qū)域稱為NLVP，則NLVP(li)可以形式化定義為：

若線段集L中的每一個(gè)線段都能生成一個(gè)NLVP，則NLVD由n個(gè)NLVP組成，因此可以定義NLVD如下：

NLVD(L)={NLVP(l1),NLVP(l2),…,NLVP(ln)}

由網(wǎng)絡(luò)線段Voronoi圖的結(jié)構(gòu)及定義可以得出以下性質(zhì)。

性質(zhì)1（最短距離特性）兩線段之間的最短距離是線段到邊界點(diǎn)的最短距離之和，而非兩線段之間的連線距離。

性質(zhì)2（最近鄰特性）生成線段li的最近鄰必定存在于與NLVP(li)鄰接的NLVP中。

根據(jù)網(wǎng)絡(luò)線段Voronoi圖的定義及性質(zhì)，進(jìn)一步給出NLVD生成算法如算法1所示。

算法1Create_NLVD

輸入：數(shù)據(jù)線段集L，邊的集合E，節(jié)點(diǎn)集合N

輸出：NLVD

Begin

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

2.設(shè)生成線段l的左右端點(diǎn)分別為s、e;

3.過節(jié)點(diǎn)n做l的垂線，垂足為o;

4.ifo∈lithen

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

6.elseo?li

7.d(ni)=min{d(ni,s),d(ni,e)};

8.end if

9.ifd(ni,li)＜d(ni,lj)

10.ni∈NLVP(li);

11.end if

12.for each(ni,nj)∈E

13. if(li∩lj=NULL)then

14. 計(jì)算NLVP(li)與NLVP(lj)邊界點(diǎn)b=(ni,nj|d(ni)-d(nj)-d(ni,nj)/2)的位置;

15. end if

16.end for

17.return NLVD;

End

Create_NLVD算法的具體過程為：首先利用給定的數(shù)據(jù)線段集生成線段Voronoi圖，通過計(jì)算確定節(jié)點(diǎn)和邊界點(diǎn)的位置。計(jì)算節(jié)點(diǎn)ni到線段li的最短距離，從而得出ni的最近生成線段以及d(ni)。然后通過比較最短距離，可以確定ni存在于其最短生成線段所在的NLVP中。進(jìn)一步根據(jù)計(jì)算公式得出NLVP(li)與NLVP(lj)的邊界點(diǎn)位置。繼續(xù)運(yùn)行算法得到n個(gè)NLVP，從而得到NLVD。

3 路網(wǎng)環(huán)境下LRkNN查詢

根據(jù)線段集中的線段是否變化，本文提出路網(wǎng)中線段反k最近鄰查詢（RVLRkNN查詢）方法。主要分為兩部分，分別為靜態(tài)數(shù)據(jù)集情況下的RVLRkNN查詢（STA_RVLRkNN查詢）和動(dòng)態(tài)數(shù)據(jù)集情況下的RVLRkNN查詢（DYN_RVLRkNN查詢）兩類。

3.1 靜態(tài)數(shù)據(jù)集情況下RVLRkNN查詢

本節(jié)提出的路網(wǎng)中線段反k最近鄰查詢方法主要包括兩個(gè)階段，分別為過濾過程和精煉過程。首先是過濾過程，對(duì)查詢線段集進(jìn)行優(yōu)化處理，獲取較精確的候選集。然后是精煉過程，對(duì)候選集進(jìn)行精煉得到更加精確的候選集。最后排除錯(cuò)誤結(jié)果，得到正確的查詢結(jié)果集。

3.1.1 過濾過程

過濾過程的主要工作是對(duì)查詢線段進(jìn)行過濾處理，過濾掉大量非候選者，獲取較精確的線段反k最近鄰查詢候選集合。將Voronoi圖和本文提出的網(wǎng)絡(luò)線段Voronoi圖的基本性質(zhì)相結(jié)合，給出定理1和定理2，為過濾線段反k最近鄰的查詢算法提供了基礎(chǔ)理論支持。

定理1線段li為網(wǎng)絡(luò)線段Voronoi圖中NLVP(li)的生成線段，那么lq的第一個(gè)反向最近鄰為li，且對(duì)于NLVP(li)中的查詢線段的下一個(gè)最近鄰一定在與NLVP(li)鄰接的NLVP中。

Fig.1 Example of theorem 1 and theorem 2圖1 基于定理1和定理2的示例圖

證明該定理可用反證法證明。如圖1（左上角）所示，對(duì)于查詢線段lq，設(shè)其左右端點(diǎn)分別為a和b。對(duì)于線段l8，設(shè)其左右端點(diǎn)分別為x和y。對(duì)于線段l7,設(shè)其左右端點(diǎn)分別為q和p。b23和b24為NLVP(l1)和NLVP(l8)之間的邊界點(diǎn)。b31為NLVP(l7)與NLVP(l8)之間的邊界點(diǎn)。由于lq在NLVP(l1)中，從而對(duì)于查詢線段lq的1-LRNN為l1。假設(shè)lq的2-LRNN存在于與NLVP(l2)不相鄰的NLVP中，即為l7。根據(jù)點(diǎn)到線段的距離定義，求b24到lq的距離，過點(diǎn)b24做線段lq的垂線交于點(diǎn)o，則b24到lq的距離表示為d(b24,o)。由于點(diǎn)b31到線段l7的垂足不在l7上，從而點(diǎn)b31到線段l7的距離為d(b31,p)。同理點(diǎn)b24到線段l8的距離為d(b24,x)，點(diǎn)b31到線段l8的距離為d(b31,x)。根據(jù)網(wǎng)絡(luò)線段Voronoi圖的性質(zhì)，可計(jì)算出查詢線段lq到線段l7的最短路徑d(lq,l7)，即為d(lq,l7)=d(b24,o)+d(b24,b31)+d(b31,p)。同理，lq到l8的最短距離d(lq,l8)=d(b24,x)+d(b24,o)。由網(wǎng)絡(luò)線段Voronoi圖的性質(zhì)可知d(b31,p)=d(b31,x)。由于在路網(wǎng)中滿足三角不等式定理，可以得到不等式d(b31,x)+d(b24,b31)>d(b24,x)，即d(b24,o)+d(b24,b31)+d(b31,p)>d(b24,x)+d(b24,o)，從而得到d(lq,l7)>d(lq,l8)。與假設(shè)lq的下一個(gè)最近鄰在與NLVP(l2)不相鄰的NLVP中相矛盾，故原性質(zhì)成立。 □

定理2在網(wǎng)絡(luò)線段Voronoi圖中，存在鄰接生成線段li和lj，它們之間的距離記為d(li,lj)，假設(shè)查詢線段的最近鄰為li，如果有d(lq,li)>d(li,lj),則li、lj被剪枝。

證明該定理可用反證法證明。如圖1（右下角）所示，設(shè)定線段l4為查詢線段，其左右端點(diǎn)分別為h和s。線段l15是查詢線段l4的最近鄰，其左右端點(diǎn)分別為m和n，兩線段之間的最短距離用d(l4,l15)表示。同理證明定理1中的距離計(jì)算方法d(l4,l15)=d(s,b14)+d(b14,m)。存在與線段l15鄰接的線段l16，其左右端點(diǎn)分別為w和v。線段l15與線段l16之間的距離可以表示為d(l15,l16)=d(v,b32)+d(b32,m)。假設(shè)d(l4,l15)d(s,b32)+d(b14,m)存在，又因?yàn)閐(b32,b14)表示距離，一定是大于0的，所以可以對(duì)其移項(xiàng)并對(duì)不等式進(jìn)行整理得到不等式d(v,b32)>d(b14,m)-d(b32,b14)。同理可以得到d(b14,m)>d(b32,b14)。在路網(wǎng)環(huán)境下滿足三角不等式原理，因此有不等式d(m,b32)-d(b32,b14)d(m,b32)。由網(wǎng)絡(luò)線段Voronoi圖的性質(zhì)得到d(b14,m)=d(s,b14)和d(m,b32)=d(v,b32)，從而得到d(s,b14)+d(b14,m)>d(v,b32)+d(b32,m)，即d(l4,l15)>d(l15,l16)。與假設(shè)矛盾，故原性質(zhì)成立，l15、l16被剪枝。 □

本小節(jié)提出的過濾算法的主要思想為：首先通過定理1提供的理論，判斷查詢線段的位置，如果lq在NLVP(li)中，則線段li為lq的第一個(gè)反向最近鄰，將li插入到候選集中，并對(duì)li的鄰接生成線段繼續(xù)判斷，過濾掉大量非候選者。然后根據(jù)定理2，對(duì)LC中的候選線段進(jìn)一步判斷，將滿足條件的線段進(jìn)行剪枝，有效地提高了查詢算法的效率。

基于以上討論，進(jìn)一步給出過濾算法，如算法2所示。

算法2RVLRkNN_Filter(L,lq,k)

輸入：數(shù)據(jù)線段集L，查詢線段lq,k值

輸出：過濾后的候選集LC

Begin

1.Create_NLVD(L∪lq);/*創(chuàng)建網(wǎng)絡(luò)線段Voronoi圖*/

2.LC←?;/*初始化候選集為空*/

3.fori=1 tokdo

4.iflq∈NLVP(li)then

5.LC←li;/*將lq的第一個(gè)反向最近鄰加入到LC中*/

6.end if

7.elsei++

8.iflx與lq是鄰接的then

9.LC←li+lx;

10. elselx被過濾掉

11.end if

12.ifly是lq的最近鄰andd(lq,ly)>d(lx,ly)then

13.LC←LC-lx-ly;

14.end if

15.end for

16.returnLC;

End

RVLRkNN_Filter算法的具體過程為：首先以數(shù)據(jù)線段集L和查詢線段lq的并集為生成線段創(chuàng)建網(wǎng)絡(luò)線段Voronoi圖。然后根據(jù)定理1，對(duì)數(shù)據(jù)線段進(jìn)行過濾。根據(jù)定理2，對(duì)得到的候選結(jié)果做進(jìn)一步篩選，滿足條件的線段被剪枝，最后剩下為排除掉非候選者的結(jié)果集合。如圖1所示，lq存在于NLVP(l1)中，因此其1-LRNN為線段l1，它的2-LRNN一定存在于候選集{l2,l3,l9,l8}中。再根據(jù)定理2進(jìn)一步判斷，線段l3和l9滿足條件，因此被剪枝，得出候選集合為{l2,l8}。

3.1.2 精煉過程

本小節(jié)提出的精煉算法主要以過濾過程中所得到的候選集LC為對(duì)象進(jìn)行操作。首先計(jì)算查詢線段到新加入到候選集合中的生成線段的最短距離，然后對(duì)所得到的最短距離進(jìn)行比較，從而得到更精確的線段反k最近鄰的查詢結(jié)果。

為了計(jì)算查詢線段到新生成的線段的最短距離，進(jìn)一步給出定理3、定理4和定理5。

定理3在網(wǎng)絡(luò)線段Voronoi圖中，假設(shè)查詢線段lq的前兩個(gè)反向最近鄰為{li,lj}，那么NLVP(li)與NLVP(lj)一定是相鄰的，即NLVP(li)與NLVP(lj)之間存在公共邊。

證明此定理可以使用反證法證明。如果查詢線段lq到lj的最短路徑經(jīng)過NLVP(lk)，并且lk不屬于{li,lj}，lj是緊挨著li的鄰接生成線段，那么查詢線段lq到lk在NLVP(lk)中所經(jīng)過的最短路徑要比到線段lj的距離近。如圖2所示，假設(shè){l2,l3}是查詢線段lq的前兩個(gè)反向最近鄰，令從lq到l3的最短路徑為L={p,n1,n4,b3,b6,e}，它與NLVP(l4)相交于邊界點(diǎn)b3、b6。令從查詢線段lq到l4的路徑為L′={p,n1,n4,b3,s}。連接點(diǎn)s和b6，根據(jù)網(wǎng)絡(luò)線段Voronoi圖的性質(zhì)可得d(s,b6)=d(e,b6)。已知在路網(wǎng)中滿足三角不等式定理，即存在不等式d(s,b6)+d(b3,b6)>d(b3,s)，從而可得不等式d(b3,b6)+d(b6,e)>d(b3,s),即L>L′。因此線段l4比線段l3更接近lq。這與假設(shè)矛盾，故原定理成立。 □

Fig.2 Example of theorem 3圖2 基于定理3的示例圖

定理4在網(wǎng)絡(luò)線段Voronoi圖中，假設(shè) {l1,l2,…,lk}為查詢線段lq的前k個(gè)反向最近鄰，那么NLVP(l1),NLVP(l2),…,NLVP(lk)一定是相鄰的，即NLVP(l1), NLVP(l2),…,NLVP(lk)互相之間存在公共邊。

證明此定理是定理3的一般化，同理依然可以采用反證法進(jìn)行證明。假設(shè)查詢線段lq到lk的最短路徑通過NLVP(li)，并且li?{l1,l2,…,lk},那么在NLVP(li)中的最短路徑比lk更接近li。這與假設(shè){l1,l2,…,lk}為查詢線段lq的前k級(jí)鄰接生成線段相矛盾，故原定理成立。 □

定理5在網(wǎng)絡(luò)線段Voronoi圖中，對(duì)于NLVP(li)的生成線段li，li到其n級(jí)鄰接生成線段的最短距離小于到NLVP(li)的任意n+1級(jí)鄰接生成線段的距離。

證明由定理1可知，對(duì)于生成線段li而言，NLVP(li)內(nèi)任何一個(gè)查詢線段的下一個(gè)反向最近鄰一定是在與NLVP(li)相鄰的NLVP中。由網(wǎng)絡(luò)線段Voronoi圖的性質(zhì)可知，li到其所有n+1級(jí)鄰接生成線段必經(jīng)過NLVP(li)的所有n級(jí)鄰接生成線段。故li到其n級(jí)鄰接生成線段的最短距離小于到NLVP(li)任意n+1級(jí)鄰接生成線段的距離。 □

基于定理3、定理4、定理5，本小節(jié)提出的精煉算法主要思想為：首先初始化查詢結(jié)果集，調(diào)用過濾過程算法，得到候選集LC。然后利用點(diǎn)到線段的距離定義計(jì)算最短距離，并對(duì)候選集作進(jìn)一步篩選，得到最終查詢結(jié)果。

基于以上討論，進(jìn)一步給出精煉算法，如算法3所示。

算法3STA_RVLRkNN(L,lq,k)

輸入：數(shù)據(jù)線段集L，查詢線段lq,k值

輸出：線段反k最近鄰查詢結(jié)果集LR

Begin

1.LR←?;/*初始化查詢結(jié)果集為空*/

2.dist(li,lj)←?;/*初始化最短路徑為空*/

3.LC←RVLRkNN_Filter(L,lq,k);

4.while(LC!=NULL)do

5.設(shè)l的兩端點(diǎn)分別為s、e;

6.過邊界點(diǎn)bi做線段li垂直平分線垂足為o;

7.ifo∈li

8.dist(li,bi)=dist(bi,o);

9.elseo?li

10.dist(li,bi)=min{dist(bi,s),dist(bi,e)};

11.end if

12.iflx與ly是相鄰的andlx,ly∈LCthen

13.dist(lx,lq)=dist(lx,bz)+dist(bz,lq);/*其中bz為NLVP(lx)與NLVP(lq)之間的邊界點(diǎn)*/

14.dist(ly,lq)=dist(ly,bs)+dist(bs,lq);/*其中bs為NLVP(lx)與NLVP(lq)之間的邊界點(diǎn)*/

15.end if

16.compare min{dist(lx,lq)};/*比較出lx與lq之間的最小距離*/

17.ifdist(ly,lq)>dist(bs,lq)then

18.LC←LC-ly;/*從候選集中將ly刪除*/

19.else

20.LR←LC+lx;/*將線段lx添加到結(jié)果集中*/

21.end if

22.end while

23.returnLR

End

STA_RVLRkNN算法的具體過程為：首先初始化查詢結(jié)果集并調(diào)用算法2，得到候選集LC。根據(jù)定理3，最短路徑由兩部分組成，一部分為查詢線段到邊界點(diǎn)的距離，另一部分為生成線段到邊界點(diǎn)的距離。設(shè)線段li的左右端點(diǎn)分別為是s和e，過邊界點(diǎn)bi做線段li的垂直平分線，垂足為o。如果o在線段li上，則dist(li,bi)=dist(bi,o)，如果o不在線段li上，則dist(li,bi)=min{dist(bi,s),dist(bi,e)}。從而得到lq到已經(jīng)計(jì)算出的k個(gè)LRNN所在的NLVP共同邊的最短距離，最后得到精確的查詢結(jié)果集。

3.2 數(shù)據(jù)線段集合變化對(duì)查詢結(jié)果的影響

數(shù)據(jù)線段集L的變化對(duì)查詢結(jié)果會(huì)產(chǎn)生一定的影響，主要分為兩部分，即新增數(shù)據(jù)線段對(duì)查詢結(jié)果的影響，以及移除數(shù)據(jù)線段對(duì)查詢結(jié)果的影響。

3.2.1 新增數(shù)據(jù)線段對(duì)查詢結(jié)果的影響

在現(xiàn)實(shí)社會(huì)中，空間數(shù)據(jù)集中的線段對(duì)象的數(shù)量是不穩(wěn)定的。當(dāng)數(shù)據(jù)線段集新增線段時(shí)，有可能會(huì)對(duì)原有的查詢結(jié)果產(chǎn)生影響，因此本小節(jié)主要討論向查詢線段集增加數(shù)據(jù)線段時(shí)的解決方法，并提出算法DYN_ADD_RVLRkNN。根據(jù)數(shù)據(jù)線段動(dòng)態(tài)增加的情況給出實(shí)例，如圖3所示。以lq的前兩個(gè)最近鄰為例，給定數(shù)據(jù)線段集L={l1,l2,…,l26},查詢線段為lq，新增線段為l′。以s為圓心，經(jīng)計(jì)算假設(shè)l3到lq的距離最短，則以lq到l3的距離d(lq,l3)為半徑，繪制圓S，根據(jù)本文前面提到的計(jì)算方法可得d(lq,l3)=d(lq,s)。

Fig.3 Example of adding line圖3 新增線段示例圖

根據(jù)新插入的線段所在的位置，來決定是否重新進(jìn)行線段反k最近鄰查詢。新增數(shù)據(jù)線段對(duì)查詢結(jié)果的影響可分為兩種情況：新增數(shù)據(jù)線段不在圓S中，則對(duì)查詢結(jié)果集合沒有影響，直接返回上次的查詢結(jié)果集合即可。新增數(shù)據(jù)線段在圓S內(nèi)，則對(duì)查詢結(jié)果集合有影響，需將新增數(shù)據(jù)線段加入到數(shù)據(jù)線段集L中，重新計(jì)算查詢結(jié)果集合。結(jié)合圖2，在沒有加入新增線段的情況下，針對(duì)lq的前兩個(gè)反向最近鄰進(jìn)行說明，lq的1-LRNN為l2，它的2-LRNN存在于候選集{l1,l4,l6}中，經(jīng)過計(jì)算假設(shè)l1到lq的距離更近，則它的2-LRNN為{l1,l2}。如圖3所示，假設(shè)新增線段為l′，它包含于圓S中，因此對(duì)查詢結(jié)果有影響，將其插入到L中，得到新的線段集L′={l′,l1,l2,…,l26}，重新查詢得線段lq的第一個(gè)反向最近鄰為l′，經(jīng)過計(jì)算假設(shè)l3到lq的距離更近，則它的2-LRNN為{l′,l3}。

基于以上討論，給出算法4。

算法4DYN_ADD_RVLRkNN(L,lq,l′,k)

輸入：數(shù)據(jù)線段集L，查詢線段lq，新插入線段l′,k值輸出：新增數(shù)據(jù)線段后線段反k最近鄰的查詢結(jié)果

Begin

1.Lnew←?;/*初始化查詢結(jié)果為空集*/

2.LR←?;/*初始化候選集為空集*/

3.Dist(d)←?;/*初始化線段間最短距離為空集*/

4.L′←L+l′;/*將新增線段l′加入到數(shù)據(jù)線段集合L中*/

5.call STA_RVLRkNN(L,lq,k);/*得到候選集LR*/

6.d(li,lq)=d(li,bz)+d(bz,lj);/*計(jì)算線段li與lq之間的距離，其中bz為邊界點(diǎn)*/

7.Dist(d)←d(li,lq);

8.CR←Circle(s,d(s,lq));/*以點(diǎn)s為圓心，d(s,lq)為半徑構(gòu)造圓S*/

9.Judge_Postion(l′);/*判斷新插入線段的位置*/

10.ifl′∈CRthen

11.returnSTA_RVLRkNN(L′,lq,k);

12.Lnew←LR;

13.end if

14.ifl′?CRthen

15.Lnew←LR;

16.end if

17.returnLnew;

End

算法DYN_ADD_RVLRkNN首先初始化集合Lnew，LR和Dist(d)為空。將新增線段l′添加到數(shù)據(jù)線段集L中，得到新的數(shù)據(jù)線段集L′。接著調(diào)用STA_RVLRkNN算法，計(jì)算出線段li與查詢線段lq之間的距離，并添加到Dist(d)集合中。然后以點(diǎn)s為圓心，d(s,lq)為半徑構(gòu)造圓S，若新增線段l′在圓S內(nèi)，則對(duì)查詢結(jié)果有影響，重新調(diào)用STA_RVLRkNN算法并根據(jù)新的數(shù)據(jù)線段集L′重新進(jìn)行計(jì)算；若l′不在圓S中，則新增線段對(duì)原查詢結(jié)果沒有影響，直接返回原查詢結(jié)果即可。

3.2.2 移除數(shù)據(jù)線段對(duì)查詢結(jié)果的影響

在大多情況下，空間數(shù)據(jù)集的動(dòng)態(tài)變化是不確定的。如果將某數(shù)據(jù)線段從數(shù)據(jù)線段集中移除，有可能對(duì)原有的查詢結(jié)果產(chǎn)生影響。下面討論從數(shù)據(jù)線段集中移除線段對(duì)查詢結(jié)果的影響，并提出算法DYN_DEL_RVLRkNN。

根據(jù)移除數(shù)據(jù)線段是否在查詢結(jié)果中，對(duì)查詢結(jié)果的影響可以分為兩種情況：一種情況為所移除的數(shù)據(jù)線段不在查詢結(jié)果集合中，則它對(duì)查詢結(jié)果沒有影響，直接返回上次的查詢結(jié)果集合即可。另一種情況為所移除的數(shù)據(jù)線段在查詢結(jié)果集合中，則從數(shù)據(jù)線段集L中撤除該數(shù)據(jù)線段，并重新計(jì)算查詢結(jié)果。如圖3所示，針對(duì)lq的前兩個(gè)反向最近鄰來說，假設(shè)移除線段l2，由于l2不屬于查詢結(jié)構(gòu)集，從而查詢結(jié)果不變。假設(shè)移除線段為l′，在移除之前，由于l′包含在查詢結(jié)構(gòu)集中，此時(shí)lq的第一個(gè)反向最近鄰存在于候選集{l1,l3,l5}中。經(jīng)計(jì)算l1到lq的距離更近，則它的1-LRNN為l1，可以根據(jù)查詢算法再繼續(xù)查找它的2-LRNN，顯然最終的查詢結(jié)果發(fā)生了改變。

基于以上討論，給出算法5。

算法5DYN_DEL_RVLRkNN(L,lq,l′,k)

輸入：數(shù)據(jù)線段集L，查詢線段lq，移除線段l′,k值

輸出：移除數(shù)據(jù)線段后線段反k最近鄰的查詢結(jié)果

Begin

1.Lnew←?;/*初始化查詢結(jié)果為空集*/

2.LR←?;/*初始化候選集為空集*/

3.Dist(d)←?;/*初始化線段最短距離為空集*/

4.L′←L-l′;/*從數(shù)據(jù)線段集合L中移除l′*/

5.call STA_RVLRkNN(L,lq,k);/*得到候選集LR*/

6.ifl′∈LRthen

7.retrun STA_RVLRkNN(L′,lq,k);

8.Lnew←LR;

9.end if

10.ifl′?LRthen

11.Lnew←LR;

12.end if

13.returnLnew;

End

算法DYN_DEL_RVLRkNN首先初始化集合Lnew，LR和Dist(d)為空，將待移除線段l′從數(shù)據(jù)線段集L中移除，得到新的數(shù)據(jù)線段集L′。然后調(diào)用STA_RVLRkNN算法，得到數(shù)據(jù)線段集為L′時(shí)的查詢結(jié)果。進(jìn)一步對(duì)結(jié)果集進(jìn)行判斷，分為兩種情況：若結(jié)果集包含l′，則移除該線段會(huì)對(duì)查詢結(jié)果產(chǎn)生影響，需對(duì)L′重新調(diào)用STA_RVLRkNN算法，得到新的結(jié)果集合Lnew；如果結(jié)果集合不包含l′，則可以判斷移除該線段對(duì)查詢結(jié)果沒有影響，直接將原結(jié)果集合賦給新結(jié)果集合即可。

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

本文首次提出了路網(wǎng)中線段反k最近鄰查詢問題，并給出了查詢方法。但現(xiàn)有的路網(wǎng)反k最近鄰查詢都是以空間點(diǎn)為基礎(chǔ)的，不能用于路網(wǎng)環(huán)境下線段反k最近鄰查詢問題，因此無法直接與本文算法進(jìn)行比較。為了得到比較算法，設(shè)計(jì)了一個(gè)較為基礎(chǔ)的算法RNLRkNN_Basic。RNLRkNN_Basic算法是對(duì)文獻(xiàn)[18]中提出的線段最近鄰（line nearest neighbor，LNN）查詢算法的反復(fù)運(yùn)用，其主要思想為：在路網(wǎng)環(huán)境下反復(fù)調(diào)用LNN算法，將其應(yīng)用于線段反k最近鄰查詢中。首先對(duì)線段集中的一個(gè)線段反復(fù)調(diào)用LNN算法，得到相應(yīng)的查詢結(jié)果LkNN。然后對(duì)該線段的LkNN進(jìn)行判斷，如果查詢結(jié)果中存在查詢線段，則將該線段添加到查詢結(jié)果集中。如果查詢結(jié)果中不包含該線段，則繼續(xù)調(diào)用LNN算法并進(jìn)行判斷，最后得到LRkNN查詢結(jié)果。

本實(shí)驗(yàn)的運(yùn)行環(huán)境為：2.0 GHz CPU，4 GB內(nèi)存，500 GB硬盤，Windows 7系統(tǒng)。實(shí)驗(yàn)采用的路網(wǎng)數(shù)據(jù)集是美國舊金山和加州的路網(wǎng)信息（http://konect.unikoblenz.de/networks/roadNet-CA）。實(shí)驗(yàn)中，對(duì)目標(biāo)線段和分布進(jìn)行了適度調(diào)整。集合Q中的查詢線段均勻分布在路網(wǎng)的子區(qū)域中。用A表示子區(qū)域占整個(gè)路網(wǎng)的百分比；用參數(shù)F表示邊的權(quán)值與實(shí)際長度的偏離程度，F(xiàn)=權(quán)值／歐氏距離。在默認(rèn)情況下，分布在A=5%的路網(wǎng)圖中，目標(biāo)線段的密度P=0.05，參數(shù)F=2。對(duì)于每次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果均為執(zhí)行20次的平均值。

對(duì)靜態(tài)數(shù)據(jù)情況下的RVLRkNN查詢算法（STA_ RVLRkNN）進(jìn)行測(cè)試。首先測(cè)試k值、數(shù)據(jù)集大小、目標(biāo)線段密度P對(duì)CPU時(shí)間的影響。其次測(cè)試k值和數(shù)據(jù)集大小對(duì)兩算法I/O代價(jià)的影響。進(jìn)一步測(cè)試動(dòng)態(tài)數(shù)據(jù)集情況下兩查詢的性能。最后對(duì)兩算法的準(zhǔn)確率進(jìn)行測(cè)試。

Fig.4 Effect ofkon CPU query time圖4 k值對(duì)CPU時(shí)間的影響

首先，測(cè)試k值變化對(duì)CPU時(shí)間的影響，實(shí)驗(yàn)結(jié)果如圖4所示。從圖4中可以看出，隨著k值的不斷變大，兩算法的CPU時(shí)間均呈上升趨勢(shì)。其中RNLRkNN_Basic算法的CPU上升趨勢(shì)在k值達(dá)到一定程度時(shí)增長顯著，STA_RVLRkNN算法上升趨勢(shì)比較平緩。由于RNLRkNN_Basic算法需要對(duì)線段集中的每個(gè)線段計(jì)算它的LkNN，隨著k值的增加，造成了搜索區(qū)域大量重疊的情況，查詢所用的時(shí)間較長。而本文提出的路網(wǎng)中基于Voronoi圖的STA_ RVLRkNN算法在預(yù)處理階段排除掉大量非候選者，有效地縮小了查詢范圍，因此查詢所用的時(shí)間比RNLRkNN_Basic算法少。

其次，在其他條件不變的情況下，k=15，測(cè)試在不同大小的數(shù)據(jù)集環(huán)境下對(duì)算法CPU時(shí)間的影響，實(shí)驗(yàn)結(jié)果如圖5所示。從圖5中可以看出，隨著數(shù)據(jù)集的增大，兩算法的CPU時(shí)間均呈上升趨勢(shì)。但本文提出的STA_RVLRkNN算法的上升趨勢(shì)較為平緩，而RNLRkNN_Basic算法的變化趨勢(shì)在數(shù)據(jù)集規(guī)模達(dá)到一定程度時(shí)上升比較迅速。這是由于STA_ RVLRkNN算法有效地利用了過濾過程，縮小了查詢范圍，從而降低了查詢時(shí)間。對(duì)于RNLRkNN_Basic來說，則要對(duì)數(shù)據(jù)集中的每一個(gè)線段搜索它的LkNN，浪費(fèi)了大量時(shí)間。故在其他條件相同時(shí)，只考慮對(duì)CPU時(shí)間的影響，STA_RVLRkNN算法較優(yōu)。

Fig.5 Effect of data set size on CPU query time圖5 數(shù)據(jù)集規(guī)模對(duì)CPU時(shí)間的影響

進(jìn)一步分析目標(biāo)線段密度對(duì)CPU時(shí)間的影響，在k=15，目標(biāo)線段密度不同的情況下分別對(duì)兩算法進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如圖6所示。從圖6中可以看出,兩算法的CPU時(shí)間均隨密度P值的增大而增多。這是因?yàn)殡S著P值的增大意味著目標(biāo)線數(shù)量變多，STA_ RVLRkNN算法在計(jì)算候選線段時(shí)，需要訪問更多的NLVP，因此造成CPU時(shí)間的增大。同理RNLRkNN_Basic算法需要通過計(jì)算更多的線段間距離從而判斷LkNN。當(dāng)目標(biāo)線段較稠密時(shí)，STA_RVLRkNN算法CPU時(shí)間增長較快。但在實(shí)際生活中，目標(biāo)線段的密度通常遠(yuǎn)小于0.08。

Fig.6 Effect ofPon CPU query time圖6 目標(biāo)線段密度對(duì)CPU時(shí)間的影響

在其他條件一定時(shí)，針對(duì)k值的變化對(duì)算法I/O代價(jià)的影響進(jìn)行測(cè)試。根據(jù)實(shí)驗(yàn)測(cè)試數(shù)據(jù)繪制條形圖，如圖7所示。RNLRkNN_Basic算法的I/O代價(jià)隨著k值的增長，上升趨勢(shì)比較顯著，而STA_RVLRkNN算法相對(duì)來說I/O代價(jià)上升趨勢(shì)較為平緩。這是因?yàn)镽NLRkNN_Basic算法需要計(jì)算每一條線段的LkNN，隨著k值的增加，算法在查詢過程中所要存儲(chǔ)和訪問的線段也逐漸增多，從而造成該算法的I/O代價(jià)較高。對(duì)于STA_RVLRkNN算法，在過濾過程中排除掉大量非候選者，因此降低了查詢算法的I/O代價(jià)。故在其他條件相同時(shí)，只考慮對(duì)I/O代價(jià)的影響，STA_RVLRkNN算法性能更優(yōu)。

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

進(jìn)一步測(cè)試數(shù)據(jù)規(guī)模對(duì)I/O代價(jià)的影響，實(shí)驗(yàn)結(jié)果如圖8所示。算法RNLRkNN_Basic的I/O代價(jià)隨著數(shù)據(jù)集的增長，變化趨勢(shì)較為明顯，STA_RVLRkNN算法的變化趨勢(shì)較為緩慢。這是因?yàn)镽NLRkNN_ Basic算法中需要計(jì)算每一個(gè)線段的LkNN，由于數(shù)據(jù)集中線段越多，造成查詢過程中的無關(guān)數(shù)據(jù)訪問量越多，從而導(dǎo)致I/O代價(jià)不斷變大。而STA_ RVLRkNN算法在過濾階段排除了大量非候選者，減少了對(duì)無關(guān)數(shù)據(jù)的訪問，故而I/O代價(jià)較小，且隨著數(shù)據(jù)集規(guī)模的增加I/O代價(jià)增長緩慢。因此在其他條件相同時(shí)，只考慮對(duì)I/O代價(jià)的影響，STA_RVLRkNN算法更優(yōu)。

Fig.8 Effect of data set Size on I/O cost圖8 數(shù)據(jù)集規(guī)模對(duì)I/O代價(jià)的影響

針對(duì)動(dòng)態(tài)數(shù)據(jù)集情況下的LRkNN查詢算法的性能進(jìn)行測(cè)試。在路網(wǎng)環(huán)境下將重復(fù)調(diào)用RNLRkNN_ Basic算法的方式應(yīng)用于動(dòng)態(tài)數(shù)據(jù)集情況中，形成對(duì)比算法。當(dāng)線段動(dòng)態(tài)增加時(shí)，該算法的主要思想為：將新的線段添加到數(shù)據(jù)集中形成新的數(shù)據(jù)線段集，重新調(diào)用原有的算法，從而得出結(jié)果集。當(dāng)線段動(dòng)態(tài)減少時(shí)，該算法的主要思想為：將某一線段從線段集中移除形成新的數(shù)據(jù)線段集，重新調(diào)用原有的算法得出結(jié)果集。

設(shè)定線段數(shù)量為8 000，k=15，在路網(wǎng)環(huán)境下分別運(yùn)行DYN_ADD_RVLRkNN算法和RNLRkNN_Basic算法，得到其CPU運(yùn)行時(shí)間記錄到表1中。在其他環(huán)境不變時(shí)，線段以每次增加一條的方式進(jìn)行測(cè)試，重復(fù)運(yùn)行并取時(shí)間的平均值，記錄其時(shí)間到表1中。從表1中可以看出，當(dāng)數(shù)據(jù)線段動(dòng)態(tài)增加時(shí)DYN_ADD_RVLRkNN算法的CPU時(shí)間有所增加，但變化不明顯。而RNLRkNN_Basic算法的CPU時(shí)間變化相對(duì)增長幅度較大。這是因?yàn)楫?dāng)增加一條線段時(shí)DYN_ADD_RVLRkNN算法會(huì)先判斷其是否在影響區(qū)域內(nèi)，然后采取不同的策略。而RNLRkNN_Basic算法則要重新執(zhí)行一遍算法。因此，在數(shù)據(jù)集增加線段的情況下，只考慮對(duì)CPU時(shí)間影響的因素，DYN_ADD_RVLRkNN算法的性能優(yōu)于RNLRkNN_ Basic算法。

Table 1 Performance comparison between DYN_ADD_RVLRkNN and RNLRkNN_Basic表1DYN_ADD_RVLRkNN與RNLRkNN_Basic算法性能比較

進(jìn)一步在線段動(dòng)態(tài)減少的情況下進(jìn)行測(cè)試，分別運(yùn)行DYN_DEL_RVLRkNN算法和RNLRkNN_Basic算法，得到CPU時(shí)間并記錄到表2中。然后，保證其他條件不變，每次減少一條線段并記錄其CPU時(shí)間，重復(fù)運(yùn)行算法，計(jì)算其平均時(shí)間并記錄到表2中。從時(shí)間的變化可以看出，雖然算法的時(shí)間都有增長，但DYN_DEL_RVLRkNN算法增長的幅度遠(yuǎn)小于RNLRkNN_Basic算法。這是由于DYN_DEL_RVLRkNN算法會(huì)對(duì)刪除的線段進(jìn)行判斷，然后再采取相應(yīng)的策略。而RNLRkNN_Basic算法需要對(duì)新的數(shù)據(jù)集重新運(yùn)行一次，形成了較多的冗余數(shù)據(jù)，比較浪費(fèi)查詢時(shí)間。因此在數(shù)據(jù)集減少線段的情況下，只考慮對(duì)CPU時(shí)間影響的因素，DYN_DEL_RVLRkNN算法的性能優(yōu)于RNLRkNN_Basic算法。

Table 2 Performance comparison between DYN_DEL_RVLRkNN and RNLRkNN_Basic表2DYN_DEL_RVLRkNN與RNLRkNN_Basic算法性能比較

最后對(duì)算法的準(zhǔn)確率進(jìn)行測(cè)試。在其他條件不變的情況下數(shù)據(jù)量為5 000，分別測(cè)試靜態(tài)數(shù)據(jù)集和動(dòng)態(tài)數(shù)據(jù)集下兩算法的準(zhǔn)確率20次，最終結(jié)果取其平均值。首先測(cè)試準(zhǔn)確率隨k值的變化情況，如圖9所示。從圖9中可以看出，隨著k值的增加，兩算法的準(zhǔn)確率存在上升、不變以及減少的情況。這說明準(zhǔn)確率與k值之間沒有必然的線性關(guān)系。設(shè)定k=12，測(cè)試隨著查詢次數(shù)的增加準(zhǔn)確率的變化情況，如圖10所示。從圖10中可以看出，兩算法的準(zhǔn)確率均隨著查詢次數(shù)的增加而增加，但本文提出的RVLRkNN算法比RNLRkNN_Basic算法更快速地達(dá)到較高的準(zhǔn)確率。

Fig.9 Effect ofkon accuracy圖9 k值對(duì)準(zhǔn)確率的影響

Fig.10 Effect of queries number on accuracy圖10 查詢次數(shù)對(duì)準(zhǔn)確率的影響

5 結(jié)束語

本文提出了路網(wǎng)環(huán)境下線段反k最近鄰查詢方法，有效減少了現(xiàn)實(shí)生活中對(duì)象（例如河流、大型建筑、軌道等）抽象為點(diǎn)時(shí)反k最近鄰查詢所帶來的誤差，解決了針對(duì)靜態(tài)數(shù)據(jù)集情況下以及動(dòng)態(tài)數(shù)據(jù)集情況下的線段反k最近鄰查詢問題。通過理論研究和實(shí)驗(yàn)表明，對(duì)于數(shù)據(jù)集比較稠密的情況本文算法存在著一定的局限性，但在數(shù)據(jù)集密度較低時(shí)，本文算法具有較好的性能。未來的研究重點(diǎn)主要集中在路網(wǎng)環(huán)境下的線段最近鄰查詢。

[1]Gong Caixia,Chen Xinjun,Gao Feng,et al.Development and application of geographic information system in marine fisheries[J].Journal of Shanghai Ocean University,2011,15 (2):134-143.

[2]Mookiah M R K,Acharya U R,Koh J E W,et al.Decision support system for age-related macular degeneration using discrete wavelet transform[J].Medical&Biological Engineering&Computing,2014,52(9):781-796.

[3]Hong Zixuan,Bian Fuling.Time-space and cognition-space transformations for transportation network analysis based on multidimensional scaling and self-organizing map[C]// SPIE 7144:Proceedings of the Geoinformatics 2008 and Joint Conference on GIS and Built Environment:The Built Environment and its Dynamics,Guangzhou,China,Jun 28-29,2008.

[4]Dasarathy B V.Nearest neighbor(NN)norms:NN pattern classification techniques[M].Los Alamitos,USA:IEEE Computer Society Press,1990:217-224.

[5]Li Song,Zhang Liping,Hao Zhongxiao.Strong neighbor pair query in dynamic dataset[J].Journal of Computer Research and Development,2015,52(3):749-759.

[6]Boiman O,Shechtman E,Irani M.In defense of nearest-neighbor based image classification[C]//Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition,Anchorage,USA,Jun 23-28,2008.Piscataway,USA: IEEE,2008:1192-1999.

[7]Cheng R,Chen Lei,Chen Jinchuan,et al.Evaluating probability thresholdk-nearest-neighbor queries over uncertain data[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology,Saint Petersburg,Russia,Mar 24-26,2009.New York:ACM,2009:672-683.

[8]Zhang Zhaoxing,Fan Xingqi,Zhao Suyun,et al.Fast reduction algorithm research based onk-nearest neighbor fuzzy rough set[J].Journal of Frontiers of Computer Science and Technology,2015,9(1):14-23.

[9]Yi Xun,Paulet R,Bertino E,et al.Practical approximateknearest neighbor queries with location and query privacy[J]. IEEE Transactions on Knowledge and Data Engineering, 2016,28(6):1546-1559.

[10]Wang Li,Qin Xiaolin,Shi Changyue.Bichromatic reverse nearest neighbor queries in indoor space[J].Journal of Frontiers of Computer Science and Technology,2015,9(3):310-320.

[11]Lin Huaizhong,Chen Fangshu,Gao Yunjun,et al.Finding optimal region for bichromatic reverse nearest neighbor in two-and three-dimensional spaces[J].Geoinformatica,2016, 20(3):351-384.

[12]Tran Q T,Taniar D,Safar M.Bichromatic reverse nearestneighbor search in mobile systems[J].IEEE Systems Journal,2014,4(2):230-242.

[13]Lee K W,Choi D W,Chung C W.DART:an efficient method for direction-aware bichromatic reverseknearest neighbor queries[C]//LNCS 8098:Proceedings of the 13th International Conference on Advances in Spatial and Temporal Databases,Munich,Germany,Aug 21-23,2013.Berlin,Heidelberg:Springer,2013:295-311.

[14]Emrich T,Kriegel H P,Ger P,et al.Reversek-nearest neighbor monitoring on mobile objects[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems,San Jose,USA,Nov 2-5,2010.New York:ACM,2010:494-497.

[15]Lu Bingliang,Cui Xiaoyu,Liu Na.Bichromatic reverse nearestkneighbor query processing on road network[J].Journal of Chinese Computer Systems,2015,36(2):266-270.

[16]Yu Xiaonan.A method for reversek-nearest-neighbor queries in obstructed spaces[J].Chinese Journal of Computers, 2011,34(10):1917-1925.

[17]Zhu Huaijie,Wang Jiaying,Wang Bin,et al.Location privacy pressing obstructed nearest neighbor queries[J].Journal of Computer Research and Development,2014,51(1):115-125.

[18]Hao Zhongxiao,Wang Yudong,He Yunbin.Line segment nearest neighbor query of spatial database[J].Journal of Computer Research and Development,2008,45(9):1539-1545.

[19]Gu Yu,Zhang Hui,Wang Zhigang,et al.Efficient movingknearest neighbor queries over line segment objects[J].World Wide Web Internet and Web Information Systems, 2015,19(4):653-677.

[20]Liu Runtao,Hao Zhongxiao.Fast algorithm of nearest neighbor query for line segments of spatial database[J].Journal of Computer Research and Development,2011,48(12):2379-2384.

[21]Papadopoulou E,Zavershynskyi M.The higher-order Voronoi diagram of line segments[J].Algorithmica,2014,74 (1):1-25.

附中文參考文獻(xiàn)：

[1]龔彩霞,陳新軍,高峰,等.地理信息系統(tǒng)在海洋漁業(yè)中的應(yīng)用現(xiàn)狀及前景分析[J].上海海洋大學(xué)學(xué)報(bào),2011,20(6): 902-909.

[5]李松,張麗平,郝忠孝.動(dòng)態(tài)數(shù)據(jù)集環(huán)境下的強(qiáng)鄰近對(duì)查詢[J].計(jì)算機(jī)研究與發(fā)展，2015,52(3):749-759.

[8]張照星,范星奇,趙素云,等.k-近鄰模糊粗糙集的快速約簡算法研究[J].計(jì)算機(jī)科學(xué)與探索,2015,9(1):14-23.

[10]王麗,秦小麟,施常月.室內(nèi)雙色數(shù)據(jù)集上的反向最近鄰查詢[J].計(jì)算機(jī)科學(xué)與探索，2015,9(3):310-320.

[15]盧秉亮,崔曉玉,劉娜.路網(wǎng)中雙色反向k近鄰查詢處理[J].小型微型計(jì)算機(jī)系統(tǒng)，2015,36(2):266-270.

[16]于曉南.一種障礙空間中的反k最近鄰查詢研究[J].計(jì)算機(jī)學(xué)報(bào)，2011,34(10):1917-1925.

[17]朱懷杰,王佳英,王斌,等.障礙空間中保持位置隱私的最近鄰查詢方法[J].計(jì)算機(jī)研究與發(fā)展，2014,51(1):115-125.

[18]郝忠孝,王玉東,何云斌.空間數(shù)據(jù)庫平面線段最近鄰查詢問題研究[J].計(jì)算機(jī)研究與發(fā)展,2008,45(9):1539-1545.

[20]劉潤濤,郝忠孝.空間數(shù)據(jù)庫平面線段快速最近鄰查詢算法[J].計(jì)算機(jī)研究與發(fā)展,2011,48(12):2379-2384.

張麗平（1976—），女，遼寧鐵嶺人，碩士，哈爾濱理工大學(xué)副教授、研究生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫理論及應(yīng)用，數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

GUO Yingying was born in 1993.She is an M.S.candidate at Harbin University of Science and Technology.Her research interests include data mining and data query.

郭瑩瑩（1993—），女，黑龍江大慶人，哈爾濱理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，數(shù)據(jù)查詢。

LI Song was born in 1977.He received the Ph.D.degree from Harbin University of Science and Technology.Now he is an associate professor at Harbin University of Science and Technology,and the member of CCF.His research interests include database theory and application,data mining and data query.

李松（1977—），男，江蘇沛縣人，博士，哈爾濱理工大學(xué)副教授、研究生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫理論及應(yīng)用，數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

LI Shuang was born in 1991.She is an M.S.candidate at Harbin University of Science and Technology.Her research interests include data mining and data query.

李爽（1991—），女，黑龍江哈爾濱人，哈爾濱理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，數(shù)據(jù)查詢。

FAN Ruiguang was born in 1993.He is an M.S.candidate at Harbin University of Science and Technology.His research interests include data mining and data query.

樊瑞光（1993—），男，黑龍江哈爾濱人，哈爾濱理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，數(shù)據(jù)查詢。

Line ReversekNearest Neighbor Query in Road Network*

ZHANG Liping+,GUO Yingying,LI Song,LI Shuang,FAN Ruiguang
College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
+Corresponding author:E-mail:zhanglptg@163.com

To remedy the defects that existing methods can not deal with the line segment reverseknearest neighbor (RkNN)query in road network,this paper puts forward the line segment RkNN query method in road network.The query method is mainly used to assess the scope of query object.Based on the characteristics of road network and Voronoi diagram,the network line Voronoi diagram(NLVD)concept is proposed.According to the property of NLVD,the STA_RVLRkNN is given in static line segment set environment,the query includes two parts:filtering and refining processes.Further,DYN_RVLRkNN method is given in dynamic line segment set environment,this query is divided into two parts of adding and deleting space segment objects,then the corresponding algorithm is proposed for different situations and new query result set is obtained.The theatrical study and experimental results show that the algorithm can effectively deal with the line segment RkNN query in road network.

road network;network line Voronoi diagram(NLVD);reverseknearest neighbor

ing was born in 1976.She

the M.S.degree from Harbin University of Science and Technology. Now she an associate professor at Harbin University of Science and Technology,and the member of CCF.Her research interests include database theory and application,data mining and data query.

A

TP311.13

*The Science and Technology Research Project of Heilongjiang Provincial Education Department under Grant No.12531z004(黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目).

Received 2016-04,Accepted 2016-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1045.004.html