劉俊嶺 劉柏何 鄒鑫源 孫煥良

(沈陽建筑大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽 110168) (遼寧省城市建設(shè)大數(shù)據(jù)管理與分析重點(diǎn)實(shí)驗(yàn)室(沈陽建筑大學(xué)) 沈陽 110168)

廣泛的位置感知應(yīng)用產(chǎn)生了大量的空間文本數(shù)據(jù)，如用戶的簽到數(shù)據(jù)和評論、帶有地理標(biāo)記的帖子以及商業(yè)平臺(tái)的基于位置的廣告等，擴(kuò)展了路線規(guī)劃問題.結(jié)合空間文本數(shù)據(jù)，產(chǎn)生了符合用戶給定關(guān)鍵字相關(guān)約束的路線查詢問題[1-3].

現(xiàn)有的應(yīng)用空間文本查詢路線的研究，通常返回1條由空間興趣點(diǎn)(point of interests, POI)組成的路線，每個(gè)POI是單獨(dú)的空間對象[4-7].由于實(shí)際應(yīng)用中POI及相關(guān)的空間關(guān)鍵字是海量的，并且POI的分布通常嚴(yán)重偏斜，使得多條路線通過相同的聚集區(qū)域，導(dǎo)致查詢結(jié)果相似性較高，無法滿足用戶對于結(jié)果多樣性的需求.同時(shí)路線查詢需要遍歷每個(gè)POI及相關(guān)的空間關(guān)鍵字使得查詢算法的效率較低.

圖1(a)為空間關(guān)鍵字POI路線查詢示例圖，其中曲線代表軌跡、實(shí)心圓代表POI點(diǎn).假設(shè)查詢起點(diǎn)為p1，給定路線長度約束及空間關(guān)鍵字集合，以最大化關(guān)鍵字收益和為目標(biāo)可以得到2條路線，分別為A1(p1→p4→p5→p6)和A2(p1→p3→p5→p6).從示例中可以看出路線A1與A2存在多個(gè)重疊結(jié)點(diǎn)，導(dǎo)致路線間的相似性較大.當(dāng)存在大量的POI及相關(guān)的空間關(guān)鍵字時(shí)，增加了搜索空間，影響了查詢算法的效率.

本文提出了面向空間興趣區(qū)域的路線查詢(region of interests oriented route query, ROIR)問題.給定一個(gè)反映用戶轉(zhuǎn)移關(guān)系的圖G、帶有關(guān)鍵字的POI集合P及查詢QU(v0,C,r,L)，其中v0為查詢起點(diǎn)，C為關(guān)鍵字集合，r為一個(gè)興趣區(qū)域半徑，L為路線的長度限制.ROIR返回滿足長度L約束，關(guān)于關(guān)鍵字集C收益和最大的路線Ares，路線Ares的每個(gè)結(jié)點(diǎn)為一個(gè)興趣區(qū)域.如圖1(b)所示，在與圖1(a)相同的查詢條件下可以得到查詢結(jié)果Ares(D1→D2→D3→D4)，該結(jié)果由半徑為r的興趣區(qū)域序列組成，包含了圖1(a)中A1和A2這2條路線.

與現(xiàn)有的POI路線查詢相比，ROIR返回路線的結(jié)點(diǎn)為興趣區(qū)域，包含了多個(gè)鄰近的POI，降低了路線的相似性，增加了用戶的選擇空間，使得查詢結(jié)果有更好的適用性.同時(shí)ROIR結(jié)果包含多條POI路線，提高了查詢效率.ROIR適用于海量分布的POI及空間關(guān)鍵字場景下的關(guān)鍵字偏好路線查詢，同時(shí)ROIR也適用于結(jié)伴出行情況，允許用戶在興趣區(qū)域內(nèi)分別訪問各自偏好的地點(diǎn).

本文將空間路線查詢對象由POI擴(kuò)展為興趣區(qū)域，存在的主要挑戰(zhàn)包括：1)如何有效組織多種類型的海量POI及相關(guān)空間關(guān)鍵字是一個(gè)挑戰(zhàn).本查詢涉及用戶的空間轉(zhuǎn)移關(guān)系、空間對象及對象的文本描述等多種數(shù)據(jù)類型.2)如何設(shè)計(jì)支持ROIR的高效算法是另一個(gè)挑戰(zhàn).需要建立適用于所提出查詢的索引結(jié)構(gòu).ROIR是一個(gè)NP難問題，需要設(shè)計(jì)相應(yīng)的高效近似算法.

為了應(yīng)對以上2個(gè)挑戰(zhàn)，本文提出一種2層數(shù)據(jù)組織模型.其中上層為反映用戶轉(zhuǎn)移關(guān)系的圖結(jié)構(gòu)，結(jié)點(diǎn)概括抽象了POI的聚集區(qū)域；下層為細(xì)節(jié)的POI數(shù)據(jù)及相關(guān)空間關(guān)鍵字信息.針對提出的空間數(shù)據(jù)組織模型，提出了綜合空間對象、轉(zhuǎn)移關(guān)系以及空間關(guān)鍵字等信息的索引結(jié)構(gòu)，同時(shí)預(yù)計(jì)算了空間關(guān)鍵字的局部收益的統(tǒng)計(jì)值，并以簽名方式存儲(chǔ)在轉(zhuǎn)移結(jié)點(diǎn)上.利用所提出的索引結(jié)構(gòu)，設(shè)計(jì)了過濾—提煉2階段ROIR精確算法以及近似算法.

