道路網絡中基于方向關系約束的CKNN 查詢

孫海龍 ,王霓虹 ,王春艷

(東北林業大學a.信息與計算機工程學院；b.圖書館,哈爾濱 150040)

1 概述

隨著無線通信技術的發展和具有GPS 定位功能的移動電話、PDA 等便攜設備的普及,基于位置的服務(Location Based Service,LBS)得以快速發展,已廣泛應用于地理信息系統、應急服務、汽車導航和旅游路徑規劃等領域[1]。空間查詢與基于位置服務密切相關,其中,道路網絡環境下移動對象的連續K 最近鄰查詢(Continouns K Nearest Neighbors,CKNN)是一類重要的查詢請求,能夠在道路網絡環境下不斷查找距離給定的查詢對象最近的K個最近鄰目標,例如,在消防指揮中,查找距離指揮中心最近的4 輛消防車。解決此問題的關鍵在于：(1)快速實時計算任意2 個移動對象之間的最短路徑；(2)移動對象位置更新后查詢結果的維護與管理。

國內外針對道路網絡的CKNN 查詢問題,學者們進行了深入研究。文獻[2]提出IMA/GMA方法,處理查詢對象和興趣點對象在道路網上任意移動的CKNN 查詢問題。該方法是處理基于道路網絡的CKNN 查詢經典算法,采用基于內存的數據結構存儲網絡邊、結點以及查詢信息,提出IMA/GMA 算法處理查詢請求。IMA 算法從查詢對象所在邊開始擴展網絡邊,并遍歷網絡邊上的興趣點對象,形成初始KNN 查詢結果集,同時以查詢點為根,建立查詢擴展樹,處理查詢請求、移動對象和道路邊權重更新時的連續查詢請求。GMA 采用IMA和共享執行機制,算法使用“序列”思想,即：序列上的查詢請求結果為序列上的對象和序列端點處KNN 結果的并集,當多個查詢請求處在同一序列上時可共享已獲得的查詢結果。為維護查詢結果的更新,在計算初始KNN 時建立影響列表。IMA/GMA 算法適合于密集的道路網絡。文獻[3]提出MovNet 框架處理道路網絡環境下的基于位置的查詢,使用基于磁盤的R 樹索引道路網絡,基于內存的格網索引管理移動對象的位置更新,通過網格重疊計算算法將道路網與格網單元進行關聯,完成基于位置的范圍查詢和KNN 查詢。文獻[4]針對IMA/GMA 算法中Dijkstra 算法進行網絡距離計算時盲目擴展以及對象位置更新時盲目映像的缺點,提出ER-CKNN 算法,基于PMR-QuadTree 索引道路網絡,基于格網索引移動對象位置,使用edgebitmap-encoding 技術結合A*啟發式搜索算法,提高最短路徑計算速度；同時,在查詢時使用歐式距離約束限制K 近鄰搜索區域；對象位置更新時,只對區域內的移動對象進行更新,從而加快查詢處理速度。文獻[5]針對基于道路網絡的CKNN 查詢處理,提出一種新的道路網絡有向圖模型,分別利用基于內存的哈希表和線性鏈表結構對移動對象當前位置和道路網絡有向圖模型進行存儲和管理。通過引入單向網絡距離度量和雙向網絡距離度量,提出單向網絡擴展(UNE)算法和雙向網絡擴展(BNE)算法以支持不同語義的連續K 近鄰查詢處理,并采用影響樹及網絡擴展策略來減少連續K近鄰查詢更新的搜索代價。文獻[6]針對數據頻繁更新時查詢性能下降問題,結合多核多線程技術,提出一種基于多線程的連續查詢處理框架。該框架周期性重計算所有查詢結果,將查詢處理分為順序執行的數據更新階段和查詢執行階段,分別使用任務并行和數據并行的方法執行各階段的操作。設計了數據更新階段使用的數據結構,提出了查詢處理階段的K 近鄰查詢處理策略,包含離線預計算和在線K 近鄰查詢處理算法2 個部分,并對K近鄰算法復雜性及多線程處理框架的加速比進行理論分析。以上文獻采用了不同技術提高CKNN算法的執行速度,但是都沒有考慮到方向關系約束條件在空間查詢中的作用[7-8]。文獻[8-9]研究了基于開放區域的方向關系查詢技術以及三維環境下的方向關系建模,但沒有考慮道路網絡環境下的最近鄰查詢問題。

