高效的多關鍵詞匹配最優路徑查詢算法KSRG

金鵬飛，牛保寧，張興忠

(太原理工大學 計算機科學與技術學院，太原 030024)

(*通信作者電子郵箱zhangxingzhong@tyut.edu.cn)

高效的多關鍵詞匹配最優路徑查詢算法KSRG

金鵬飛，牛保寧，張興忠*

(太原理工大學 計算機科學與技術學院，太原 030024)

(*通信作者電子郵箱zhangxingzhong@tyut.edu.cn)

為改進基于關鍵詞的最優路徑查詢算法，在大規模圖以及多查詢關鍵詞下復雜度過高與可擴展性不足的缺陷，依據查詢關鍵詞序列構建候選路徑的策略提出一種高效查詢算法。該算法在路徑構建過程中優先滿足查詢關鍵詞的全包含條件，以關鍵詞引導下的路徑拓展替代盲目的鄰邊拓展，從而高效地構建候選路徑；通過變量縮放與無效路徑裁剪，將問題求解復雜度由階乘級轉化為多項式級，進一步降低算法復雜度，提升可擴展性。通過四組圖數據集下的實驗，驗證了算法在查詢效率與可擴展性上的提升。

基于關鍵詞的最優路徑查詢；復雜度；可擴展性

0 引言

隨著移動互聯網技術與地理定位技術的發展，基于位置的服務當下被廣泛應用于交通、物流、旅游等多個領域。在眾多基于位置的服務中，地圖服務是一項極為常見的服務。根據位置信息為用戶在路網空間中查詢一條合適的路徑是地圖服務的一項重要功能[1]。考慮到在Web資源與地圖服務結合的背景下，路徑查詢功能應不再局限于在給定起點與終點的情況下單純返回兩點間最短路徑。為滿足用戶個性化的行程需求，針對特殊路徑，提出高效的查詢方法尤為重要。

在生活中可以考慮如下場景：用戶來到了一個陌生的城市，希望搜尋一條最受歡迎的旅游路線，該路線從指定起點出發，途經所有與用戶指定關鍵詞相關的興趣點(如自然景區、文化古跡、特色美食)，最終到達用戶指定的終點，此外路徑需滿足游客有限的行程預算。

該類路徑查詢問題被定義為基于關鍵詞的最優路徑查詢(Keyword-aware Optimal Route Search， KORS)[2-3]。KORS是空間關鍵詞查詢中的一類特殊查詢[4]，能夠為地圖服務在旅游行程中的路線規劃提供有效支持。與傳統的單源最短路徑(Single Source Shortest Path)查詢不同，KORS綜合考慮路徑關鍵詞覆蓋條件、路徑行程代價約束以及路徑流行度三類因素間的組合優化性，該類問題為NP-hard問題[2]，實際路徑的搜索空間復雜度為O(dn)(d為圖中頂點最大出度)。

目前針對KORS算法主要基于鄰邊拓展的路徑構建策略，該策略自起點出發通過不斷拓展當前路徑終點的所有鄰邊以產生新的子路徑，直到路徑到達查詢終點。該過程實際枚舉了起點與終點間所有可行路徑，由于在KORS的問題求解中，關鍵是通過路徑拓展構建滿足查詢約束的可行路徑，因此當查詢關鍵詞個數較多、起點終點間最優路徑的頂點個數較多或者部分查詢關鍵詞分布稀疏時，鄰邊拓展的路徑構建策略將枚舉大量的中間路徑，造成算法在空間、時間上開銷驟增，可擴展性變差。

為解決上述問題，本文提出基于關鍵詞序列的路徑構建 (KeywordSequenceRouteGenerating，KSRG)算法。該算法提出基于關鍵詞序列的路徑構建方案，在路徑拓展過程中優先考慮路徑對查詢關鍵詞的包含情況，采用關鍵詞引導下的有效路徑拓展代替盲目的鄰邊拓展，避免無關頂點的遍歷，提高候選路徑的構建效率；其次采用完全多項式時間近似策略，以及在查詢中對無效中間結果的及時裁剪，對問題解進行近似求解，從而將搜索空間復雜度模限定在多項式級，提升算法可擴展性。綜上所述，本文的主要工作總結如下：