本文工作的主要貢獻(xiàn)有3個(gè)方面：

1) 定義了面向空間興趣區(qū)域的路線查詢問題，解決了現(xiàn)有關(guān)鍵字路線查詢中多樣性不足問題，提高了路線查詢的適用性.

2) 設(shè)計(jì)了結(jié)合上層轉(zhuǎn)移圖與下層POI對象及相關(guān)空間關(guān)鍵字的2層數(shù)據(jù)組織模型.針對2層模型提出一種新的索引結(jié)構(gòu)，并設(shè)計(jì)了面向空間興趣區(qū)域的路線查詢優(yōu)化算法.

3) 利用真實(shí)數(shù)據(jù)集進(jìn)行了詳細(xì)的實(shí)驗(yàn)分析，評估了所提出算法的有效性.

1 問題定義

給定一個(gè)空間D、興趣點(diǎn)集合P，任何一個(gè)點(diǎn)p∈P表示為p(p.id,p.loc,p.C)，其中p.id是p的唯一身份標(biāo)識(shí)，p.loc是點(diǎn)p的空間坐標(biāo)，p.C是點(diǎn)p含有的關(guān)鍵字及其流行度的集合.對于一個(gè)興趣點(diǎn)的某個(gè)關(guān)鍵字p.c∈p.C，收益分值p.Sc代表點(diǎn)p中關(guān)鍵字c的流行度，可用用戶的訪問次數(shù)表示.

轉(zhuǎn)移圖G(V,E)是用戶在空間上軌跡轉(zhuǎn)移的概括表示，反映了結(jié)點(diǎn)間用戶流行的轉(zhuǎn)移關(guān)系，其中V為結(jié)點(diǎn)的集合，E為邊集.任意結(jié)點(diǎn)v∈V代表興趣點(diǎn)聚集的中心點(diǎn)，定義為(v.id,v.loc)，其中v.id是v的唯一身份標(biāo)識(shí)，v.loc是結(jié)點(diǎn)v的空間坐標(biāo)；任意邊e∈E代表V中2個(gè)結(jié)點(diǎn)vi與vj間的轉(zhuǎn)移關(guān)系.轉(zhuǎn)移圖的生成方法將在2.1節(jié)中介紹.

(1)

(2)

查詢實(shí)例如圖2所示，假設(shè)查詢關(guān)鍵字集合為C={a,b,d,e,f}.長度約束L=17，區(qū)域半徑r=2，查詢起點(diǎn)為v1.

Fig. 2 The example of ROIR圖2 ROIR實(shí)例

對于傳統(tǒng)POI路線查詢，例中針對查詢關(guān)鍵字集合C的最優(yōu)結(jié)果為序列A2(p1→p4→p5→p6)，序列收益分?jǐn)?shù)為29.然而，對于ROIR最優(yōu)路線為A1(v1(D1)→v3(D2)→v5(D3)→v7(D4))，其收益為33，高于POI路線的收益.由定義1可知，ROIR屬于空間關(guān)鍵字偏好的路線查詢，將關(guān)鍵字的收益和作為優(yōu)化目標(biāo).

由實(shí)例可以看出，所提出的ROIR可以提高路線的收益值.由區(qū)域組成的路線，提高了原有單個(gè)POI結(jié)點(diǎn)的多樣性，起到對多個(gè)相似路線聚集的作用.另外，在轉(zhuǎn)移圖上按興趣區(qū)域查詢也可以提高查詢效率.

實(shí)現(xiàn)ROIR是一個(gè)具有挑戰(zhàn)性的工作.由實(shí)例可知，本查詢涉及POI點(diǎn)、圖結(jié)構(gòu)以及文本信息等多種類型的數(shù)據(jù)，并且實(shí)際應(yīng)用中數(shù)據(jù)具有海量性，需要對數(shù)據(jù)進(jìn)行有效的組織與設(shè)計(jì)相應(yīng)索引以支持查詢.同時(shí)所定義的查詢在轉(zhuǎn)移圖上進(jìn)行搜索是NP難問題.假設(shè)每個(gè)結(jié)點(diǎn)的出度為λ，即經(jīng)過結(jié)點(diǎn)后有λ條路可選擇，在長度約束L下可以經(jīng)過的結(jié)點(diǎn)個(gè)數(shù)為n，則代價(jià)為λn，若結(jié)點(diǎn)上含有關(guān)鍵字個(gè)數(shù)為m，則最終代價(jià)為(m·λ)n.因此，ROIR問題是NP難問題.表1簡要概述了本文所使用的符號.

Table 1 Symbol Summary表1 符號總結(jié)

2 查詢處理算法

本節(jié)介紹數(shù)據(jù)組織與索引結(jié)構(gòu)，以及精確查詢算法和近似查詢算法.

2.1 數(shù)據(jù)組織與索引結(jié)構(gòu)

為了有效地處理多類型的海量數(shù)據(jù)，考慮將POI及相關(guān)空間關(guān)鍵字密集且流行度高的區(qū)域聚集，并從具體的細(xì)節(jié)數(shù)據(jù)中分離出來，以提高查詢路線的多樣性和算法查詢效率.因此，提出一種2層數(shù)據(jù)組織結(jié)構(gòu)，如圖2所示.圖2中，上層為轉(zhuǎn)移圖，由軌跡的交叉區(qū)域提取或是密集POI點(diǎn)聚集生成；下層為具體的POI及其關(guān)鍵字信息，路線的關(guān)鍵字收益得分由下層數(shù)據(jù)提供.

