高效的多關(guān)鍵詞匹配最優(yōu)路徑查詢(xún)算法KSRG

金鵬飛，牛保寧，張興忠

(太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

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

高效的多關(guān)鍵詞匹配最優(yōu)路徑查詢(xún)算法KSRG

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

(太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

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

為改進(jìn)基于關(guān)鍵詞的最優(yōu)路徑查詢(xún)算法，在大規(guī)模圖以及多查詢(xún)關(guān)鍵詞下復(fù)雜度過(guò)高與可擴(kuò)展性不足的缺陷，依據(jù)查詢(xún)關(guān)鍵詞序列構(gòu)建候選路徑的策略提出一種高效查詢(xún)算法。該算法在路徑構(gòu)建過(guò)程中優(yōu)先滿足查詢(xún)關(guān)鍵詞的全包含條件，以關(guān)鍵詞引導(dǎo)下的路徑拓展替代盲目的鄰邊拓展，從而高效地構(gòu)建候選路徑；通過(guò)變量縮放與無(wú)效路徑裁剪，將問(wèn)題求解復(fù)雜度由階乘級(jí)轉(zhuǎn)化為多項(xiàng)式級(jí)，進(jìn)一步降低算法復(fù)雜度，提升可擴(kuò)展性。通過(guò)四組圖數(shù)據(jù)集下的實(shí)驗(yàn)，驗(yàn)證了算法在查詢(xún)效率與可擴(kuò)展性上的提升。

基于關(guān)鍵詞的最優(yōu)路徑查詢(xún)；復(fù)雜度；可擴(kuò)展性

0 引言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)與地理定位技術(shù)的發(fā)展，基于位置的服務(wù)當(dāng)下被廣泛應(yīng)用于交通、物流、旅游等多個(gè)領(lǐng)域。在眾多基于位置的服務(wù)中，地圖服務(wù)是一項(xiàng)極為常見(jiàn)的服務(wù)。根據(jù)位置信息為用戶(hù)在路網(wǎng)空間中查詢(xún)一條合適的路徑是地圖服務(wù)的一項(xiàng)重要功能[1]?？紤]到在Web資源與地圖服務(wù)結(jié)合的背景下，路徑查詢(xún)功能應(yīng)不再局限于在給定起點(diǎn)與終點(diǎn)的情況下單純返回兩點(diǎn)間最短路徑。為滿足用戶(hù)個(gè)性化的行程需求，針對(duì)特殊路徑，提出高效的查詢(xún)方法尤為重要。

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

該類(lèi)路徑查詢(xún)問(wèn)題被定義為基于關(guān)鍵詞的最優(yōu)路徑查詢(xún)(Keyword-aware Optimal Route Search， KORS)[2-3]。KORS是空間關(guān)鍵詞查詢(xún)中的一類(lèi)特殊查詢(xún)[4]，能夠?yàn)榈貓D服務(wù)在旅游行程中的路線規(guī)劃提供有效支持。與傳統(tǒng)的單源最短路徑(Single Source Shortest Path)查詢(xún)不同，KORS綜合考慮路徑關(guān)鍵詞覆蓋條件、路徑行程代價(jià)約束以及路徑流行度三類(lèi)因素間的組合優(yōu)化性，該類(lèi)問(wèn)題為NP-hard問(wèn)題[2]，實(shí)際路徑的搜索空間復(fù)雜度為O(dn)(d為圖中頂點(diǎn)最大出度)。

目前針對(duì)KORS算法主要基于鄰邊拓展的路徑構(gòu)建策略，該策略自起點(diǎn)出發(fā)通過(guò)不斷拓展當(dāng)前路徑終點(diǎn)的所有鄰邊以產(chǎn)生新的子路徑，直到路徑到達(dá)查詢(xún)終點(diǎn)。該過(guò)程實(shí)際枚舉了起點(diǎn)與終點(diǎn)間所有可行路徑，由于在KORS的問(wèn)題求解中，關(guān)鍵是通過(guò)路徑拓展構(gòu)建滿足查詢(xún)約束的可行路徑，因此當(dāng)查詢(xún)關(guān)鍵詞個(gè)數(shù)較多、起點(diǎn)終點(diǎn)間最優(yōu)路徑的頂點(diǎn)個(gè)數(shù)較多或者部分查詢(xún)關(guān)鍵詞分布稀疏時(shí)，鄰邊拓展的路徑構(gòu)建策略將枚舉大量的中間路徑，造成算法在空間、時(shí)間上開(kāi)銷(xiāo)驟增，可擴(kuò)展性變差。

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