1)針對KORS提出基于關鍵詞序列路徑構建算法——KSRG算法，在路徑拓展過程中優先滿足查詢關鍵詞的全包含條件，對查詢結果進行高效的近似求解；

2)運用四組圖數據集，對各類算法進行充分實驗測試，并對查詢效率進行對比，驗證本文算法的有效性以及相對現有算法在查詢性能上的提升效果。

1 相關工作

1.1 空間關鍵詞查詢

近年來學者們針對空間關鍵詞查詢的研究[5-8]提出了多種查詢，如：最優k鄰居查詢(top-kNN)、范圍查詢(Range query)、逆向最鄰近查詢(ReversekNN query)，這些查詢對空間對象的空間鄰近度與文本相似性進行考察，但查詢粒度局限為單一個體，無法解決多個鄰接的空間對象組合相連下最優路徑問題。文獻[6]在歐氏空間中提出了滿足關鍵詞全包含下的一組鄰近空間實體集合的查詢；文獻[9]在路網空間下進行最優子區域的高效查詢。上述查詢返回一組興趣點集合，但無法適用于路徑形式下的組合優化問題。

1.2 最優路徑查詢

最優路徑查詢是基于位置的服務中被廣泛研究的一個問題[2-3，10-13]。文獻[10]于空間數據庫領域最先提出一種新的行程規劃查詢(Trip Plan Query，TPQ)，TPQ在指定的空間兩點間搜索一條經過所有指定類別對象且長度最小的路徑，如在用戶的住處與工作地點間查找一條經過便利店、加油站、銀行的最短路徑，該類查詢問題為廣義旅行商問題(Generalized Traveling Salesman Problem， GTSP)的特例，為NP難題。與TPQ問題類似，文獻[11]提出最優序列路徑 (Optimal Sequenced Route，OSR)查詢問題，搜索一條由空間中某點出發，按規定類別訪問順序，經過所有類別對象且長度最短的路徑，如從用戶當前所在位置出發找到一條依次經過銀行、加油站、影院的最短路徑，該查詢固定了對象的訪問順序，為TPQ問題的一類特例。文獻[12]提出了多規則局部有序路徑(Multi-Rule Partial Sequenced Rout，MRPSR)查詢，該查詢區別于OSR查詢中固定的類別訪問順序，僅對部分不同對象的訪問順序限定條件，如用戶必需在訪問加油站前優先訪問銀行。文獻[13]提出BBS(Batch Backward Search)與SBS(Simple Backward Search)兩類算法解決任意訪問規則下的最優路徑查詢問題，相比文獻[12]可滿足更為多樣的訪問約束。文獻[14]在旅游背景下提出體驗式路徑查詢(Short-term Experience Route Search，SERS)。文獻[15]基于貪婪策略提出了三種高效的旅游行程規劃算法，折中游客行程預算與景點流行度，返回一條近似最優行程路徑。

在TPQ、OSR、MRPSR查詢以及SERS中，對象類別屬性較為單一，包含信息量有限，使得路徑難以精確匹配用戶個性化要求。此外由于上述路徑查詢忽略了路徑代價預算，因此不能較好地滿足實際生活場景中的行程問題。文獻[15]雖然考慮了路徑行程中各類預算條件的滿足，但路徑中興趣點的選擇較為固定，無法適應不同用戶的多種個性化要求。

1.3 KORS

為使規劃的路線能夠滿足用戶個性化行程需求，同時在代價預算上保持合理性，基于關鍵詞下的最優路徑查詢(KORS)是一種合適的查詢類型。該查詢最早在文獻[2]中被提出，與歐氏空間下的路徑問題[10-12]不同，KORS在路網空間下查詢返回一條覆蓋所有用戶指定關鍵詞，同時滿足行程預算(如費用、時間)且流行度最大的路徑。該類路徑問題為權值受限最短路徑(Weight Constrained Shortest Path，WCSP)問題的一個特例，為NP難題[2]。基于鄰邊拓展的路徑構建策略，OSScalling和BucketBound算法[2-3]實現了多項式復雜度下的問題近似求解。然而由于路徑拓展策略，算法在大規模的無向圖以及多關鍵詞條件下進行時，存在復雜度過高、空間開銷極大、伸縮性不理想的缺陷。