本文首先利用用戶軌跡數(shù)據(jù)，采用文獻(xiàn)[4]的方法提取了轉(zhuǎn)移圖.同時(shí)，添加一些流行度高且遠(yuǎn)離現(xiàn)有結(jié)點(diǎn)的POI聚集點(diǎn)，采用了基于網(wǎng)格密度聚類的方法產(chǎn)生增加的聚集點(diǎn)[8].首先將空間網(wǎng)格化，統(tǒng)計(jì)單元格內(nèi)點(diǎn)的數(shù)量并對稠密的單元格進(jìn)行聚類；然后計(jì)算轉(zhuǎn)移結(jié)點(diǎn)所在單元格與聚類后的單元格的轉(zhuǎn)移數(shù)量，數(shù)量超過一定閾值即可生成一條轉(zhuǎn)移邊；最后提取聚集網(wǎng)格的中心點(diǎn)加入轉(zhuǎn)移圖.

針對提出的2層數(shù)據(jù)組織模型，本文借鑒文獻(xiàn)[9]對交通網(wǎng)絡(luò)的索引結(jié)構(gòu)，并引入關(guān)鍵字簽名，提出了結(jié)合空間文本索引與轉(zhuǎn)移圖結(jié)構(gòu)的索引結(jié)構(gòu)，命名為BIR(balance information tree).如圖3所示，索引結(jié)構(gòu)由3部分組成，第1部分為擴(kuò)展的B+樹結(jié)構(gòu)，存儲(chǔ)了轉(zhuǎn)移圖上的結(jié)點(diǎn)、鄰接表以及關(guān)鍵字的概要簽名信息，對應(yīng)于圖2中上層數(shù)據(jù)結(jié)構(gòu)；第2部分為IR樹結(jié)構(gòu)，用于存儲(chǔ)POI點(diǎn)空間位置及其文本信息，對應(yīng)于圖2中下層數(shù)據(jù)結(jié)構(gòu)；第3部分為圖結(jié)點(diǎn)與空間最小邊界矩形MBR的關(guān)系表，用于連接IR樹與B+樹這2個(gè)索引，實(shí)現(xiàn)圖結(jié)點(diǎn)到其所在MBR的聯(lián)系.

Fig. 3 BIR index structure圖3 BIR索引結(jié)構(gòu)

IR樹結(jié)構(gòu)中使用簽名存儲(chǔ)2層結(jié)構(gòu)中底層的POI點(diǎn)信息，底層結(jié)點(diǎn)存儲(chǔ)POI點(diǎn)包含的關(guān)鍵字及分值，非底層結(jié)點(diǎn){E1,E2,…,En}稱為中間結(jié)點(diǎn)，代表IR樹中由結(jié)點(diǎn)組成的矩形區(qū)域MBR.中間結(jié)點(diǎn)的簽名由多個(gè)葉子結(jié)點(diǎn)的簽名計(jì)算得到，為該區(qū)域內(nèi)葉子結(jié)點(diǎn)的關(guān)鍵字與其最大分值.

擴(kuò)展的B+樹結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)存儲(chǔ)2部分內(nèi)容，分別為結(jié)點(diǎn)鄰接表和關(guān)鍵字范圍簽名(命名為r簽名).鄰接表存儲(chǔ)一個(gè)結(jié)點(diǎn)所有鄰接結(jié)點(diǎn)的信息，圖3中v1結(jié)點(diǎn)的鄰接表由鄰接結(jié)點(diǎn)v2,v3,v4組成，v1鄰接表的第1行v2,5,ptr2表示v1鄰接到v2，5為2點(diǎn)間的距離，ptr2指向v2在B+樹中葉子結(jié)點(diǎn)的位置.

關(guān)鍵字范圍簽名存儲(chǔ)了以結(jié)點(diǎn)為中心多個(gè)同心圓周范圍內(nèi)的關(guān)鍵字收益的最大值信息.圖3中簽名的每一列對應(yīng)不同的半徑r.例如，以v2結(jié)點(diǎn)為中心的r簽名中，當(dāng)r1=400 m時(shí)，(p8,p9,p10)包含在范圍400 m內(nèi)，取這些POI點(diǎn)的關(guān)鍵字的最大收益值，可以得到{0,2,1,2,0,0}作為簽名表的1列.

(3)

文獻(xiàn)[10]給出適宜步行距離的結(jié)論，即在787 m的步行距離以內(nèi)，用戶選擇步行出行的可能性超過10%.本文選取1 000 m作為r的最大值，在該范圍內(nèi)用戶選擇步行分散訪問所偏好的空間對象.通過預(yù)計(jì)算的r簽名可以初步估算路線收益值，從而過濾大量的結(jié)點(diǎn)，減少候選路線的數(shù)量.

轉(zhuǎn)移圖結(jié)點(diǎn)與空間MBR關(guān)系表存儲(chǔ)轉(zhuǎn)移結(jié)點(diǎn)與其所在空間的MBR位置關(guān)系，分別記錄了指向B+樹中轉(zhuǎn)移結(jié)點(diǎn)的指針，以及結(jié)點(diǎn)位置在IR樹中所屬M(fèi)BR的指針.