1)針對(duì)KORS提出基于關(guān)鍵詞序列路徑構(gòu)建算法——KSRG算法，在路徑拓展過(guò)程中優(yōu)先滿足查詢(xún)關(guān)鍵詞的全包含條件，對(duì)查詢(xún)結(jié)果進(jìn)行高效的近似求解；

2)運(yùn)用四組圖數(shù)據(jù)集，對(duì)各類(lèi)算法進(jìn)行充分實(shí)驗(yàn)測(cè)試，并對(duì)查詢(xún)效率進(jìn)行對(duì)比，驗(yàn)證本文算法的有效性以及相對(duì)現(xiàn)有算法在查詢(xún)性能上的提升效果。

1 相關(guān)工作

1.1 空間關(guān)鍵詞查詢(xún)

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

1.2 最優(yōu)路徑查詢(xún)

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

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

1.3 KORS

為使規(guī)劃的路線能夠滿足用戶(hù)個(gè)性化行程需求，同時(shí)在代價(jià)預(yù)算上保持合理性，基于關(guān)鍵詞下的最優(yōu)路徑查詢(xún)(KORS)是一種合適的查詢(xún)類(lèi)型。該查詢(xún)最早在文獻(xiàn)[2]中被提出，與歐氏空間下的路徑問(wèn)題[10-12]不同，KORS在路網(wǎng)空間下查詢(xún)返回一條覆蓋所有用戶(hù)指定關(guān)鍵詞，同時(shí)滿足行程預(yù)算(如費(fèi)用、時(shí)間)且流行度最大的路徑。該類(lèi)路徑問(wèn)題為權(quán)值受限最短路徑(Weight Constrained Shortest Path，WCSP)問(wèn)題的一個(gè)特例，為NP難題[2]?；卩忂呁卣沟穆窂綐?gòu)建策略，OSScalling和BucketBound算法[2-3]實(shí)現(xiàn)了多項(xiàng)式復(fù)雜度下的問(wèn)題近似求解。然而由于路徑拓展策略，算法在大規(guī)模的無(wú)向圖以及多關(guān)鍵詞條件下進(jìn)行時(shí)，存在復(fù)雜度過(guò)高、空間開(kāi)銷(xiāo)極大、伸縮性不理想的缺陷。

2 問(wèn)題定義

2.1 問(wèn)題抽象

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

圖1 圖的結(jié)構(gòu)

表1 頂點(diǎn)關(guān)鍵詞信息

Tab.1Informationofvertexkeyword

頂點(diǎn)關(guān)鍵詞集頂點(diǎn)關(guān)鍵詞集v0t4t6t7v4t4t6v1t3t5v5t2t8t10v2t2t9t10v6t1v3t1t11t12v7t3t9

邊集E中的每條邊表示連接兩處興趣點(diǎn)的直通行程e。e帶有兩類(lèi)權(quán)值：1)代價(jià)權(quán)值(圖中括號(hào)外的數(shù)值)，表示通過(guò)該行程所需的行程代價(jià)(根據(jù)不同場(chǎng)景可為路段的時(shí)耗或距離)；2)流行度權(quán)值(圖中括號(hào)內(nèi)的數(shù)值)，表示該行程的流行度。若vi到vj存在直達(dá)路段(vi,vj)∈E,則b(vi,vj)為邊的代價(jià)權(quán)值，p(vi,vj)為邊的價(jià)值權(quán)值。

在KORS應(yīng)用場(chǎng)景中，最優(yōu)路徑查詢(xún)Q=(vs,vt,ψ,Δ)包含四類(lèi)查詢(xún)參數(shù)，其中：vs為用戶(hù)指定的行程起點(diǎn)(可為圖1任意某個(gè)興趣點(diǎn))；vt代表用戶(hù)指定的行程終點(diǎn)；ψ表示一組用戶(hù)指定的關(guān)鍵詞集合；Δ表示路徑代價(jià)上限值。

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

2.2 求解轉(zhuǎn)化

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

(1)

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

(2)

證畢。

根據(jù)定理1，KORS所求最優(yōu)路徑ropt即為滿足查詢(xún)約束條件，且擁有最小目標(biāo)值的路徑，形式化描述為：