2 問題定義

2.1 問題抽象

將旅游行程抽象為如圖1所示的一幅連通圖G=(V,E)。圖G中，頂點集V中每個頂點v代表了一個興趣點。v擁有兩類屬性：1)地理位置坐標〈經度, 緯度〉，符號表示為v.loc;2)關鍵詞集合，〈關鍵詞1,關鍵詞2,關鍵詞3…〉(個數不大于5)，符號表示為v.ψ。圖1中各個頂點所帶的關鍵詞信息如表1所示。

圖1 圖的結構

表1 頂點關鍵詞信息

Tab.1Informationofvertexkeyword

頂點關鍵詞集頂點關鍵詞集v0t4t6t7v4t4t6v1t3t5v5t2t8t10v2t2t9t10v6t1v3t1t11t12v7t3t9

邊集E中的每條邊表示連接兩處興趣點的直通行程e。e帶有兩類權值：1)代價權值(圖中括號外的數值)，表示通過該行程所需的行程代價(根據不同場景可為路段的時耗或距離)；2)流行度權值(圖中括號內的數值)，表示該行程的流行度。若vi到vj存在直達路段(vi,vj)∈E,則b(vi,vj)為邊的代價權值，p(vi,vj)為邊的價值權值。

在KORS應用場景中，最優路徑查詢Q=(vs,vt,ψ,Δ)包含四類查詢參數，其中：vs為用戶指定的行程起點(可為圖1任意某個興趣點)；vt代表用戶指定的行程終點；ψ表示一組用戶指定的關鍵詞集合；Δ表示路徑代價上限值。

將由起點vs至終點vt的路徑集合表示為Rs,t,根據查詢Q中參數，若某路徑r∈Rs,t且滿足：1)BS(r)<Δ；2)r.ψ?Q.ψ,則路徑r為一條可行路徑，所有可行路徑的集合表示為R,KORS的最優路徑符號表示為ropt，ropt即為可行路徑集合R中擁有最大流行度的路徑。具體形式化描述如下：

2.2 求解轉化

o(vi,vj)=log(1/p(vi,vj))

(1)

定理1 在圖G中擁有最大流行度PS(r)的路徑，擁有最小目標值OS(r)。

(2)

證畢。

根據定理1，KORS所求最優路徑ropt即為滿足查詢約束條件，且擁有最小目標值的路徑，形式化描述為：

3 KSRG算法

3.1 準備工作

為在算法執行中及時過濾無效的中間結果，提高問題求解效率，在算法執行前，需進行如下準備工作。

工作1 路徑預處理。為在搜索過程中對局部路徑的后續拓展情況作預判，及時去除不滿足約束條件的中間結果，采用弗洛伊德算法[17]對圖G中任意兩點求其間擁有最小OS(r)與最小BS(r)的路徑，兩類特殊路徑符號表示為τi, j、σi, j。

工作2 構建倒排索引。抽取圖G中各興趣點的所有關鍵詞構成一非重關鍵詞集合。該集合中每個關鍵詞對應一個倒排表，記錄包含該關鍵詞的興趣點的集合。通過倒排索引的構建，含有查詢關鍵詞的興趣點可被優先篩選。

3.2 算法描述

KSRG算法首先采用關鍵詞序列路徑構建來提高可行路徑構建效率，此基礎上通過完全多項式時間近似策略進一步實現高效、可擴展性更優的KORS。以下首先對這兩部分進行說明。

3.2.1KSRG預備知識

KSRG核心在于路徑拓展過程中優先滿足查詢關鍵詞的全包含條件，進行關鍵詞引導下的路徑拓展。在闡述思路前，有如下定義陳述。

定義1 關鍵詞頂點。給定查詢Q=(vs,vt,ψ,Δ),關鍵詞ti∈ψ。若vm.ψ包含ti,且BS(σs,m)+BS(σm,t)<Δ,則vm為關鍵詞ti對應的關鍵詞頂點，ti對應的所有關鍵詞頂點構成的集合符號表示為Vti。