由于提出的索引結(jié)構(gòu)為離線構(gòu)建并存儲(chǔ)在磁盤中，索引建立的時(shí)間不會(huì)影響查詢效率，因此只需分析索引的空間代價(jià).空間代價(jià)由3部分組成：第1部分為轉(zhuǎn)移圖結(jié)點(diǎn)的B+樹存儲(chǔ)，代價(jià)為|C|×nr×h，其中|C|為關(guān)鍵字類別數(shù)，nr為r簽名的列數(shù)，h為B+樹高度；第2部分為POI點(diǎn)的IR樹存儲(chǔ)，代價(jià)為|C|×(|P|-1)/(mR-1)，其中mR為IR樹最大扇出，|P|為POI集合的大??；第3部分為圖結(jié)點(diǎn)與空間最小邊界矩形MBR的關(guān)系表，代價(jià)為NG×(|P|-1)/(mR-1)，其中NG為轉(zhuǎn)移圖結(jié)點(diǎn)數(shù).由于轉(zhuǎn)移圖結(jié)點(diǎn)數(shù)NG遠(yuǎn)小于POI數(shù)|P|，則總的空間代價(jià)為O(|P|).

2.2 ROIR精確算法

基于所提出的索引結(jié)構(gòu)，本文設(shè)計(jì)了一種過濾—提煉2階段精確查詢算法，如算法1所示.算法1在過濾階段利用上下界剪枝，過濾掉不可行解，減少對IR樹的訪問；在提煉階段采用best-first方式，優(yōu)先選擇高收益的解，從而提高算法查詢效率.

算法1.ROIR路線查詢精確算法Region.

輸入:QU(v0,C,r,L)，由G和P建立的索引BIR;

輸出:收益最高的一條路線Ares.

①A={v0},A.last=v0,LIST={};

② for (A.last未訪問的鄰接點(diǎn)v)

③ if (dist(A.last,v)+A.L>L)

④ if (Mupper(A)>Mmaxlower(LIST))

⑤LIST=LIST∪A，更新

Mmaxlower(LIST);

⑥ 刪除上界分值小于Mlower(A)的路線；

⑦ end if

⑧ else

⑨A=A∪{v},A.last=v;

⑩DFS(Q,BIR,A);

算法1的過濾過程在擴(kuò)展的B+樹上執(zhí)行如行①～所示.算法1遞歸調(diào)用算法2執(zhí)行深度優(yōu)先搜索，不斷擴(kuò)展路徑長度，直到其滿足長度約束，返回一條候選路線并計(jì)算其上下界收益值.如果生成的候選路線A的上界得分高于候選列表中路線的下界得分，需要用路線A更新候選列表，實(shí)現(xiàn)對候選路線的剪枝(行③～⑦)，更新方法的正確性由定理1及推論1，2保證.提煉階段在IR樹上執(zhí)行，如行～所示.初始計(jì)算LIST中的一條候選路線的精確收益值(行)，然后用此路線精確收益對候選進(jìn)行剪枝.若候選路線的精確得分高于當(dāng)前最優(yōu)路線的得分，則用此路線更新最優(yōu)路線(行～).

算法2.DFS(Q,BIR,A).

① for (A.last未訪問的鄰接點(diǎn)v′)