3 KSRG算法

3.1 準(zhǔn)備工作

為在算法執(zhí)行中及時(shí)過(guò)濾無(wú)效的中間結(jié)果，提高問(wèn)題求解效率，在算法執(zhí)行前，需進(jìn)行如下準(zhǔn)備工作。

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

工作2 構(gòu)建倒排索引。抽取圖G中各興趣點(diǎn)的所有關(guān)鍵詞構(gòu)成一非重關(guān)鍵詞集合。該集合中每個(gè)關(guān)鍵詞對(duì)應(yīng)一個(gè)倒排表，記錄包含該關(guān)鍵詞的興趣點(diǎn)的集合。通過(guò)倒排索引的構(gòu)建，含有查詢(xún)關(guān)鍵詞的興趣點(diǎn)可被優(yōu)先篩選。

3.2 算法描述

KSRG算法首先采用關(guān)鍵詞序列路徑構(gòu)建來(lái)提高可行路徑構(gòu)建效率，此基礎(chǔ)上通過(guò)完全多項(xiàng)式時(shí)間近似策略進(jìn)一步實(shí)現(xiàn)高效、可擴(kuò)展性更優(yōu)的KORS。以下首先對(duì)這兩部分進(jìn)行說(shuō)明。

3.2.1KSRG預(yù)備知識(shí)

KSRG核心在于路徑拓展過(guò)程中優(yōu)先滿足查詢(xún)關(guān)鍵詞的全包含條件，進(jìn)行關(guān)鍵詞引導(dǎo)下的路徑拓展。在闡述思路前，有如下定義陳述。

定義1 關(guān)鍵詞頂點(diǎn)。給定查詢(xún)Q=(vs,vt,ψ,Δ),關(guān)鍵詞ti∈ψ。若vm.ψ包含ti,且BS(σs,m)+BS(σm,t)<Δ,則vm為關(guān)鍵詞ti對(duì)應(yīng)的關(guān)鍵詞頂點(diǎn)，ti對(duì)應(yīng)的所有關(guān)鍵詞頂點(diǎn)構(gòu)成的集合符號(hào)表示為Vti。

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

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

定理2OS(KSRopt)<|ψ|OS(ropt),其中|ψ|為查詢(xún)關(guān)鍵詞個(gè)數(shù)。

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

證畢。

根據(jù)定理2，采用KSRG對(duì)KORS的最優(yōu)路徑ropt進(jìn)行近似求解，基本思想為：根據(jù)查詢(xún)關(guān)鍵詞集，枚舉該集合下各個(gè)關(guān)鍵詞覆蓋序列對(duì)應(yīng)的可行關(guān)鍵詞頂點(diǎn)序列，計(jì)算其對(duì)應(yīng)的關(guān)鍵詞序列路徑的目標(biāo)值。在所有滿足查詢(xún)約束的可行關(guān)鍵詞路徑中，擁有最小目標(biāo)值的路徑即為最優(yōu)路徑ropt。

3.2.2 完全多項(xiàng)式時(shí)間近似策略

在3.2.1節(jié)中，枚舉所有關(guān)鍵詞頂點(diǎn)序列依然是一項(xiàng)復(fù)雜度較大的工作。給定一個(gè)查詢(xún)，查詢(xún)關(guān)鍵詞為Q.ψ,該工作的復(fù)雜度為O(nk×k!)(其中k=|Q.ψ|,n=max{|Vtm||tm∈Q.ψ})。

為避免此類(lèi)復(fù)雜度下的問(wèn)題求解，采用完全多項(xiàng)式時(shí)間近似策略(FullyPolynomial-TimeApproximationScheme，F(xiàn)PTAS)[18-19]，通過(guò)相關(guān)變量轉(zhuǎn)化，可將問(wèn)題求解的規(guī)模轉(zhuǎn)變?yōu)槎囗?xiàng)式級(jí)，具體步驟如下所述。

首先定義比例因子

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