定義2 關鍵詞路徑。關鍵詞ti∈vm,關鍵詞tj∈vn,路徑r∈Rm,n,若OS(r)=OS(τm,n),則路徑r為一條關鍵詞路徑。

定義3 關鍵詞頂點序列。給定查詢Q=(vs,vt,ψ,Δ),其中ψ=〈ti1,ti2,…,tin〉,對于某條包含所有查詢關鍵詞且滿足代價約束的可行路徑r,根據每個查詢關鍵詞在路徑r拓展過程中被先后覆蓋到的順序(僅考慮每個關鍵詞在路徑中第一次被覆蓋的次序)，可得關鍵詞覆蓋序列st=〈ts1,ts2,…,tsn〉,滿足該序列的關鍵詞頂點序列為sv=〈vs1,vs2,…,vsn〉(vs1∈Vts1,vs2∈Vts2,…,vsn∈Vtsn)。

定理2OS(KSRopt)<|ψ|OS(ropt),其中|ψ|為查詢關鍵詞個數。

證明 將忽略Δ,給定新查詢Q′=(vs,vt,ψ),文獻[10]基于貪婪策略提出AMD算法可對一條包含ψ中所有關鍵詞且有最短長度的路徑rmin進行近似求解，令近似求解得的路徑符號為rMD,若將路徑長度作為路徑目標值，則有OS(rMD)<|ψ|OS(rmin)[10]。由于rMD為KSR，故有OS(KSRopt)

證畢。

根據定理2，采用KSRG對KORS的最優路徑ropt進行近似求解，基本思想為：根據查詢關鍵詞集，枚舉該集合下各個關鍵詞覆蓋序列對應的可行關鍵詞頂點序列，計算其對應的關鍵詞序列路徑的目標值。在所有滿足查詢約束的可行關鍵詞路徑中，擁有最小目標值的路徑即為最優路徑ropt。

3.2.2 完全多項式時間近似策略

在3.2.1節中，枚舉所有關鍵詞頂點序列依然是一項復雜度較大的工作。給定一個查詢，查詢關鍵詞為Q.ψ,該工作的復雜度為O(nk×k!)(其中k=|Q.ψ|,n=max{|Vtm||tm∈Q.ψ})。

為避免此類復雜度下的問題求解，采用完全多項式時間近似策略(FullyPolynomial-TimeApproximationScheme，FPTAS)[18-19]，通過相關變量轉化，可將問題求解的規模轉變為多項式級，具體步驟如下所述。

首先定義比例因子

θ=(εmin{OS(τi, j)}min{BS(σi, j)})/Δ

在KSRG構建策略中，路徑由起點vs出發，通過關鍵詞路徑拓展至所有之前未被包含的關鍵詞對應的關鍵詞頂點，產生更長關鍵詞序列對應的關鍵詞序列路徑；所有子路徑繼續由當前拓展終點重復上述拓展步驟直到路徑關鍵詞序列包含所有查詢關鍵詞。考慮到在路徑拓展過程需記錄下所有枚舉的局部路徑，因此需以適當方式表示這些中間結果。

針對標簽操作產生的大量中間結果(路徑標簽)根據一定的優先級，可決定哪條路徑標簽優先進行下一步拓展，使路徑拓展盡可能朝最優解所在方向推進，具體規則如下定義。

定義8 標簽優先級。綜合路徑標簽中的λ、OS′和BS三部分判定標簽優先級：

1)當兩條路徑對應的路徑標簽包含的查詢關鍵詞個數不同時，包含查詢關鍵詞個數越多的路徑，其優先級越高；

2)當兩條路徑對應的路徑標簽中包含的查詢關鍵詞個數相同時，路徑目標值越小，路徑優先級越高；

3)當兩條路徑對應的路徑標簽包含的查詢關鍵詞個數、路徑目標值都相同時，路徑代價值越小路徑優先級越高。

根據定理2，KORS求解的復雜度與Δ呈多項式相關性，與k呈指數相關性(k的取值通常不大)。

3.2.3 算法步驟