② if (A.L

③A=A∪{v′},A.last=v′;

④DFS(Q,BIR,A);

⑤ else returnA;

⑥ end if

⑦ end for

定理1.已知2條路線A和A′，當(dāng)A的下界收益值Mlower(A)大于A′上界收益值Mupper(A′)時(shí)，即Mupper(A′)≤Mlower(A)，則可用A剪枝A′.

定理1說明了給定2條路線A和A′，當(dāng)Mupper(A′)≤Mlower(A)時(shí)路線A的實(shí)際收益值一定大于路線A′的實(shí)際收益值，則可用A剪枝A′.

算法1定義了一個(gè)存儲(chǔ)候選路線集LIST，LIST中各候選路線應(yīng)滿足性質(zhì)1.

性質(zhì)1.LIST中的任意候選路線的上界收益都大于所有其它候選路線的下界，其下界都小于所有其它候選路線的上界.

性質(zhì)1說明當(dāng)LIST用于返回一個(gè)具有最高收益的結(jié)果時(shí)，LIST中候選路線收益范圍是交疊的.為了便于算法剪枝，將LIST中的路線按下界收益值降序排列,將最大下界與最小下界收益值分別表示為Mmaxlower(LIST)與Mminlower(LIST).由性質(zhì)1可以得出推論1與推論2，用于對候選路線的剪枝.

推論1.已知候選路線集LIST，對于任意一條新的候選路線A，若Mupper(A)≤Mmaxlower(LIST)，則可以將A放棄.

Fig. 4 The figure of routes in candidate set圖4 候選集路線示意圖

圖4(a)為推論1的情況示例，A1～A4是LIST中的候選路線，縱軸為收益值，分別含有上下界收益，Mlower(A1)即為Mmaxlower(LIST).A是新的候選路線，Mupper(A)

推論2.已知候選路線集LIST，對于任意一條新的候選路線A，滿足Mupper(A)>Mmaxlower(LIST)，需要將A插入到LIST中.路線集LIST中任意路線A′，如果Mupper(A′)≤Mlower(A)，則可將路線A′剪枝.

如圖4(b)所示，路線A的上界收益值大于A1的下界收益值，可插入到LIST中.然而，在候選路線集LIST中存在路線A2和A4，Mupper(A2)≤Mlower(A)及Mupper(A4)≤Mlower(A)時(shí)，A2和A4被剪枝.利用推論2實(shí)現(xiàn)對LIST剪枝見算法1行⑥.

在提煉階段，優(yōu)先選擇可能有較高精確收益值的候選路線，獲得的精確值有利于對剩余候選路線的剪枝，從而減少IR樹的訪問次數(shù).因此，本文分別采用最大上界收益值優(yōu)先、最大下界收益值優(yōu)先、最大平均收益值優(yōu)先3種策略選取路線.實(shí)現(xiàn)時(shí)只需更改算法1的行即可.算法1中輸入C為空間關(guān)鍵字集合，當(dāng)實(shí)際應(yīng)用中需要考慮關(guān)鍵字訪問順序時(shí)，可以在算法的提煉階段中增加訪問順序作為過濾條件來實(shí)現(xiàn).

通過分析可知，本文算法在過濾階段的復(fù)雜度級別與POI點(diǎn)序列路線查詢算法同為(mλ)n，在提煉階段，假設(shè)剪枝后的路線為x條，每條路線的結(jié)點(diǎn)數(shù)依舊為n，結(jié)點(diǎn)范圍內(nèi)POI點(diǎn)的個(gè)數(shù)為n′，代價(jià)為n′xn，因此算法總代價(jià)為(mλ)n+n′xn，可表示為O((mλ)n).然而，由于算法過濾階段是在轉(zhuǎn)移圖上進(jìn)行，圖中結(jié)點(diǎn)概要了底層POI點(diǎn)相關(guān)信息，因此顯著降低了n的大小，從而降低整個(gè)算法代價(jià).

2.3 ROIR近似算法

由于ROIR是一個(gè)NP難問題，為了有效地實(shí)現(xiàn)該查詢，提出了近似路線查詢算法.ROIR的近似查詢利用近似收益代替精確收益.路線Ares的近似收益值由式(4)計(jì)算：

(4)

為了減少提煉過程的查詢代價(jià)，僅保留上層空間轉(zhuǎn)移圖用于查詢，由于轉(zhuǎn)移結(jié)點(diǎn)上不存儲(chǔ)精確的關(guān)鍵字收益值，僅在r簽名存儲(chǔ)固定區(qū)域內(nèi)的關(guān)鍵字分值信息，查詢結(jié)果返回區(qū)間收益而不能得到精確收益值.本文采用近似的方法估計(jì)轉(zhuǎn)移結(jié)點(diǎn)在某關(guān)鍵字上的收益值，基本思想假定收益與圓周面積成正比，關(guān)鍵字近似收益如定義2.

定義2.r簽名關(guān)鍵字近似收益.已知轉(zhuǎn)移結(jié)點(diǎn)vj中某一關(guān)鍵字的下界與上界收益值分別為Si和Si+1，且ri

(5)

數(shù)據(jù)組織模型只保留了上層轉(zhuǎn)移圖，對應(yīng)的索引結(jié)構(gòu)也只保留了擴(kuò)展的B+樹，同時(shí)設(shè)計(jì)了新的簽名存儲(chǔ)于樹上的每個(gè)結(jié)點(diǎn)之中，索引結(jié)構(gòu)命名為簽名B樹(balance tree with signature, BTS).以B+樹為基礎(chǔ)擴(kuò)展了結(jié)點(diǎn)的信息，每個(gè)結(jié)點(diǎn)存儲(chǔ)3部分內(nèi)容，包括鄰接表、r簽名和長度約束簽名(稱為L簽名).長度約束簽名存儲(chǔ)在轉(zhuǎn)移圖上，存儲(chǔ)以當(dāng)前結(jié)點(diǎn)為起始點(diǎn)、長度為L約束下經(jīng)過的所有結(jié)點(diǎn)關(guān)鍵字的最大收益值，且半徑L等間隔遞增.由于轉(zhuǎn)移圖上結(jié)點(diǎn)間的距離大于r簽名的半徑，因此被圓周包含的結(jié)點(diǎn)的關(guān)鍵字收益值由r簽名半徑最大一列的收益值表示.

定義3.L簽名關(guān)鍵字近似收益.已知轉(zhuǎn)移結(jié)點(diǎn)v在L簽名上某一關(guān)鍵字的下界與上界收益值分別為Si和Si+1，且Li

(6)

定義4.路線預(yù)期收益.已知當(dāng)前查詢路線A，在剩余長度約束L下路線訪問結(jié)點(diǎn)v時(shí)，路線預(yù)期收益為各個(gè)關(guān)鍵字已獲與可獲收益值之間的最大收益值之和，由查詢路線A得到各關(guān)鍵字已獲取的收益值，由結(jié)點(diǎn)v得到剩余長度下各關(guān)鍵字可獲取的收益值，如式(7)所示：

Mexp_Q(A,v)=

(7)

算法3是查詢一條近似路線的算法，當(dāng)起始點(diǎn)的鄰接點(diǎn)未全部訪問時(shí)，每次優(yōu)先訪問收益最大的鄰接點(diǎn)v(行②③).若路線滿足長度約束，需要計(jì)算該路線的近似收益MQ(A′)，并與候選路線A的近似收益MQ(A)進(jìn)行比較，若當(dāng)前路線的近似收益大于候選路線的近似收益，則當(dāng)前路線是更優(yōu)的結(jié)果，需要對候選路線進(jìn)行更新(行④～⑦)；若不存在候選路線，當(dāng)前路線是通過best-first方法搜索出的最優(yōu)路線，因此直接加入候選解中.每次比較候選路線后，需要將當(dāng)前路線最后一個(gè)結(jié)點(diǎn)彈出并標(biāo)記(行⑧⑨).當(dāng)搜索長度小于約束條件時(shí)，將結(jié)點(diǎn)加入路線中并通過深度優(yōu)先搜索(DFS)過程獲取可行路線(行⑩～)，與算法2類似.若路線當(dāng)前結(jié)點(diǎn)的所有鄰接點(diǎn)都已經(jīng)被訪問，將該結(jié)點(diǎn)從路線中刪除，直到起始點(diǎn)的鄰接點(diǎn)都被標(biāo)記(行).

算法3.ROIR近似查詢算法r-RegionApprox.

輸入：QU(v0,C,r,L)、基于圖G建立的索引BTSG;

輸出：一條近似收益最高的路線A.

①A′={v0},A′.last=v0,A={};

② while (A′不為空)

③ for (A′.last中未訪問的鄰接點(diǎn)v)

④ if (dist(A′.last,v)+A′.L≥L)

⑤ if (MQ(A′)>MQ(A))

⑥A=A′;

⑦ end if

⑧vtag=A′.pop(),標(biāo)記vtag;

⑨A′.last=A′.top();

⑩ else

定理2.當(dāng)一條路線A′訪問到結(jié)點(diǎn)v時(shí)，其預(yù)期收益值小于路線A的近似收益值時(shí)，即Mexp(A′,v)

證明.當(dāng)Mexp(A′,v)

證畢.

本節(jié)提出的近似ROIR，利用面積近似的方法計(jì)算路線收益值，返回結(jié)果較優(yōu)的路線.采用近似的方法代替提煉過程，減少了訪問IR樹的I/O操作，加快了查詢效率.

定理3.近似路線查詢算法的收益近似率為1/ε.

證明.假設(shè)查詢結(jié)果Ares，滿足長度約束L，查詢半徑為r，查詢的關(guān)鍵字集合為C，Ares包含n個(gè)轉(zhuǎn)移結(jié)點(diǎn)，近似率為

(8)

(9)

(10)

(11)

則存在

(12)

證畢.

3 實(shí)驗(yàn)分析

本節(jié)對所提出的ROIR精確算法及近似算法進(jìn)行實(shí)驗(yàn)評估.

3.1 數(shù)據(jù)集

實(shí)驗(yàn)采用北京市75 963條POI數(shù)據(jù)和北京市2012年10月、11月這2個(gè)月的出租車上下車數(shù)據(jù).本文選擇了賓館、餐飲、大廈、商場、休閑娛樂等10個(gè)類別作為實(shí)驗(yàn)數(shù)據(jù)的關(guān)鍵字.

實(shí)驗(yàn)中類別的偏好值利用高斯函數(shù)賦值.以北京市天安門為中心，采用高斯分布為不同區(qū)域范圍內(nèi)的POI點(diǎn)賦值，從二環(huán)以內(nèi)到五環(huán)以外期望值分別為8.0～2.0，標(biāo)準(zhǔn)差為1.0～3.0.將用戶軌跡與近鄰POI進(jìn)行匹配，利用軌跡的轉(zhuǎn)移關(guān)系生成轉(zhuǎn)移圖，通過設(shè)置區(qū)域間距大小及POI點(diǎn)的密度補(bǔ)充轉(zhuǎn)移圖中結(jié)點(diǎn)的數(shù)量.通過設(shè)置連通數(shù)的數(shù)量篩選軌跡，剪去流行度低的路線，利用長度限制剪枝結(jié)點(diǎn)間距離較遠(yuǎn)的路線.

3.2 精確查詢算法比較

本文結(jié)合現(xiàn)有算法設(shè)計(jì)實(shí)現(xiàn)了2個(gè)基準(zhǔn)算法的ROIR，利用3種優(yōu)化策略實(shí)現(xiàn)了相應(yīng)的優(yōu)化算法，比較了這些算法的收益值及查詢效率，其中查詢效率用I/O次數(shù)度量.各算法如下.

1) BaseDFS.文獻(xiàn)[3]處理top-k空間多樣性問題，本文采用DFS實(shí)現(xiàn)了top-1路線查詢，作為比較算法，命名為BaseDFS.該算法在獲得轉(zhuǎn)移圖上候選路線后，以路線各轉(zhuǎn)移結(jié)點(diǎn)為中心，查詢范圍r內(nèi)POI序列是否符合查詢結(jié)果.