為提高CKNN 查詢速度,本文將方向關系作為查詢約束條件引入到算法中,提出基于方向關系約束的CKNN 查詢CDR-CKNN 算法,處理道路網絡環境下連續K 最近鄰查詢問題。

2 問題描述及相關定義

在基于位置的服務中,消防員、消防車輛等移動對象配備了具有定位功能的移動設備,移動終端周期性地將位置信息傳送到服務器端。當用戶提交CKNN 查詢請求時,在服務器端基于道路網絡距離完成查詢請求,由于查詢對象和興趣點對象是不斷運動的,實時獲得連續KNN 查詢結果是系統應用的關鍵。為提高KNN 查詢速度,根據實際應用情況對已有算法進行改進：(1)預計算道路網絡結點之間的最短路徑；(2)由于移動對象的運動具有一定的方向性,因此將方向關系謂詞作為空間查詢約束條件引入CKNN 查詢中,快速過濾掉與查詢結果不相關的區域。

定義1(道路網絡) 一個道路網可以建模為有向帶權圖G(N,E,W),其中,N表示道路邊連接點和終點的集合；E(E∈N×N)表示道路網絡邊的集合,每條邊e記作e(ni,nj),表示由起點ni和終點nj組成的結點序列構成,并且邊不能存在環,即每條邊是由n0,n1,…,nk系列結點組成的多段線,n0表示邊的起點,nk表示邊的終點,并且n0≠nk；W：E|?R+表示邊權值的集合,權值可以是道路邊的長度、運行時間或者車流量等,如非特指,本文是指道路邊的長度,圖1 為部分道路網絡及其對應的有向帶權圖。

從圖1 可以看出,實際道路運行包括單行道和雙向車道,在建模圖形時用有向邊表示。同時,查詢對象和興趣點對象(統稱移動對象)在道路上運動時也具有方向性,下面對移動對象進行建模。

圖1 道路網絡及其對應有向帶權圖

定義2(移動對象) 在道路網絡中,移動對象建模為：MO(oid,x,y,eid,pos,dir),其中,oid表示移動對象的編號；x,y表示移動對象的坐標位置；eid表示移動對象所在的道路邊；pos表示移動對象在道路邊上距離道路邊起點的距離；dir表示移動對象運動方向,dir=1 表示從所在道路邊起點向終點方向運行,dir=-1 表示從所在道路邊終點向起點方向運行。移動對象可以是查詢對象,也可以是待查詢的興趣點對象(Points of Interest,POI)。

定義3(道路結點的鄰接鏈表) 為反映出道路網中U 型轉彎和十字路口轉向等交通規則,為道路網中的道路邊結點設置一個單鏈表,表示通過該結點的道路邊的轉向關系。圖2 為圖1 所示道路網絡中部分結點的鄰接鏈表。對于道路邊的交點n1,n5n5表示在結點n1處允許U 型轉彎；n5n2表示移動對象在n5n2道路邊上運動時,經過n1結點可以右轉彎,其他結點含義相同。

圖2 部分道路結點的鄰接鏈表

定義4(道路邊最短路徑) 任意給定的2 條道路邊：e1=(n1i,n1j),e2=(n2i,n2j),e1和e2之間的最短網絡距離可以用2 條邊起始點和終點之間最短路徑的最小值表示,即：

為提高系統的執行速度,預計算道路網絡中各頂點的最短路徑[10],在存儲在數據庫中,為計算道路網上任意2 個對象之間的最短路徑做基礎。

定義5(移動對象之間的最短路徑) 在道路網絡中,移動對象在道路邊上的位置表示為：(e,pos),道路邊e的權值記作：C(e)。假設2 個移動對象p1=(e1,pos1)、p2=(e2,pos2)分別在道路邊e1和e2上運動,則移動對象p1 和p2 的最短網絡距離表示為：