綜合3.2.1節與3.2.2節中各項定義和定理，提出KSRG算法。算法的基本思想為枚舉各關鍵詞序列下的有效路徑標簽：首先篩選各個查詢關鍵詞對應的所有關鍵詞頂點，之后路徑由起點vs出發按關鍵詞序列進行關鍵詞路徑拓展，產生包含更多查詢關鍵詞的關鍵詞序列路徑，在此過程中每次選擇優先級最高的中間路徑進行拓展，并及時檢查拓展所得路徑裁剪無效路徑標簽。重復此過程直到產生所有終點vt對應的包含全部查詢關鍵詞的路徑標簽，篩選滿足查詢約束且有最小修正目標值的路徑標簽，即為最優路徑ropt。具體描述如下：

算法1KSRG算法。

輸入 圖G，查詢Q=(vs,vt,ψ,Δ);

輸出 最優路徑標簽LL。

1)

初始化隊列Q為空隊列，LL為Null，上界值U為無窮大；

2)

獲取Q.λ中每個關鍵詞ti對應的Vti;

3)

4)

WhileQ中元素不為空do

5)

6)

7)

Foreachvj∈Vtido

8)

9)

10)

//舍棄該路徑,即停止后續拓展

11)

Else

12)

13)

14)

//無效路徑被舍棄，即停止后續拓展

15)

Else

16)

17)

18)

刪除Q中相關無效標簽；

19)

Else

20)

21)

22)

23)

ReturnLL;

標簽檢查函數checkLabel。

輸出 布爾值flag。

①

初始化布爾值flag=false，無效標簽表UL；

②

Foreachl∈vj.listdo

③

④

flag=true;

⑤

returnflag;

⑥

⑦

將l加入UL;

⑧

list中刪除l;

⑨

Returnflag;

3.2.4 算法分析

近似度分析 由于完全多項式時間近似策略，因此最終算法求得的解r′為ropt的近似解。設以KSRG方式實際求得的最優路徑為re。由于完全多項式時間近似策略，關鍵詞路徑目標值與修正目標值之間滿足OS′(τi, j)=?θ-1OS(τi, j)」,因此滿足如下式關系：

OS(τi, j)-θ≤θOS′(τi, j)≤OS(τi, j)

(3)

令rd表示可行路徑中有最小OS′(r)的路徑，可得如下關系：

(4)

對式(4)最右部分進一步推導可得：

4 實驗與評估

對提出的KSRG算法進行實驗測試，并與OSScaling算法、BucketBound算法進行性能對比。所有算法均由Java語言編程實現，實驗在PC上執行，處理器型號為AMDA8- 7100 1.8GHz，主存為4.0GB，操作系統為Windows8，JDK版本為1.7，Java虛擬機堆空間設定為512MB。

4.1 實驗數據集

實驗采用文獻[20]提供的路網數據集，本文截取路網COL、NW、DE、ME中的部分點集與邊集，通過程序去除其中的孤立點與冗余邊構建連通子圖G1、G2、G3、G4；結合文獻[6]中的關鍵詞數據集，為圖中的頂點分配相應關鍵詞構成本文數據集，具體如表2所示。

表2 實驗圖數據集

本文隨機使用范圍在0到1間的小數對圖中所有邊的流行度權值進行賦值，流行度權值代表了某條邊對應的路段熱度，流行度權值越大表示該路段被游客訪問的概率越高。

4.2 算法性能對比

4.2.1 不同查詢關鍵詞個數下運行結果

為比較算法在不同查詢關鍵詞個數下的性能，在圖G2中，隨機選定兩個頂點作為路徑起點與終點，設定查詢的代價約束為50km，測試算法分別在關鍵詞數目為2、4、6、8、10共五種情況下的查詢性能，每種查詢各運行5次，對運行時間取平均值，結果具體如圖2所示。

圖2 不同關鍵詞個數下查詢響應時間