2) BaseRegion.利用文獻(xiàn)[1]中過濾—提煉查詢2階段方式實(shí)現(xiàn)，實(shí)現(xiàn)無r簽名優(yōu)化的空間興趣區(qū)域路線查詢算法，在過濾階段返回所有候選路線集，在提煉階段求得路線精確收益值并選取收益值高的路線返回.

3) Region.本文提出的ROIR算法，該算法利用r簽名在過濾階段采用上下界收益值剪枝方法獲取候選路線集，在提煉階段遍歷IR樹比較求得最優(yōu)路線，見算法1.

4) RegionLow,RegionUp，RegionAvg.這3個(gè)算法是在Region算法基礎(chǔ)上采用下界收益值優(yōu)先策略所實(shí)現(xiàn)的算法.算法在提煉階段分別按候選路線的下界收益值、上界收益值、上下界收益值的均值從大到小次序訪問IR樹，對收益值進(jìn)行精確計(jì)算并剪枝求得最終結(jié)果.

3.2.1 路線收益比較

本節(jié)比較了在長度和關(guān)鍵字?jǐn)?shù)量變化的情況下，BaseDFS算法和Region算法的收益值.

圖5(a)比較了長度約束對路線收益的影響，給定關(guān)鍵字約束{賓館，餐館，商場，商務(wù)中心，娛樂}，各算法隨著長度的增長，收益均呈上升趨勢.其中，BaseDFS算法的收益值最低，Region算法的收益值最高.在r從200～800 m變化時(shí)，r越小，收益值越趨向于BaseDFS算法收益值；r越大，收益值趨向于800-Region算法收益值.隨著長度增長，查詢返回一條路線所包含的轉(zhuǎn)移結(jié)點(diǎn)增多，算法收益值也會(huì)增大.BaseDFS算法返回的是POI點(diǎn)組成的序列路線，Region算法返回的是區(qū)域組成的路線，增大了解空間，收益值高于BaseDFS算法的收益值.另外，隨著區(qū)域半徑r的增大，區(qū)內(nèi)包含的POI數(shù)量不斷增多，算法整體收益值的差距較小.