定義6(CKNN 查詢) 參考對象和待查詢的興趣點對象都在道路網絡邊上自由運動,CKNN 查詢是指每隔一定時間間隔查找距離查詢對象q最近的K個對象。假設興趣點對象集合S={p1,p2,…,pn},K 最近鄰查詢結果集為S′,S′?S,且|S′|≤K。對于任意數據對象p′∈S′,p∈S-S′,則有dN(p′,q)≤dN(p,q)。

3 索引結構設計

在道路網絡環境中,能夠有效存儲和查找道路邊上移動對象的最簡單方法是將移動對象看作道路網的結點,利用定義1 對道路網建模,然后采用文獻[11]提出的INE 方法進行查詢。但是該方法存在一些缺陷：(1)將移動對象當作道路邊結點對待,增加了網絡的復雜度和Dijkstra 算法的運行時間；(2)移動對象位置經常變化,需要不斷重建道路網結構。在實際應用中,道路網絡結構往往是不變的,而移動對象不斷更新位置,因此,道路網絡和移動對象必須分別存儲,本文提出一種3 層的索引結構,如圖3所示。上層是一棵R 樹,對道路網絡進行索引,當查詢點發出查詢請求時,通過R 樹可以快速定位查詢對象所在的道路邊；R 樹的葉子結點指向道路邊的實際存儲,這兩部分用來對道路網絡中靜態部分進行索引；第3 層hash 表部分以道路邊的編號為hash 值建立hash 表,存儲每條道路邊上的移動對象標識,并通過移動對象標識連接到移動對象列表中。當移動對象進行位置更新時,首先在移動對象列表中完成信息的更新,然后更新道路邊上的移動對象。靜態道路網絡部分不受影響。

圖3 道路網絡及移動對象索引結構

4 CKNN 查詢算法

在道路網絡中,基于方向謂詞約束的CKNN 查詢分為2 個步驟：(1)基于方向關系完成KNN 查詢請求；(2)更新KNN 查詢結果。第(1)個步驟又可細分為過濾和精煉2 個步驟。

4.1 基于方向謂詞約束的KNN 查詢算法設計

移動對象運行在道路網中,當查詢對象發出查詢請求時,首先通過索引結構中的移動對象列表和hash 表的鏈接關系找到查詢對象所在的道路邊；然后將查詢中的方向關系謂詞通過構建開放圖形轉化為ArcGIS 中的Geometry 類；其次將Geometry 圖形與道路網圖層作相交運算,獲得查詢區域內的道路邊,通過索引結構獲得查詢區域內的移動對象,獲得候選結果集；最后利用預計算的道路網結點數據計算查詢對象和候選結果集中各對象的最短路徑,精煉出最終的KNN 查詢結果。

定義7(錐形模型) 以參考對象為中心,將空間目標及周圍區域劃分成不同區域來表示對象之間方向關系的建模方法,適合于參考對象為點對象的建模情況。根據劃分區域數量不同,通常分為四方向錐形模型和八方向錐形模型,如圖4 所示。在四方向錐形模型中,用方向關系謂詞集合：{E,S,W,N}表示空間對象之間的方向關系,分別對應東、南、西、北4 個方向；在八方向錐形模型中,用方向關系謂詞集合{E,SE,S,SW,W,NW,N,NE}表示空間對象之間的方向關系,分別對應東、東南、南、西南、西、西北、北和東北8 個方向。從圖4 可以看出,每個方向關系謂詞都是一個由參考點和2 條邊組成的開放區域,因此,可以用開放圖形概念表示方向關系謂詞。

圖4 錐形模型

定義8(改進的開放圖形) 在文獻[6]中提出開放圖形概念,但是在實際道路網路查詢中,查詢范圍是有一定距離限制的,改進的開放圖形表示為：OpenShape(point,r,dir1,dir2),其中,point表示開放圖形的頂點；r表示距離；dir1 表示起始端線的方向；dir2 表示終端線的方向,按逆時針方向,以弧度值計算。例如,在圖4 中四方向錐形模型的東方向可表示為

算法1 給出了具有方向關系約束的道路網絡KNN 查詢過程,其中,KnnQuery代表查詢算法的名稱；q代表查詢參考對象；dp代表方向關系謂詞；K代表待查詢最近鄰對象的數量。