根據圖2，KSRG算法的查詢響應時間遠小于OSScaling以及BucketBound算法。OSScaling算法的查詢響應時間最長，由于在查詢關鍵詞個數大于8時，運行時間大于10s，因此不在圖中標注。當查詢關鍵詞個數大于6時，OSScaling、BucketBound算法的響應時間顯著增加，這是因為兩者都采用鄰邊拓展的路徑構建原則，將產生大量的路徑標簽；KSRG算法通過關鍵詞路徑拓展構建路徑，僅考慮查詢關鍵詞相關的頂點，將產生更少路徑標簽，降低中間結果的處理代價因而響應時延更小。三類算法在查詢過程中產生的路徑標簽的個數統計如圖3所示。根據圖3，OSScaling算法在查詢中產生的路徑標簽數量約為KSRG算法的100倍，BucketBound算法產生的路徑標簽數量約為KSRG算法的10倍。大量路徑標簽的存儲，使得OSScaling和BucketBound算法在多關鍵詞查詢過程中的空間開銷過大，又由于查詢過程中大量中間結果(路徑標簽)的處理操作，進而嚴重限制了查詢效率。

4.2.2 不同查詢代價約束下的運行結果

為比較不同代價約束對算法查詢的影響，選定在圖G4中進行查詢測試。在圖G4中同樣隨機選定兩個頂點作為路徑起點與終點，設定查詢關鍵詞個數為6，測試算法在代價約束為40、50、60、70、80km共5類查詢的運行情況，每類查詢運行5次，對結果取平均值，如圖4所示。根據圖4，三類算法的查詢響應時間隨代價約束值的變大，呈現先減小后逐漸趨于穩定的趨勢。這是因為，在一定范圍內，較大的查詢約束值能夠使算法更早地求得可行路徑標簽，從而裁剪更多中間結果；當查詢約束值繼續增大時，由于最優解限定了目標值的上界，問題的解空間不再增大，故查詢時間基本不變。三類算法在不同代價值約束下在查詢過程中產生的路徑標簽數統計，如圖5所示。

圖3 不同查詢關鍵詞個數下路徑標簽產生數

圖4 不同查詢代價約束下查詢運行時間

圖5 不同查詢代價約束下路徑標簽產生個數

綜合圖4和圖5，在不同查詢代價約束下，KSRG算法相比OSScaling算法及BucketBound算法，有更少的查詢響應時間以及更小的空間開銷代價。

4.2.3 不同數據集下的運行結果

為比較算法在不同數據集對應的圖下的運行結果，在圖G1、G2、G3、G4中隨機選定兩個頂點作為查詢的起點與終點，統一設定查詢關鍵詞個數為6，代價約束為50km，不同圖下的查詢各運行5次，對結果取平均，如圖6所示。根據圖6，OSScaling、BucketBound算法的查詢響應時間隨圖尺寸變大呈線性增大趨勢，因為隨著圖的變大，兩種算法在鄰邊拓展過程中將遍歷更多的頂點與邊，產生更多的路徑標簽，增加查詢處理代價。KSRG算法在不同尺寸圖中運行時間呈現波動趨勢，時間變化與圖尺寸大小沒有明顯關聯，因為KSRG算法通過關鍵詞路徑拓展產生關鍵詞序列路徑，該過程中對關鍵詞頂點進行拓展，避免了無關頂點的遍歷，故在代價約束確定后，查詢代價不受圖中頂點總數影響。

圖6 不同圖中的查詢響應時間

4.3 相關因素評估

考慮KSRG的路徑拓展策略，影響查詢響應性能的主要因素為查詢關鍵詞的頻度和起點終點相對位置。

4.3.1 不同頻度的查詢關鍵詞對查詢的影響

為比較關鍵詞的頻度對算法查詢響應時間的影響，構建Q1、Q2、Q3和Q4共四類查詢，每類查詢都設定相同查詢起點與終點，并統一查詢代價約束為30km，統一查詢關鍵詞個數為6。每類查詢的關鍵詞頻度不同，具體如表3所示。

表3 查詢中的關鍵詞頻度

在圖G3中對上述四類查詢進行測試，每類查詢各運行5次，對查詢響應時間取平均值，具體結果如表4所示。

表4 查詢關鍵詞頻度對查詢響應時間的影響 ms