在KSRG構(gòu)建策略中，路徑由起點(diǎn)vs出發(fā)，通過(guò)關(guān)鍵詞路徑拓展至所有之前未被包含的關(guān)鍵詞對(duì)應(yīng)的關(guān)鍵詞頂點(diǎn)，產(chǎn)生更長(zhǎng)關(guān)鍵詞序列對(duì)應(yīng)的關(guān)鍵詞序列路徑；所有子路徑繼續(xù)由當(dāng)前拓展終點(diǎn)重復(fù)上述拓展步驟直到路徑關(guān)鍵詞序列包含所有查詢(xún)關(guān)鍵詞。考慮到在路徑拓展過(guò)程需記錄下所有枚舉的局部路徑，因此需以適當(dāng)方式表示這些中間結(jié)果。

針對(duì)標(biāo)簽操作產(chǎn)生的大量中間結(jié)果(路徑標(biāo)簽)根據(jù)一定的優(yōu)先級(jí)，可決定哪條路徑標(biāo)簽優(yōu)先進(jìn)行下一步拓展，使路徑拓展盡可能朝最優(yōu)解所在方向推進(jìn)，具體規(guī)則如下定義。

定義8 標(biāo)簽優(yōu)先級(jí)。綜合路徑標(biāo)簽中的λ、OS′和BS三部分判定標(biāo)簽優(yōu)先級(jí)：

1)當(dāng)兩條路徑對(duì)應(yīng)的路徑標(biāo)簽包含的查詢(xún)關(guān)鍵詞個(gè)數(shù)不同時(shí)，包含查詢(xún)關(guān)鍵詞個(gè)數(shù)越多的路徑，其優(yōu)先級(jí)越高；

2)當(dāng)兩條路徑對(duì)應(yīng)的路徑標(biāo)簽中包含的查詢(xún)關(guān)鍵詞個(gè)數(shù)相同時(shí)，路徑目標(biāo)值越小，路徑優(yōu)先級(jí)越高；

3)當(dāng)兩條路徑對(duì)應(yīng)的路徑標(biāo)簽包含的查詢(xún)關(guān)鍵詞個(gè)數(shù)、路徑目標(biāo)值都相同時(shí)，路徑代價(jià)值越小路徑優(yōu)先級(jí)越高。

根據(jù)定理2，KORS求解的復(fù)雜度與Δ呈多項(xiàng)式相關(guān)性，與k呈指數(shù)相關(guān)性(k的取值通常不大)。

3.2.3 算法步驟

綜合3.2.1節(jié)與3.2.2節(jié)中各項(xiàng)定義和定理，提出KSRG算法。算法的基本思想為枚舉各關(guān)鍵詞序列下的有效路徑標(biāo)簽：首先篩選各個(gè)查詢(xún)關(guān)鍵詞對(duì)應(yīng)的所有關(guān)鍵詞頂點(diǎn)，之后路徑由起點(diǎn)vs出發(fā)按關(guān)鍵詞序列進(jìn)行關(guān)鍵詞路徑拓展，產(chǎn)生包含更多查詢(xún)關(guān)鍵詞的關(guān)鍵詞序列路徑，在此過(guò)程中每次選擇優(yōu)先級(jí)最高的中間路徑進(jìn)行拓展，并及時(shí)檢查拓展所得路徑裁剪無(wú)效路徑標(biāo)簽。重復(fù)此過(guò)程直到產(chǎn)生所有終點(diǎn)vt對(duì)應(yīng)的包含全部查詢(xún)關(guān)鍵詞的路徑標(biāo)簽，篩選滿足查詢(xún)約束且有最小修正目標(biāo)值的路徑標(biāo)簽，即為最優(yōu)路徑ropt。具體描述如下：

算法1KSRG算法。

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

輸出 最優(yōu)路徑標(biāo)簽LL。

1)

初始化隊(duì)列Q為空隊(duì)列，LL為Null，上界值U為無(wú)窮大；

2)

獲取Q.λ中每個(gè)關(guān)鍵詞ti對(duì)應(yīng)的Vti;

3)

4)

WhileQ中元素不為空do

5)

6)

7)

Foreachvj∈Vtido

8)

9)

10)

//舍棄該路徑,即停止后續(xù)拓展

11)

Else

12)

13)

14)

//無(wú)效路徑被舍棄，即停止后續(xù)拓展

15)

Else

16)

17)

18)

刪除Q中相關(guān)無(wú)效標(biāo)簽；

19)

Else

20)

21)

22)

23)

ReturnLL;

標(biāo)簽檢查函數(shù)checkLabel。

輸出 布爾值flag。

①

初始化布爾值flag=false，無(wú)效標(biāo)簽表UL；