算法1KnnQuery(q,dp,K)

輸入R-Tree

輸出ResultList 滿足查詢條件的KNN 結果集

算法1 的時間復雜度計算主要集中在搜索R樹、搜索hash 表、計算道路網與方向區域的相交運算和計算候選集中對象的最短路徑等部分組成。在R樹中搜索道路邊的時間復雜度為O(NlogmN),其中,N為R 樹中葉子結點總數,即道路邊數量；m為每個結點最大分支數。hash 表通過hash 值進行搜索,時間復雜度為O(1)。道路網與方向區域的相交運算的時間復雜度取決于道路邊的數量,時間復雜度為O(N)。候選集中各結點之間的最短路徑計算采用Dijkstra 算法,時間復雜度為O(KlgK),K為候選集區域內道路網絡結點數量；其他部分時間計算可忽略不計,因此算法1 的時間復雜度為：O(NlogmN) +O(KlgK) +O(N)。

算法1 中步驟2、步驟3 通過搜索道路網絡的索引結構得到查詢點q所在的道路邊及其在道路邊上的位置；步驟4～步驟6 用來查找查詢區域內的道路邊,步驟4 將查詢條件中的方向關系謂詞轉換為開放圖形,但是開放圖形的開放區域沒有邊界限制,影響算法查詢效率。步驟5、步驟6 引用ArcGIS Server 中圖層的Intersect 相交運算幫助獲得查詢區域內的道路邊,步驟5 采用定義8 提出的改進開放圖形將開放區域轉化為Geometry,然后與道路網圖層進行Intersect運算,快速過濾掉與查詢結果無關的道路邊,獲得查詢區域內的道路邊。步驟7～步驟15 計算查詢區域內滿足查詢條件的所有候選興趣點對象。步驟7～步驟9 通過查詢索引結構中的hash 表獲得查詢區域內道路邊上的所有移動對象,但是有些興趣點對象并不在查詢區域內,如圖5(a)所示。當查詢移動對象q以東方向5 km 以內的最近鄰對象時,雖然邊n7n8位于查詢區域內,但興趣點對象o8不在查詢區域內。為解決該問題,步驟10～步驟14使用Geometry 的Contain包含運算,對候選興趣點對象candidateMO 中的每個對象進行驗證,從而得到查詢區域內的KNN 候選興趣點集。步驟16～步驟19 根據預計算的道路網絡結點之間的最短路徑,快速計算查詢點q與候選興趣點集candidateKNNs 中的各對象的最短路徑,并統計對象個數k,同時按照距離升序排序,存入ResultList 中。步驟20～步驟25 根據候選最近鄰對象個數決定查詢是否繼續。如圖5(a)所示的左斜線填充的查詢區域,如果查詢2 個最近鄰對象,則只需取出ResultList 中距離最近的前2 個對象即可。如果要查詢4 個最近鄰對象,則必須擴展查詢區域,如圖5(b)中右斜線填充部分為擴展區域,然后利用步驟7～步驟19 的方法計算擴展區域內的興趣點對象,直到得到K個最近鄰對象,將包含K個最近鄰對象的查詢區域保存在knnArea 中,供連續查詢KNN 時使用,算法運行結束。

圖5 KNN 查詢算法實例

4.2 連續K 最近鄰查詢實現

當系統再次發出KNN 查詢請求時,最簡單的處理方法是采用4.1 節提出的算法重新計算KNN,但是受移動終端計算能力和通信速度的影響,計算速度難以滿足要求。為了提高連續KNN 查詢的執行速度,可以維護4.1 節算法的查詢結果來提高連續KNN 查詢的性能。移動對象(包括查詢點對象和興趣點對象)不斷移動時,道路網絡結構和道路邊連接點的鄰接關系并不變,只是對移動對象的位置和坐標進行更新,根據移動對象位置變化不同,可以分為2 種情況維護KNN 查詢結果：(1)當查詢對象q位置不變,興趣點對象位置更新時,查詢對象q的KNN 查詢區域不變,可以利用算法1 得到的knnArea 區域加速更新算法；(2)查詢對象q位置更新或者方向關系約束條件改變,必須重新計算KNN集合。算法2 給出了連續KNN 查詢的算法實現。