根據表3，KSRG算法對查詢關鍵詞的頻度敏感。這是因為關鍵詞頻度越大，在每種關鍵詞序列將枚舉更多可行的關鍵詞頂點序列，從而在查詢過程產生更多路徑標簽。

4.3.2 查詢起點與終點相對位置對響應時間的影響

為比較查詢中不同的起點與終點的相對位置對KSRG算法響應時間的影響，特構建四組查詢Q5、Q6、Q7、Q8。每組查詢設定代價約束為50km；統一查詢關鍵詞個數為6；選擇相距不同歐氏距離的起點與終點，具體如表5所示。

將上述四組查詢在圖G3中進行測試，結果如表6所示。根據表5，起點與終點間的歐氏距離越大，算法響應時間越長，這是因為在較大歐氏距離間隔下，兩點間將包含更多關鍵詞頂點，因此在查詢過程也將產生更多的關鍵詞序列路徑對應的路徑標簽。

表5 查詢點位置間歐氏距離

表6 查詢點間距離對查詢響應時間的影響 ms

5 結語

為解決KORS在大圖查詢以及多關鍵詞查詢中復雜度過高、空間開銷過大以及伸縮性較差的缺陷，本文提出了關鍵詞序列路徑構建算法——KSRG算法。該算法優先滿足路徑對查詢關鍵詞的全包含條件，采用關鍵詞引導下的路徑拓展提高可行路徑的構建效率，從而減小路徑構建過程中的空間開銷；此外采用完全多項式時間近似策略，通過對路徑目標值的倍率轉換以及在查詢過程中無效的路徑標簽過濾刪除，進一步將問題求解的規模由階乘級轉化為多項式級。本文利用四組數據集對各類算法的查詢性能作了綜合對比，并分析影響查詢效率的相關因素。實驗表明，KSRG算法相比OSScaling和BucketBound算法在時間與空間開銷以及可擴展性上有更優性能。

)

[1]RESNAR,LALLUA.Optimalroutequeriesforroadnetworkswithuserinterest[J].InternationalJournalofComputerTrendsandTechnology, 2015, 21(1): 41-45.

[2]CAOX,CHENL,CONGG,etal.Keyword-awareoptimalroutesearch[J].ProceedingsoftheVLDBEndowment, 2012, 5(11): 1136-1147.

[3]CONGG,CHENL,CAOX,etal.KORS:keyword-awareoptimalroutesearchsystem[C]//ICDE’13:Proceedingsofthe2013IEEEInternationalConferenceonDataEngineering.Washington,DC:IEEEComputerSociety, 2013: 1340-1343.

[4]CONGG,JENSENCS.Queryinggeo-textualdata:spatialkeywordqueriesandbeyond[C]//SIGMOD’16:Proceedingsofthe2016InternationalConferenceonManagementofData.NewYork:ACM, 2016: 2207-2212.

[5]CONGG,JENSENCS,WUD.Efficientretrievalofthetop-kmost relevant spatial Web objects [J].Proceedings of the VLDB Endowment, 2009, 2(1): 337-348.

[6] CAO X, CONG G, JENSEN C S, et al.Collective spatial keyword querying [C]// SIGMOD ’11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data.New York: ACM, 2011: 373-384.

[7] CHEN L, CONG G, JENSEN C S, et al.Spatial keyword query processing: an experimental evaluation [J].Proceedings of the VLDB Endowment, 2013, 6(3): 217-228.

[8] CHOUDHURY F M, CULPEPPER J S, SELLIS T, et al.Maximizing bichromatic reverse spatial and textualknearest neighbor queries [J].Proceedings of the VLDB Endowment, 2016, 9(6): 456-467.

[9] CAO X, CONG G, JENSEN C S, et al.Retrieving regions of interest for user exploration [J].Proceedings of the VLDB Endowment, 2014, 7(9): 733-744.

[10] LI F F, CHENG D, HADJIELEFTHERIOU M, et al.On trip planning queries in spatial databases [C]// Proceedings of the 9th International Symposium on Advances in Spatial and Temporal Databases, LNCS 3633.Berlin: Springer-Verlag, 2005: 273-290.