②

Foreachl∈vj.listdo

③

④

flag=true;

⑤

returnflag;

⑥

⑦

將l加入U(xiǎn)L;

⑧

list中刪除l;

⑨

Returnflag;

3.2.4 算法分析

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

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

(3)

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

(4)

對(duì)式(4)最右部分進(jìn)一步推導(dǎo)可得：

4 實(shí)驗(yàn)與評(píng)估

對(duì)提出的KSRG算法進(jìn)行實(shí)驗(yàn)測(cè)試，并與OSScaling算法、BucketBound算法進(jìn)行性能對(duì)比。所有算法均由Java語(yǔ)言編程實(shí)現(xiàn)，實(shí)驗(yàn)在PC上執(zhí)行，處理器型號(hào)為AMDA8- 7100 1.8GHz，主存為4.0GB，操作系統(tǒng)為Windows8，JDK版本為1.7，Java虛擬機(jī)堆空間設(shè)定為512MB。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用文獻(xiàn)[20]提供的路網(wǎng)數(shù)據(jù)集，本文截取路網(wǎng)COL、NW、DE、ME中的部分點(diǎn)集與邊集，通過(guò)程序去除其中的孤立點(diǎn)與冗余邊構(gòu)建連通子圖G1、G2、G3、G4；結(jié)合文獻(xiàn)[6]中的關(guān)鍵詞數(shù)據(jù)集，為圖中的頂點(diǎn)分配相應(yīng)關(guān)鍵詞構(gòu)成本文數(shù)據(jù)集，具體如表2所示。

表2 實(shí)驗(yàn)圖數(shù)據(jù)集

本文隨機(jī)使用范圍在0到1間的小數(shù)對(duì)圖中所有邊的流行度權(quán)值進(jìn)行賦值，流行度權(quán)值代表了某條邊對(duì)應(yīng)的路段熱度，流行度權(quán)值越大表示該路段被游客訪問(wèn)的概率越高。

4.2 算法性能對(duì)比

4.2.1 不同查詢(xún)關(guān)鍵詞個(gè)數(shù)下運(yùn)行結(jié)果

為比較算法在不同查詢(xún)關(guān)鍵詞個(gè)數(shù)下的性能，在圖G2中，隨機(jī)選定兩個(gè)頂點(diǎn)作為路徑起點(diǎn)與終點(diǎn)，設(shè)定查詢(xún)的代價(jià)約束為50km，測(cè)試算法分別在關(guān)鍵詞數(shù)目為2、4、6、8、10共五種情況下的查詢(xún)性能，每種查詢(xún)各運(yùn)行5次，對(duì)運(yùn)行時(shí)間取平均值，結(jié)果具體如圖2所示。

圖2 不同關(guān)鍵詞個(gè)數(shù)下查詢(xún)響應(yīng)時(shí)間

根據(jù)圖2，KSRG算法的查詢(xún)響應(yīng)時(shí)間遠(yuǎn)小于OSScaling以及BucketBound算法。OSScaling算法的查詢(xún)響應(yīng)時(shí)間最長(zhǎng)，由于在查詢(xún)關(guān)鍵詞個(gè)數(shù)大于8時(shí)，運(yùn)行時(shí)間大于10s，因此不在圖中標(biāo)注。當(dāng)查詢(xún)關(guān)鍵詞個(gè)數(shù)大于6時(shí)，OSScaling、BucketBound算法的響應(yīng)時(shí)間顯著增加，這是因?yàn)閮烧叨疾捎绵忂呁卣沟穆窂綐?gòu)建原則，將產(chǎn)生大量的路徑標(biāo)簽；KSRG算法通過(guò)關(guān)鍵詞路徑拓展構(gòu)建路徑，僅考慮查詢(xún)關(guān)鍵詞相關(guān)的頂點(diǎn)，將產(chǎn)生更少路徑標(biāo)簽，降低中間結(jié)果的處理代價(jià)因而響應(yīng)時(shí)延更小。三類(lèi)算法在查詢(xún)過(guò)程中產(chǎn)生的路徑標(biāo)簽的個(gè)數(shù)統(tǒng)計(jì)如圖3所示。根據(jù)圖3，OSScaling算法在查詢(xún)中產(chǎn)生的路徑標(biāo)簽數(shù)量約為KSRG算法的100倍，BucketBound算法產(chǎn)生的路徑標(biāo)簽數(shù)量約為KSRG算法的10倍。大量路徑標(biāo)簽的存儲(chǔ)，使得OSScaling和BucketBound算法在多關(guān)鍵詞查詢(xún)過(guò)程中的空間開(kāi)銷(xiāo)過(guò)大，又由于查詢(xún)過(guò)程中大量中間結(jié)果(路徑標(biāo)簽)的處理操作，進(jìn)而嚴(yán)重限制了查詢(xún)效率。