算法2UpdateKnnQuery(q,dp,K)

輸入R-Tree

輸出ResultList 滿足查詢條件的KNN 結果集

算法2 中步驟3～步驟11 處理第(1)種情況時的查詢結果更新情況。只有落入knnArea 區域內的興趣點對象才影響查詢結果。根據移動對象位置更新后落入knnArea 區域內興趣點對象個數多少分為3 種不同情況。步驟5～步驟6 是恰好有K個對象落入查詢區域內,這是最理想的情況,K個對象即為更新后的查詢結果；步驟7～步驟8 表示落入knnArea 區域內對象數大于K,則利用算法1 中的步驟計算k′個對象與查詢對象q之間的最短路徑,并按照升序排序,將前K個對象作為查詢結果；步驟9～步驟10 表示落入knnArea 區域內對象數小于K,則必須擴展查詢區域半徑,繼續計算最近鄰對象,直到達到K為止。步驟12～步驟13 處理第(2)種情況,由于查詢對象q位置改變或者方向關系約束條件改變,原有的方向區域不再有效,不能利用knnArea 區域更新查詢結果,必須利用算法1 對KNN 集重新計算,算法2 結束。

5 實驗對比及分析

本文從興趣點對象(POI)數量、查詢請求數K、道路網規模以及不同方向關系模型等方面測試本文提出的CDR-CKNN 查詢算法與IMA/GMA 算法的性能對比情況,實驗測試數據集來自TIGER/Line 下載的加利福尼亞州洛杉磯市(Los Angeles,LA)道路網數據,LA 數據集中包含266 335 條雙向邊,195 010個道路結點,利用Brinkhoff[12]設計的基于道路網絡的移動對象產生器生成興趣點對象集。下載的shp 格式數據經過轉換工具,生成node 結點數據和edge 道路邊數據,作為移動對象產生器的輸入因子,實驗參數如表1 所示。實驗系統采用Java 語言編寫,運行環境為AMD 2.31 GHz 三核處理器,內存2 GB,Windows XP SP3 操作系統。每次測試只改變其中的一個參數值,其他參數采用默認值。

表1 實驗參數

5.1 道路網絡規模大小對查詢時間的影響

圖6 給出了在POI 對象數、查詢請求數K和方向關系謂詞3 個參數不變情況下,道路網絡大小對CDR-CKNN 算法和IMA/GMA 算法CPU 運行時間的對比情況。可以看出,當道路網絡規模較小時,2 種算法的CPU 運行時間并沒有太大差距；當道路網絡規模增加時,2 種算法之間的差距越來越明顯,道路網為150K 時,IMA/GMA 算法是CDR-CKNN算法運行時間的2 倍；道路網為250K 時,IMA/GMA 算法是CDR-CKNN 算法運行時間的3.3 倍。這是因為道路網絡規模增加時,POI 對象的分布密度(本文用POI 對象數與道路網規模的比值來衡量)降低,IMA/GMA 算法計算最短路徑時采用的是盲目擴展方式,需要遍歷大量的網絡邊；而CDRCKNN 算法通過方向關系謂詞可以快速過濾掉與查詢結果無關的邊,大幅縮短計算最短路徑的時間。

圖6 道路網規模對CPU 運行時間的影響

5.2 興趣點對象數量對查詢時間的影響

圖7 給出了在道路網規模、查詢請求數K和方向關系謂詞3 個參數不變情況下,POI 對象數量對CDRCKNN 算法和IMA/GMA 算法CPU 運行時間的對比情況。POI 對象數量決定了對象在道路網絡上的分布密度,當POI 數量較少時,道路網上POI 對象分布稀疏,為查詢到K個最近鄰對象,IMA/GMA 算法需要不斷擴展搜索網絡,CDR-CKNN 算法也需要不斷擴展方向區域的查詢半徑r,2 種算法的CPU 運行時間都較高；但是CDR-CKNN 算法采用了預計算技術,大大降低了計算最短路徑的時間,因此在POI 對象數量為5K 時,CPU 運行時間明顯優于IMA/GMA 算法。隨著POI 對象數量的增加,2 種算法的CPU 運行時間都減少并呈現出平緩下降的趨勢。

