道路網(wǎng)絡(luò)中基于方向關(guān)系約束的CKNN 查詢

孫海龍 ,王霓虹 ,王春艷

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

1 概述

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

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

為提高CKNN 查詢速度,本文將方向關(guān)系作為查詢約束條件引入到算法中,提出基于方向關(guān)系約束的CKNN 查詢CDR-CKNN 算法,處理道路網(wǎng)絡(luò)環(huán)境下連續(xù)K 最近鄰查詢問題。

2 問題描述及相關(guān)定義

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

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

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

圖1 道路網(wǎng)絡(luò)及其對應(yīng)有向帶權(quán)圖

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

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

圖2 部分道路結(jié)點的鄰接鏈表

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

為提高系統(tǒng)的執(zhí)行速度,預(yù)計算道路網(wǎng)絡(luò)中各頂點的最短路徑[10],在存儲在數(shù)據(jù)庫中,為計算道路網(wǎng)上任意2 個對象之間的最短路徑做基礎(chǔ)。

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

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

3 索引結(jié)構(gòu)設(shè)計

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

圖3 道路網(wǎng)絡(luò)及移動對象索引結(jié)構(gòu)

4 CKNN 查詢算法

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

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

移動對象運(yùn)行在道路網(wǎng)中,當(dāng)查詢對象發(fā)出查詢請求時,首先通過索引結(jié)構(gòu)中的移動對象列表和hash 表的鏈接關(guān)系找到查詢對象所在的道路邊；然后將查詢中的方向關(guān)系謂詞通過構(gòu)建開放圖形轉(zhuǎn)化為ArcGIS 中的Geometry 類；其次將Geometry 圖形與道路網(wǎng)圖層作相交運(yùn)算,獲得查詢區(qū)域內(nèi)的道路邊,通過索引結(jié)構(gòu)獲得查詢區(qū)域內(nèi)的移動對象,獲得候選結(jié)果集；最后利用預(yù)計算的道路網(wǎng)結(jié)點數(shù)據(jù)計算查詢對象和候選結(jié)果集中各對象的最短路徑,精煉出最終的KNN 查詢結(jié)果。

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

圖4 錐形模型

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

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

算法1KnnQuery(q,dp,K)

輸入R-Tree

輸出ResultList 滿足查詢條件的KNN 結(jié)果集

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

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

圖5 KNN 查詢算法實例

4.2 連續(xù)K 最近鄰查詢實現(xiàn)

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

算法2UpdateKnnQuery(q,dp,K)

輸入R-Tree

輸出ResultList 滿足查詢條件的KNN 結(jié)果集

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

5 實驗對比及分析

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

表1 實驗參數(shù)

5.1 道路網(wǎng)絡(luò)規(guī)模大小對查詢時間的影響

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

圖6 道路網(wǎng)規(guī)模對CPU 運(yùn)行時間的影響

5.2 興趣點對象數(shù)量對查詢時間的影響

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

圖7 興趣點對象數(shù)量對CPU 運(yùn)行時間的影響

5.3 方向關(guān)系謂詞對查詢時間的影響

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

圖8 不同方向關(guān)系模型對查詢性能的影響

6 結(jié)束語

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

[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]廖 巍,張 琪,吳曉平,等.網(wǎng)絡(luò)環(huán)境下的連續(xù)k 近鄰查詢處理研究[J].小型微型計算機(jī)系統(tǒng),2010,31(4)：666-671.

[6]趙 亮,景 寧,陳 犖,等.面向多核多線程的移動對象連續(xù)K 近鄰查詢[J].軟件學(xué)報,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]石 靜,劉永山.基于開放區(qū)域的定量方向關(guān)系查詢技術(shù)[J].計算機(jī)工程,2007,33(22)：89-91,94.

[9]郝曉紅,張麗平,李 松.三維空間中3DR44 方向關(guān)系表示模型[J].計算機(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.