4.2.2 不同查詢(xún)代價(jià)約束下的運(yùn)行結(jié)果

為比較不同代價(jià)約束對(duì)算法查詢(xún)的影響，選定在圖G4中進(jìn)行查詢(xún)測(cè)試。在圖G4中同樣隨機(jī)選定兩個(gè)頂點(diǎn)作為路徑起點(diǎn)與終點(diǎn)，設(shè)定查詢(xún)關(guān)鍵詞個(gè)數(shù)為6，測(cè)試算法在代價(jià)約束為40、50、60、70、80km共5類(lèi)查詢(xún)的運(yùn)行情況，每類(lèi)查詢(xún)運(yùn)行5次，對(duì)結(jié)果取平均值，如圖4所示。根據(jù)圖4，三類(lèi)算法的查詢(xún)響應(yīng)時(shí)間隨代價(jià)約束值的變大，呈現(xiàn)先減小后逐漸趨于穩(wěn)定的趨勢(shì)。這是因?yàn)?，在一定范圍?nèi)，較大的查詢(xún)約束值能夠使算法更早地求得可行路徑標(biāo)簽，從而裁剪更多中間結(jié)果；當(dāng)查詢(xún)約束值繼續(xù)增大時(shí)，由于最優(yōu)解限定了目標(biāo)值的上界，問(wèn)題的解空間不再增大，故查詢(xún)時(shí)間基本不變。三類(lèi)算法在不同代價(jià)值約束下在查詢(xún)過(guò)程中產(chǎn)生的路徑標(biāo)簽數(shù)統(tǒng)計(jì)，如圖5所示。

圖3 不同查詢(xún)關(guān)鍵詞個(gè)數(shù)下路徑標(biāo)簽產(chǎn)生數(shù)

圖4 不同查詢(xún)代價(jià)約束下查詢(xún)運(yùn)行時(shí)間

圖5 不同查詢(xún)代價(jià)約束下路徑標(biāo)簽產(chǎn)生個(gè)數(shù)

綜合圖4和圖5，在不同查詢(xún)代價(jià)約束下，KSRG算法相比OSScaling算法及BucketBound算法，有更少的查詢(xún)響應(yīng)時(shí)間以及更小的空間開(kāi)銷(xiāo)代價(jià)。

4.2.3 不同數(shù)據(jù)集下的運(yùn)行結(jié)果

為比較算法在不同數(shù)據(jù)集對(duì)應(yīng)的圖下的運(yùn)行結(jié)果，在圖G1、G2、G3、G4中隨機(jī)選定兩個(gè)頂點(diǎn)作為查詢(xún)的起點(diǎn)與終點(diǎn)，統(tǒng)一設(shè)定查詢(xún)關(guān)鍵詞個(gè)數(shù)為6，代價(jià)約束為50km，不同圖下的查詢(xún)各運(yùn)行5次，對(duì)結(jié)果取平均，如圖6所示。根據(jù)圖6，OSScaling、BucketBound算法的查詢(xún)響應(yīng)時(shí)間隨圖尺寸變大呈線性增大趨勢(shì)，因?yàn)殡S著圖的變大，兩種算法在鄰邊拓展過(guò)程中將遍歷更多的頂點(diǎn)與邊，產(chǎn)生更多的路徑標(biāo)簽，增加查詢(xún)處理代價(jià)。KSRG算法在不同尺寸圖中運(yùn)行時(shí)間呈現(xiàn)波動(dòng)趨勢(shì)，時(shí)間變化與圖尺寸大小沒(méi)有明顯關(guān)聯(lián)，因?yàn)镵SRG算法通過(guò)關(guān)鍵詞路徑拓展產(chǎn)生關(guān)鍵詞序列路徑，該過(guò)程中對(duì)關(guān)鍵詞頂點(diǎn)進(jìn)行拓展，避免了無(wú)關(guān)頂點(diǎn)的遍歷，故在代價(jià)約束確定后，查詢(xún)代價(jià)不受圖中頂點(diǎn)總數(shù)影響。