[11] SHARIFZADEH M, KOLAHDOUZAN M, SHAHABI C.The optimal sequenced route query [J].The VLDB Journal, 2008, 17(4): 765-787.

[12] CHEN H, KU W-S, SUN M-T, et al.The multi-rule partial sequenced route query [C]// GIS ’08: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York: ACM, 2008: Article No.10.

[13] LI J, YANG Y, MAMOULIS N.Optimal route queries with arbitrary order constraints [J].IEEE Transactions on Knowledge and Data Engineering, 2013, 25(5): 1097-1110.

[14] 宋曉宇,許鴻斐,孫煥良,等.基于簽到數據的短時間體驗式路線搜索[J].計算機學報,2013,36(8):1693-1703.(SONG X Y, XU H F, SUN H L, et al.Short-term experience route search based on check-in data [J].Chinese Journal of Computers, 2013, 36(8): 1693-1703.)

[15] 鮑金玲,楊曉春,王斌,等.一種支持約束關系的高效的行程規劃算法[J].小型微型計算機系統,2013,34(12):2702-2707.(BAO J L, YANG X C, WANG B, et al.An efficient trip planning algorithm under constraint [J].Journal of Chinese Computer Systems,2013, 34(12): 2702-2707.)

[16] CHEN Z, SHEN H T, ZHOU X.Discovering popular routes from trajectories [C]// ICDE ’11: Proceedings of the 2011 IEEE 27th International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2011: 900-911.

[17] FLOYD R W.Algorithm 97: shortest path [J].Communications of the ACM, 1962, 5(6): 345.

[18] CORMEN T H, LEISERSON C E, RIVEST R L, et al.Introduction to algorithms [M].3rd ed.Cambridge, MA: MIT Press, 2009: 450-462.

[19] DUMITRESCU I, BOLAND N.Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem [J].Networks, 2003, 42(3): 135-153.

[20] ABEYWICKRAMA T, CHEEMA M A, TANIAR D.K-nearest neighbors on road networks: a journey in experimentation and in-memory implementation [J].Proceedings of the VLDB Endowment, 2016, 9(6)： 492-503.

This work is partially supported by the National Natural Science Foundation of China (61572345), the National Key Technology R&D Program (2015BAH37F01).

JIN Pengfei, born in 1992, M.S.candidate.His research interests include spatial data query.

NIU Baoning, born in 1964, Ph.D., professor.His research interests include big data, autonomic computing and performance management of database system.

ZHANG Xingzhong, born in 1964, M.S., associate professor.His research interests include network and multimedia, embedded system.

KSRG: an efficient optimal route query algorithm for multi-keyword coverage

JIN Pengfei, NIU Baoning, ZHANG Xingzhong*

(CollegeofComputerScienceandTechnology,TaiyuanUniversityofTechnology,TaiyuanShanxi030024,China)

To alleviate the issues of high complexity and poor scalability in the processing of keyword-aware optimal route query algorithms for large scale graph or multiple query keywords, an effective algorithm was proposed based on the scheme of keyword sequence route generating.The algorithm satisfied the coverage of query keywords first, and took a path expansion inspired by the keyword coverage property rather than aimless adjacent edge expansion to efficiently construct candidate paths.With the aid of a scaling method and ineffective route pruning, the search space was reduced into a polynomial order from an original factorial order, which further reduced the complexity and enhanced the scalability.Experiments conducted over four gragh datasets verified the accuracy and improvement in efficiency and scalability of the proposed algorithm.

keyword-aware optimal route query; complexity; scalability

2016- 08- 12;

2016- 09- 11。

國家自然科學基金資助項目(61572345)；國家科技支撐計劃項目(2015BAH37F01)。

金鵬飛(1992—)，男，浙江杭州人，碩士研究生，主要研究方向：空間數據查詢； 牛保寧(1964—)，男，山西太原人，教授，博士，CCF高級會員，主要研究方向：大數據、數據庫系統的自主計算與性能管理； 張興忠(1964—)，男，山西太原人，副教授，碩士，主要研究方向：網絡與多媒體、嵌入式系統。

1001- 9081(2017)02- 0352- 08

10.11772/j.issn.1001- 9081.2017.02.0352

TP

A