Fig. 5 Profit comparisons of the exact algorithms圖5 精確算法收益比較

圖5(b)比較了關(guān)鍵字?jǐn)?shù)量對路線收益的影響，給定起始點(diǎn)，路線長度約束L=10 km，各算法的收益值均隨著關(guān)鍵字?jǐn)?shù)量的增多而增大.對于BaseDFS算法，每個(gè)POI點(diǎn)僅包含一個(gè)關(guān)鍵字，路線收益值來源局限于單個(gè)POI點(diǎn)；而Region算法利用區(qū)域?qū)ο蟠纥c(diǎn)對象，區(qū)域中包含不同關(guān)鍵字的數(shù)量增多，使得一個(gè)區(qū)域可以提供多個(gè)關(guān)鍵字的收益值.因此當(dāng)區(qū)域半徑越小，涵蓋的POI點(diǎn)越少，則收益越小，區(qū)域半徑越大，則收益越大.

Fig. 6 Effects of different constraints on algorithms efficiency圖6 不同約束條件對算法效率的影響

Region算法在各類約束條件下，由于利用區(qū)域的方式擴(kuò)展了POI點(diǎn)的數(shù)量，因此較BaseDFS算法能夠獲取更高的收益值.圖5也驗(yàn)證了Region算法在路線收益值方面的優(yōu)越性.

3.2.2 算法效率比較

圖6是不同約束條件對算法效率的影響比較，算法效率由I/O次數(shù)度量，I/O次數(shù)越少，算法效率越高.圖6(a)～(c)分別為長度約束、區(qū)域半徑、關(guān)鍵字?jǐn)?shù)量對算法效率的影響.圖6(b)中當(dāng)區(qū)域半徑大于300 m時(shí)，BaseDFS算法由于其代價(jià)過高無法完成路線搜索.結(jié)果顯示本文設(shè)計(jì)的優(yōu)化算法效率均高于基本算法的效率，對比BaseDFS算法，優(yōu)化算法利用興趣區(qū)域減少了訪問結(jié)點(diǎn)的數(shù)量；對比BaseRegion算法，本文算法設(shè)計(jì)了簽名信息用于剪枝路線，減少了候選路線的數(shù)量.結(jié)果顯示，RegionUp算法效率高于RegionAvg，RegionLow算法效率.

3.3 近似路線查詢算法比較

對于近似路線查詢算法，本節(jié)將BaseDFS算法、BaseRegion算法、Region算法和RegionUp算法作為比較算法，比較算法的收益值及效率.RegionApprox是本文提出的算法，見算法3.

1) 近似路線收益比較

本節(jié)比較了長度及關(guān)鍵字?jǐn)?shù)量變化情況下BaseDFS,Region,RegionApprox算法的收益，如圖7所示，關(guān)鍵字為{賓館，餐館，商場，商務(wù)中心，娛樂}，長度約束L=10 km，半徑r=200 m.

Fig. 7 Profit comparisons of approximate algorithms圖7 近似算法收益比較

圖7(a)是長度約束下的路線收益比較，結(jié)果顯示長度越長，路線收益越大.Region算法的收益值最高，RegionApprox算法的收益值接近Region算法的收益，BaseDFS算法的收益值最低.圖7(b)是不同關(guān)鍵字?jǐn)?shù)量下的路線收益比較，結(jié)果顯示關(guān)鍵字?jǐn)?shù)量的增多會(huì)使得收益值增大，收益值由大到小排序分別是Region,RegionApprox,BaseDFS算法.

Fig. 8 Efficiency comparisons of approximate algorithm圖8 近似算法效率比較

2) 近似算法效率比較

本節(jié)比較了長度約束L、區(qū)域半徑r及關(guān)鍵字?jǐn)?shù)量|C|的變化下，BaseDFS,BaseRegion,RegionUp,RegionApprox算法的總I/O讀取次數(shù)，如圖8所示.默認(rèn)設(shè)置長度約束L=10 km，半徑r=200 m，關(guān)鍵字為{賓館，餐館，商場，商務(wù)中心，娛樂}.由圖8(a)～(c)表明算法的總I/O讀取次數(shù)均隨約束條件的變化呈上升趨勢，且RegionApprox算法的效率最高.

RegionApprox算法利用B+樹中簽名的近似收益值作為解，只保留了過濾階段的操作而不再執(zhí)行提煉階段的操作，減少了轉(zhuǎn)移圖上結(jié)點(diǎn)在IR樹中的I/O次數(shù).

4 相關(guān)工作