圖6 不同圖中的查詢(xún)響應(yīng)時(shí)間

4.3 相關(guān)因素評(píng)估

考慮KSRG的路徑拓展策略，影響查詢(xún)響應(yīng)性能的主要因素為查詢(xún)關(guān)鍵詞的頻度和起點(diǎn)終點(diǎn)相對(duì)位置。

4.3.1 不同頻度的查詢(xún)關(guān)鍵詞對(duì)查詢(xún)的影響

為比較關(guān)鍵詞的頻度對(duì)算法查詢(xún)響應(yīng)時(shí)間的影響，構(gòu)建Q1、Q2、Q3和Q4共四類(lèi)查詢(xún)，每類(lèi)查詢(xún)都設(shè)定相同查詢(xún)起點(diǎn)與終點(diǎn)，并統(tǒng)一查詢(xún)代價(jià)約束為30km，統(tǒng)一查詢(xún)關(guān)鍵詞個(gè)數(shù)為6。每類(lèi)查詢(xún)的關(guān)鍵詞頻度不同，具體如表3所示。

表3 查詢(xún)中的關(guān)鍵詞頻度

在圖G3中對(duì)上述四類(lèi)查詢(xún)進(jìn)行測(cè)試，每類(lèi)查詢(xún)各運(yùn)行5次，對(duì)查詢(xún)響應(yīng)時(shí)間取平均值，具體結(jié)果如表4所示。

表4 查詢(xún)關(guān)鍵詞頻度對(duì)查詢(xún)響應(yīng)時(shí)間的影響 ms

根據(jù)表3，KSRG算法對(duì)查詢(xún)關(guān)鍵詞的頻度敏感。這是因?yàn)殛P(guān)鍵詞頻度越大，在每種關(guān)鍵詞序列將枚舉更多可行的關(guān)鍵詞頂點(diǎn)序列，從而在查詢(xún)過(guò)程產(chǎn)生更多路徑標(biāo)簽。

4.3.2 查詢(xún)起點(diǎn)與終點(diǎn)相對(duì)位置對(duì)響應(yīng)時(shí)間的影響

為比較查詢(xún)中不同的起點(diǎn)與終點(diǎn)的相對(duì)位置對(duì)KSRG算法響應(yīng)時(shí)間的影響，特構(gòu)建四組查詢(xún)Q5、Q6、Q7、Q8。每組查詢(xún)?cè)O(shè)定代價(jià)約束為50km；統(tǒng)一查詢(xún)關(guān)鍵詞個(gè)數(shù)為6；選擇相距不同歐氏距離的起點(diǎn)與終點(diǎn)，具體如表5所示。

將上述四組查詢(xún)?cè)趫DG3中進(jìn)行測(cè)試，結(jié)果如表6所示。根據(jù)表5，起點(diǎn)與終點(diǎn)間的歐氏距離越大，算法響應(yīng)時(shí)間越長(zhǎng)，這是因?yàn)樵谳^大歐氏距離間隔下，兩點(diǎn)間將包含更多關(guān)鍵詞頂點(diǎn)，因此在查詢(xún)過(guò)程也將產(chǎn)生更多的關(guān)鍵詞序列路徑對(duì)應(yīng)的路徑標(biāo)簽。

表5 查詢(xún)點(diǎn)位置間歐氏距離

表6 查詢(xún)點(diǎn)間距離對(duì)查詢(xún)響應(yīng)時(shí)間的影響 ms

5 結(jié)語(yǔ)

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

)

[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] 宋曉宇,許鴻斐,孫煥良,等.基于簽到數(shù)據(jù)的短時(shí)間體驗(yàn)式路線搜索[J].計(jì)算機(jī)學(xué)報(bào),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] 鮑金玲,楊曉春,王斌,等.一種支持約束關(guān)系的高效的行程規(guī)劃算法[J].小型微型計(jì)算機(jī)系統(tǒng),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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572345)；國(guó)家科技支撐計(jì)劃項(xiàng)目(2015BAH37F01)。

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

1001- 9081(2017)02- 0352- 08

10.11772/j.issn.1001- 9081.2017.02.0352

TP

A