路網中線段反k最近鄰查詢研究*

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

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

路網中線段反k最近鄰查詢研究*

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

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 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.

為了彌補現有的研究成果無法有效地處理路網環境下基于線段的反k最近鄰問題的不足，提出了在路網環境下線段反k最近鄰查詢方法。該查詢方法主要應用于評估查詢對象的影響范圍。根據路網及Voronoi圖的特點提出了網絡線段Voronoi圖的概念。在靜態數據集情況下利用網絡線段Voronoi圖的性質提出了STA_RVLRkNN算法，查詢包括過濾過程和精煉過程兩大部分。進一步，在動態數據集的情況下提出了DYN_ RVLRkNN算法，查詢分為空間線段對象增加和刪除兩種情況，并對不同的情況給出了相應的算法，得到查詢結果集。理論研究和實驗表明，所提算法能有效地處理路網中基于線段的反k最近鄰問題。

路網；網絡線段Voronoi圖；反k最近鄰

1 引言

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

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

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

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

本文所提出的路網中線段反k最近鄰查詢方法，用于處理不相交的線段。分別討論了靜態數據集和動態數據集兩種情況下的線段反k最近鄰查詢。靜態數據集情況下查詢分為過濾過程和精煉過程兩個階段。動態數據情況分為數據線段的增加和刪除兩種情況，通過相對應的算法思想對新的數據線段集進行查詢得到新的查詢結果集。

2 基礎定義與性質

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

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

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

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

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

進一步，本文所提出的網絡線段Voronoi圖（network line Voronoi diagram，NLVD）如定義5所示。

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

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

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

由網絡線段Voronoi圖的結構及定義可以得出以下性質。

性質1（最短距離特性）兩線段之間的最短距離是線段到邊界點的最短距離之和，而非兩線段之間的連線距離。

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

根據網絡線段Voronoi圖的定義及性質，進一步給出NLVD生成算法如算法1所示。

算法1Create_NLVD

輸入：數據線段集L，邊的集合E，節點集合N

輸出：NLVD

Begin

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

2.設生成線段l的左右端點分別為s、e;

3.過節點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. 計算NLVP(li)與NLVP(lj)邊界點b=(ni,nj|d(ni)-d(nj)-d(ni,nj)/2)的位置;

15. end if

16.end for

17.return NLVD;

End

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

3 路網環境下LRkNN查詢

根據線段集中的線段是否變化，本文提出路網中線段反k最近鄰查詢（RVLRkNN查詢）方法。主要分為兩部分，分別為靜態數據集情況下的RVLRkNN查詢（STA_RVLRkNN查詢）和動態數據集情況下的RVLRkNN查詢（DYN_RVLRkNN查詢）兩類。

3.1 靜態數據集情況下RVLRkNN查詢

本節提出的路網中線段反k最近鄰查詢方法主要包括兩個階段，分別為過濾過程和精煉過程。首先是過濾過程，對查詢線段集進行優化處理，獲取較精確的候選集。然后是精煉過程，對候選集進行精煉得到更加精確的候選集。最后排除錯誤結果，得到正確的查詢結果集。

3.1.1 過濾過程

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

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

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

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

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

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

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

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

算法2RVLRkNN_Filter(L,lq,k)

輸入：數據線段集L，查詢線段lq,k值

輸出：過濾后的候選集LC

Begin

1.Create_NLVD(L∪lq);/*創建網絡線段Voronoi圖*/

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

3.fori=1 tokdo

4.iflq∈NLVP(li)then

5.LC←li;/*將lq的第一個反向最近鄰加入到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算法的具體過程為：首先以數據線段集L和查詢線段lq的并集為生成線段創建網絡線段Voronoi圖。然后根據定理1，對數據線段進行過濾。根據定理2，對得到的候選結果做進一步篩選，滿足條件的線段被剪枝，最后剩下為排除掉非候選者的結果集合。如圖1所示，lq存在于NLVP(l1)中，因此其1-LRNN為線段l1，它的2-LRNN一定存在于候選集{l2,l3,l9,l8}中。再根據定理2進一步判斷，線段l3和l9滿足條件，因此被剪枝，得出候選集合為{l2,l8}。

3.1.2 精煉過程

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

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

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

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

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

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

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

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

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

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

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

算法3STA_RVLRkNN(L,lq,k)

輸入：數據線段集L，查詢線段lq,k值

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

Begin

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

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

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

4.while(LC!=NULL)do

5.設l的兩端點分別為s、e;

6.過邊界點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)之間的邊界點*/

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

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添加到結果集中*/

21.end if

22.end while

23.returnLR

End

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

3.2 數據線段集合變化對查詢結果的影響

數據線段集L的變化對查詢結果會產生一定的影響，主要分為兩部分，即新增數據線段對查詢結果的影響，以及移除數據線段對查詢結果的影響。

3.2.1 新增數據線段對查詢結果的影響

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

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

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

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

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

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

Begin

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

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

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

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

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

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

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