本節(jié)介紹空間關(guān)鍵字查詢、偏好路線查詢等相關(guān)工作.

4.1 空間關(guān)鍵字查詢

空間關(guān)鍵字查詢返回滿足文本約束與空間位置要求的結(jié)果，文本約束以關(guān)鍵字集合表示[11-12].空間關(guān)鍵字查詢可分為POI對象查詢[13-14]、組對象查詢[15-16]、區(qū)域查詢等[17-21].其中，POI對象查詢返回單個(gè)POI對象滿足查詢關(guān)鍵字需求，包括滿足關(guān)鍵字集且距離最近的k個(gè)對象的布爾kNN查詢、返回前k個(gè)最佳對象的top-k查詢、返回布爾關(guān)鍵字表達(dá)式且位于指定空間區(qū)域的布爾范圍查詢.空間關(guān)鍵字組對象查詢指一組對象符合共同查詢關(guān)鍵的需求.空間關(guān)鍵字區(qū)域查詢返回一個(gè)矩形或圓形區(qū)域，其中包含最多的給定查詢關(guān)鍵字[17-18]、區(qū)域中的關(guān)鍵字集合與查詢關(guān)鍵字集合具有最高的文本相似度[20].

本文所提出ROIR與現(xiàn)有的空間關(guān)鍵字區(qū)域查詢均查找與輸入查詢關(guān)鍵字集相關(guān)的空間區(qū)域.然而，本文提出的查詢返回多個(gè)區(qū)域組成的路線，具有路線規(guī)劃功能.

4.2 偏好路線查詢

偏好路線查詢提供用戶個(gè)性化的路線搜索服務(wù)，可以分為AOP(arc orienteering problem)問題[22-23]、POI及關(guān)鍵字覆蓋路線問題[5-6,24-25]、關(guān)鍵字優(yōu)化路線問題[2,7].

在AOP問題中，結(jié)點(diǎn)上存儲(chǔ)收益值，邊表示代價(jià)(如距離成本)，查詢的目標(biāo)是獲取給定代價(jià)約束下最大化結(jié)點(diǎn)收益和的路線.ROIR與AOP均為在一定代價(jià)約束下最大化路線收益.區(qū)別在于，AOP路線由POI序列組成，ROIR路線由興趣區(qū)域序列組成.

POI及關(guān)鍵字覆蓋路線查詢的目的是獲取由POI組成的路線，返回路線上的POI所包含的關(guān)鍵字覆蓋了指定關(guān)鍵字，或者關(guān)鍵字滿足一定的關(guān)系約束下同時(shí)最小化時(shí)間或距離代價(jià).其中，文獻(xiàn)[25]研究了關(guān)鍵字覆蓋情況下top-k路線多樣性問題.文獻(xiàn)[5]搜索與用戶提供的線索最匹配的路徑，線索由用戶提供的關(guān)鍵字間的關(guān)系表示.文獻(xiàn)[6]提出了關(guān)鍵字訪問序列約束的路線查詢.

關(guān)鍵字優(yōu)化路線問題將路線長度作為約束條件，最大化關(guān)鍵字收益或關(guān)鍵字相似度.其中，文獻(xiàn)[1]提出了關(guān)鍵字敏感的路線查詢，查詢的目標(biāo)是找到一條覆蓋一組用戶指定的查詢關(guān)鍵字并最大化給定成本預(yù)算內(nèi)的目標(biāo)得分.文獻(xiàn)[4]考慮查詢對象不同關(guān)鍵字的權(quán)重，提出了一個(gè)基于關(guān)鍵字得分的路線優(yōu)化問題.文獻(xiàn)[2]提出一個(gè)距離成本約束下的路線查詢，用于檢索與用戶指定關(guān)鍵字集最相關(guān)的路徑.文獻(xiàn)[7]提出興趣路徑查詢問題，尋找收集最多查詢關(guān)鍵字?jǐn)?shù)量的最優(yōu)路線.

與文獻(xiàn)[2,7]相似，本文提出的ROIR屬于空間關(guān)鍵字的偏好路線查詢.現(xiàn)有的空間關(guān)鍵字偏好路線查詢返回的路線由POI點(diǎn)組成，而ROIR搜索由興趣區(qū)域組成的路線.

5 結(jié) 論

本文提出了一種面向空間興趣區(qū)域的路線查詢，將傳統(tǒng)空間關(guān)鍵字路線查詢的POI對象擴(kuò)展為空間興趣區(qū)域，提高了路線查詢的適用性.設(shè)計(jì)了2層數(shù)據(jù)模型及相應(yīng)的索引結(jié)構(gòu)，設(shè)計(jì)了過濾與提煉2階段算法的精確算法，以及高效的近似查詢算法.通過詳細(xì)的分析，驗(yàn)證了所提出方法的有效性.提出的ROIR可以廣泛應(yīng)用于興趣路線規(guī)劃，特別適用于結(jié)伴出行情況，允許用戶在區(qū)域內(nèi)分散訪問各自偏好的地點(diǎn).

作者貢獻(xiàn)聲明：劉俊嶺負(fù)責(zé)問題定義、算法的提出及全文的撰寫；劉柏何負(fù)責(zé)算法的實(shí)現(xiàn)與實(shí)驗(yàn)對比；鄒鑫源負(fù)責(zé)算法設(shè)計(jì)與實(shí)驗(yàn)對比分析；孫煥良參與實(shí)驗(yàn)數(shù)據(jù)的收集與論文的修改.