圖7 興趣點對象數量對CPU 運行時間的影響

5.3 方向關系謂詞對查詢時間的影響

圖8 給出了采用四方向模型和八方向模型定義方向關系謂詞時對查詢算法性能的影響情況。從定義7 可以看出,八方向模型與四方向模型相比,細化了參考對象周圍的空間區域,定義的方向關系謂詞限制了更小的KNN 查詢區域,因此,從圖8 可以看出,在相同條件下,八方向模型定義的方向關系謂詞查詢有更少的CPU 運行時間,并且CDR-CKNN 算法仍然優于IMA/GMA 算法,平均性能提高1.5 倍～3 倍。

圖8 不同方向關系模型對查詢性能的影響

6 結束語

本文利用方向關系可以作為空間查詢選擇條件這一特點,提出基于方向關系謂詞約束的道路網絡連續K 最近鄰查詢算法(CDR-CKNN)。為提高KNN 查詢速度和更新速度,算法做了3 點改進：(1)將方向關系謂詞轉化為開放圖形區域,與道路網絡層進行Intersect 運算,快速過濾掉與查詢結果無關的道路邊；(2)利用預計算的道路結點之間的最短路徑,快速計算查詢對象與查詢區域內POI 對象之間的最短路徑,從而得到K個最近鄰對象；(3)建立三層索引結構,將靜態的道路網和動態的移動對象分別存儲,便于移動對象位置的不斷更新。實驗結果表明,本文提出的CDR-CKNN 算法的查詢性能比IMA/GMA 算法提高2 倍～3.3 倍。今后工作的重點是將方向關系謂詞約束與反向最近鄰查詢相結合,提高道路網絡上反向最近鄰查詢算法的性能。

[1]Kim Hyeong,Chang Jae-Woo.K-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks[J].Journal of Computer Science and Technology,2013,28(4)：585-596.

[2]Mouratidis K,Yiu Man-Lung,Papadias D.Continuous Nearest Neighbor Monitoring in Road Networks[C]//Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul,Korea：ACM Press,2005：43-54.

[3]Wang Haojun,Zimmermann R.Location Based Query Processing on Moving Objects in Road Networks[C]//Proceedings of the16th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems.Vienna,Austria：[s.n.],2007：143-158.

[4]Demiryurek U,Banaei K F,Shahabi C.Efficient Continuous Nearest Neighbor Query in Spatial Networks Using Euclidean Restriction[C]//Proceedings of International Symposium on Spatial and Temporal Database.Aalborg,Denmark：[s.n.],2009：25-43.

[5]廖 巍,張 琪,吳曉平,等.網絡環境下的連續k 近鄰查詢處理研究[J].小型微型計算機系統,2010,31(4)：666-671.

[6]趙 亮,景 寧,陳 犖,等.面向多核多線程的移動對象連續K 近鄰查詢[J].軟件學報,2011,22(8)：1805-1815.

[7]Shekhar S,Liu Xuan.Direction as a Spatial Object：A Summary of Results[C]//Proceedings of the 6th International Symposium on Advance in Geographic Information Systems.[S.l.]：ACM Press,1998：69-75.

[8]石 靜,劉永山.基于開放區域的定量方向關系查詢技術[J].計算機工程,2007,33(22)：89-91,94.

[9]郝曉紅,張麗平,李 松.三維空間中3DR44 方向關系表示模型[J].計算機工程,2011,37(1)：75-77.

[10]de Almeida V T,Güting R H.Using Dijkstra’s Algorithm to Incrementally Find the k-nearest Neighbors in Spatial Network Databases[C]//Proceedings of 2006 ACM Symposium on Applied Computing.Dijon,France：ACM Press,2006：58-62.

[11]Papadias D,Zhang J,Mamoulis N.Query Processing in Spatial Network Databases[C]//Proceedings of the 29th VLDB Conference.Berlin,Germany：ACM Press,2003：802-813.

[12]Brinkhoff T.A Framework for Generating Networkbased Moving Objects[J].GeoInformatica,2002,6(2)：153-180.