8.CR←Circle(s,d(s,lq));/*以點s為圓心，d(s,lq)為半徑構造圓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′添加到數據線段集L中，得到新的數據線段集L′。接著調用STA_RVLRkNN算法，計算出線段li與查詢線段lq之間的距離，并添加到Dist(d)集合中。然后以點s為圓心，d(s,lq)為半徑構造圓S，若新增線段l′在圓S內，則對查詢結果有影響，重新調用STA_RVLRkNN算法并根據新的數據線段集L′重新進行計算；若l′不在圓S中，則新增線段對原查詢結果沒有影響，直接返回原查詢結果即可。

3.2.2 移除數據線段對查詢結果的影響

在大多情況下，空間數據集的動態變化是不確定的。如果將某數據線段從數據線段集中移除，有可能對原有的查詢結果產生影響。下面討論從數據線段集中移除線段對查詢結果的影響，并提出算法DYN_DEL_RVLRkNN。

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

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

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

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

輸出：移除數據線段后線段反k最近鄰的查詢結果

Begin

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

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

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

4.L′←L-l′;/*從數據線段集合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′從數據線段集L中移除，得到新的數據線段集L′。然后調用STA_RVLRkNN算法，得到數據線段集為L′時的查詢結果。進一步對結果集進行判斷，分為兩種情況：若結果集包含l′，則移除該線段會對查詢結果產生影響，需對L′重新調用STA_RVLRkNN算法，得到新的結果集合Lnew；如果結果集合不包含l′，則可以判斷移除該線段對查詢結果沒有影響，直接將原結果集合賦給新結果集合即可。

4 實驗與分析

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

本實驗的運行環境為：2.0 GHz CPU，4 GB內存，500 GB硬盤，Windows 7系統。實驗采用的路網數據集是美國舊金山和加州的路網信息（http://konect.unikoblenz.de/networks/roadNet-CA）。實驗中，對目標線段和分布進行了適度調整。集合Q中的查詢線段均勻分布在路網的子區域中。用A表示子區域占整個路網的百分比；用參數F表示邊的權值與實際長度的偏離程度，F=權值／歐氏距離。在默認情況下，分布在A=5%的路網圖中，目標線段的密度P=0.05，參數F=2。對于每次實驗，實驗結果均為執行20次的平均值。

對靜態數據情況下的RVLRkNN查詢算法（STA_ RVLRkNN）進行測試。首先測試k值、數據集大小、目標線段密度P對CPU時間的影響。其次測試k值和數據集大小對兩算法I/O代價的影響。進一步測試動態數據集情況下兩查詢的性能。最后對兩算法的準確率進行測試。

Fig.4 Effect ofkon CPU query time圖4 k值對CPU時間的影響

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

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

Fig.5 Effect of data set size on CPU query time圖5 數據集規模對CPU時間的影響

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

Fig.6 Effect ofPon CPU query time圖6 目標線段密度對CPU時間的影響

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

Fig.7 Effect ofkon I/O cost圖7 k值對I/O代價的影響

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

Fig.8 Effect of data set Size on I/O cost圖8 數據集規模對I/O代價的影響

針對動態數據集情況下的LRkNN查詢算法的性能進行測試。在路網環境下將重復調用RNLRkNN_ Basic算法的方式應用于動態數據集情況中，形成對比算法。當線段動態增加時，該算法的主要思想為：將新的線段添加到數據集中形成新的數據線段集，重新調用原有的算法，從而得出結果集。當線段動態減少時，該算法的主要思想為：將某一線段從線段集中移除形成新的數據線段集，重新調用原有的算法得出結果集。

設定線段數量為8 000，k=15，在路網環境下分別運行DYN_ADD_RVLRkNN算法和RNLRkNN_Basic算法，得到其CPU運行時間記錄到表1中。在其他環境不變時，線段以每次增加一條的方式進行測試，重復運行并取時間的平均值，記錄其時間到表1中。從表1中可以看出，當數據線段動態增加時DYN_ADD_RVLRkNN算法的CPU時間有所增加，但變化不明顯。而RNLRkNN_Basic算法的CPU時間變化相對增長幅度較大。這是因為當增加一條線段時DYN_ADD_RVLRkNN算法會先判斷其是否在影響區域內，然后采取不同的策略。而RNLRkNN_Basic算法則要重新執行一遍算法。因此，在數據集增加線段的情況下，只考慮對CPU時間影響的因素，DYN_ADD_RVLRkNN算法的性能優于RNLRkNN_ Basic算法。

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

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

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

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

Fig.9 Effect ofkon accuracy圖9 k值對準確率的影響

Fig.10 Effect of queries number on accuracy圖10 查詢次數對準確率的影響

5 結束語

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

[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.

附中文參考文獻：

[1]龔彩霞,陳新軍,高峰,等.地理信息系統在海洋漁業中的應用現狀及前景分析[J].上海海洋大學學報,2011,20(6): 902-909.

[5]李松,張麗平,郝忠孝.動態數據集環境下的強鄰近對查詢[J].計算機研究與發展，2015,52(3):749-759.

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

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

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

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

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

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

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

張麗平（1976—），女，遼寧鐵嶺人，碩士，哈爾濱理工大學副教授、研究生導師，CCF會員，主要研究領域為數據庫理論及應用，數據挖掘，數據查詢。

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—），女，黑龍江大慶人，哈爾濱理工大學碩士研究生，主要研究領域為數據挖掘，數據查詢。

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—），男，江蘇沛縣人，博士，哈爾濱理工大學副教授、研究生導師，CCF會員，主要研究領域為數據庫理論及應用，數據挖掘，數據查詢。

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—），女，黑龍江哈爾濱人，哈爾濱理工大學碩士研究生，主要研究領域為數據挖掘，數據查詢。

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—），男，黑龍江哈爾濱人，哈爾濱理工大學碩士研究生，主要研究領域為數據挖掘，數據查詢。

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(黑龍江省教育廳科學技術研究項目).

Received 2016-04,Accepted 2016-09.

CNKI網絡優先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1045.004.html