李艷紅，歐昱宏，毛德權(quán)，龐栩

（1 中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院，武漢 430074；2 重慶市公安局 渝北區(qū)分局，重慶 401120）

1 問題的引入

隨著智能移動終端的應(yīng)用，以及地理位置與文本數(shù)據(jù)的融合，大量的空間文本對象應(yīng)運(yùn)而生，但僅考慮空間文本相似度的空間關(guān)鍵詞查詢有時無法滿足成員的特殊需求.例如一組成員在晚上10點想要查詢一家能同時供應(yīng)中餐和西餐的餐廳，但大部分餐廳此時已經(jīng)暫停營業(yè)，若仍用傳統(tǒng)的查詢算法，返回的結(jié)果很可能不是成員所需要的.

如今，為分散在各地的人們規(guī)劃出最佳行程，不僅包括成員所需訪問的不同類型興趣點的查詢，也要基于滿足約束的興趣點規(guī)劃出最優(yōu)路徑.例如，圖1顯示了一個Euclidean空間中的TDGTP（Time Dynamic Group Travel Planning）查詢，其中 3 個成員u1、u2和u3的起始位置和目標(biāo)位置分別為（s1，d1）、（s2，d2）、（s3，d3）.成員 u2和u3需要找到一家能同時滿足牛排和漢堡這兩個關(guān)鍵詞的餐館，然后成員u1與他們在音樂廳碰面去聽音樂（藍(lán)線所示），聽完音樂后成員u3直接回到家中（綠線所示），其余成員則去書店買書，最后回到各自的家中.通常會遇到滿足關(guān)鍵詞要求的興趣點鄰近小組中的某位成員，但距離組內(nèi)其他成員較遠(yuǎn)的情況，此時該行程規(guī)劃可能不是最佳路徑.為此，希望找到滿足該組成員要求且總行程距離最小的最佳路徑，其中總行程距離是組中所有成員的行程距離之和，每個成員的行程從起始位置開始，然后訪問滿足要求的興趣點，最終到達(dá)目標(biāo)位置，結(jié)束行程.

圖1 一個TDGTP場景Fig.1 A TDGTP scene

當(dāng)前研究人員并未考慮行程規(guī)劃中新成員加入或已有成員離開的問題，也沒有在行程規(guī)劃中考慮興趣點與查詢需求的時間匹配問題.因此，本文提出了一個新問題——時間感知的動態(tài)組旅行規(guī)劃查詢（TDGTP）問題.上述示例中有待解決的問題有：

（1）在興趣點數(shù)量龐大的空間中，如何修剪掉不滿足要求的興趣點，快速找出符合所有成員要求的興趣點區(qū)域？

（2）對于一組成員的旅行規(guī)劃，怎樣才能找出符合所有成員要求的興趣點？

（3）如何使該行程的總距離達(dá)到最小，返回一個最佳路徑序列？

為應(yīng)對上述難題，本文提出以下解決方案：首先將R-Tree 與倒排文本列表和時間文本列表結(jié)合，構(gòu)建了TIR-Tree 索引結(jié)構(gòu)及相關(guān)算法KMA（Keyword Matching Algorithm）對興趣點進(jìn)行索引；然后，依據(jù)“橢圓上的點到兩焦點的距離之和小于橢圓外的點到兩焦點的距離之和”的性質(zhì)，設(shè)計了ESRA（Elliptic Search Refinement Algorithm）算法將空間數(shù)據(jù)集的搜索區(qū)域剪枝細(xì)化；最后，提出BestTD（Best Time Dynamic）算 法來解決 TDGTP問題.

綜上所述，本文主要貢獻(xiàn)如下：

（1）正式定義并研究了時間感知的動態(tài)組旅行規(guī)劃查詢（TDGTP）問題；

（2）設(shè)計了一種有效的綜合索引結(jié)構(gòu)，稱為TIR-Tree，提出了基于時間和關(guān)鍵詞的剪枝來高效、快速地查找相應(yīng)的興趣點；

（3）對于大規(guī)模的興趣點集，開發(fā)了一種基于橢圓區(qū)域的剪枝，利用橢圓性質(zhì)，設(shè)計了ESRA（Elliptic Search Refinement Algorithm）算法來對空間數(shù)據(jù)集剪枝，從而減少檢索數(shù)據(jù)集的數(shù)量.

2 相關(guān)工作

文獻(xiàn)［1］討論了空間數(shù)據(jù)庫中的一種新型行程規(guī)劃查詢（TPQ），研究了度量空間中TPQ 的快速近似算法.文獻(xiàn)［2］首次引入團(tuán)體旅行計劃（GTP）查詢的概念并針對Euclidean 空間做了介紹，將kGTP 定義為：如果一個組查詢一個GTP 的k組數(shù)據(jù)點，則該查詢稱為k 組旅行計劃（kGTP）查詢.文獻(xiàn)［3］將POI搜索區(qū)域細(xì)化為橢圓區(qū)域，計算組中每個成員形成的橢圓區(qū)域，其中每個橢圓的焦點位于相應(yīng)成員的源位置和目標(biāo)位置上.文獻(xiàn)［4］研究了道路網(wǎng)絡(luò)中的組最優(yōu)排序路線（GOSR）查詢問題，指出在Euclidean 空間中提出的GTP 算法會產(chǎn)生非常高的查詢處理開銷，且不能擴(kuò)展到道路網(wǎng)中.

文獻(xiàn)［5］為克服固定團(tuán)隊規(guī)模的限制，提出了NaiveDGTP算法和FastDGTP算法來處理DGTPQ，但這兩種方法在道路網(wǎng)上并不適用.文獻(xiàn)［6］提出了DGTP 算法和M-DGTP 算法來解決道路網(wǎng)上的小組規(guī)劃問題，相比之下，M-DGTP 算法處理的時間較快，內(nèi)存開銷較小，但該算法需要依次訪問道路網(wǎng)上的興趣點，處理的數(shù)據(jù)對象多且時間長.文獻(xiàn)［7-8］研究了空間數(shù)據(jù)庫中的序列團(tuán)體旅行計劃查詢（SGTPQ）問題，對于不同的團(tuán)體規(guī)模和查詢區(qū)域，所提出的PGNE算法響應(yīng)時間較短，內(nèi)存開銷較少.

文獻(xiàn)［9］提出了基于方向感知的空間關(guān)鍵詞搜索，它以空間點、方向和一組關(guān)鍵詞為參數(shù)，找到查詢的k 個最近鄰居，每個鄰居都位于搜索方向上且包含所有查詢關(guān)鍵詞.文獻(xiàn)［10］提出了時間感知布爾空間關(guān)鍵詞查詢（TABSKQ），設(shè)計了一種高效的混合索引結(jié)構(gòu)TA-tree 及相關(guān)算法來處理TABSKQ.文獻(xiàn)［11］提出了道路網(wǎng)絡(luò)上的時間感知空間關(guān)鍵詞查詢（TSK）問題，設(shè)計了一種高效索引結(jié)構(gòu)TG 及基于TG 索引的有效算法.文獻(xiàn)［12］提出了時間感知空間關(guān)鍵詞覆蓋查詢（TSKCQ），設(shè)計了PQA 算法去評估成員在時間和空間上的滿意度，并返回具有最佳成本函數(shù)的對象值.

文獻(xiàn)［13］首次探討了在查詢位置與空間對象之間的距離最短路徑道路網(wǎng)絡(luò)上處理top-k 空間關(guān)鍵詞查詢問題.文獻(xiàn)［14］研究了最接近關(guān)鍵詞搜索的最佳覆蓋，提出的keyword-NNE 算法能減少生成的候選關(guān)鍵詞覆蓋數(shù)量.文獻(xiàn)［15］引入了一種新穎的空間關(guān)鍵詞覆蓋（SK-COVER）問題，建立了一個O（log m）近似算法，設(shè)計了有效的訪問策略和修剪規(guī)則，以提高整體效率和可擴(kuò)展性.

3 問題描述

3.1 興趣點

假設(shè)在數(shù)據(jù)空間有一組時空文本對象o∈O，每個對象 o 定義為（id，doc，t），其中 o.id 是對象 o 的唯一標(biāo)識，o.doc是一組用來描述對象o的關(guān)鍵詞集合，其形式為 o.doc=｛（o.key1），（o.key2），…，（o.keyi）｝，o.t表示對象o的有效時間，形式為（st，et）其中st和et分別為對象o的起始時間和結(jié)束時間.其中，將o.t進(jìn)行整數(shù)化，以一個小時為單位.例如，購物中心的有效時間是（09：00-12：00），（09：00-12：00）中的任何時間戳都可以轉(zhuǎn)化為單位時間（9，12）.表1 列出的是本文中出現(xiàn)的符號及其定義.表2是對象信息.

表1 符號與定義Tab.1 Symbols and definitions

表2 對象信息Tab.2 Object information

3.2 時間感知的動態(tài)組旅行規(guī)劃查詢

已知數(shù)據(jù)集O和一個時間感知的動態(tài)組旅行規(guī)劃（TDGTP）查詢q=（U，S，D，P，T），其中U=｛u1，u2，…，un｝表示小組成員集合，S=｛s1，s2，…，sn｝是每個成員ui的起始位置集合，D=｛d1，d2，…，dn｝是目標(biāo)位置集合.P 是一組關(guān)鍵詞集合，表示成員查詢目的.T 是成員指定的任意查詢時間區(qū)間如（9，12）.查詢q 返回一條各個成員從S 出發(fā)、到D 結(jié)束且符合q.P 和q.T約束條件的最佳路徑.

接下來是搜索區(qū)域邊界的計算.橢圓焦點的公式如下：

其中 si是成員 ui的起點，di是成員 ui的終點，n 為組成員數(shù)量.

橢圓主軸范圍為：

其中n 是小組成員數(shù)量，總行程距離是所有成員的行程距離之和.

4 索引結(jié)構(gòu)TIR-Tree

R-tree 是目前最流行的空間索引結(jié)構(gòu)之一，它運(yùn)用了空間分割理念，用作空間數(shù)據(jù)存儲的樹狀數(shù)據(jù)結(jié)構(gòu).倒排索引是實現(xiàn)“單詞-文檔矩陣”的一種具體存儲形式，是常用的文本索引結(jié)構(gòu)之一，通過倒排索引，可以根據(jù)單詞快速獲取包含這個單詞的文檔列表.傳統(tǒng)的空間查詢和關(guān)鍵詞搜索使用不同的索引技術(shù)和查詢算法耗時又費(fèi)力，為有效地處理TDGTP 問題，本文將R-tree 上的每個非葉子結(jié)點關(guān)聯(lián)上兩個倒排文件，在查詢包含空間文本信息的文件時擁有較高的效率，這種混合數(shù)據(jù)結(jié)構(gòu)被稱為TIR-Tree索引.

在二維空間中，對于不規(guī)則幾何圖形通常采用最小邊界矩形MBR 來構(gòu)建索引.本文采用MBR 的方法，從葉子結(jié)點開始用MBR 將空間框起來，結(jié)點越往上，框住的空間就越大，從而實現(xiàn)對空間的分割，如圖2所示：首先假設(shè)所有數(shù)據(jù)對象的位置都是二維空間下的點，圖中標(biāo)識了R6區(qū)域中的數(shù)據(jù)，將它看作是多個數(shù)據(jù)圍成的一個區(qū)域，為了實現(xiàn)R樹，用一個MBR 框住形成區(qū)域R6.采用同樣的方法，一共得到了4 個最基本的MBR，這些MBR 被存儲在非葉子結(jié)點中.下一步是進(jìn)行高一層的處理，此時的R3和R4這兩個矩形距離最為靠近，因此可用一個更大的矩形R1恰好框住這兩個矩形，同樣，R5和R6恰好被R2框住.所有最基本的MBR被框入更大的矩形中后，再次迭代，用更大的框框住這些矩形.

圖2 TIR-Tree的劃分Fig.2 Division of TIR-Tree

TIR-Tree 整體結(jié)構(gòu)如圖 3 所示 .TIR-Tree 以 R 樹的形式構(gòu)建，從空樹開始，不斷插入劃分的MBR，直到生成一棵完整的R 樹.每個非葉子結(jié)點用四元組（ra，rectangle，ra.di，ra.ti）表示，其中 ra 存儲的是子節(jié)點地址，rectangle 是覆蓋所有子結(jié)點的MBR 的最小矩形，ra.di 是關(guān)鍵詞描述標(biāo)識符，連接關(guān)鍵詞倒排文件列表，其中第一列為關(guān)鍵詞信息，第二列為包含對應(yīng)關(guān)鍵詞信息的子結(jié)點的MBR.ra.ti 是有效時間信息的標(biāo)識符，連接有效時間的倒排文件，其中第一列為有效時間信息，第二列為包含對應(yīng)時間信息的MBR.每個葉子結(jié)點包含許多形式為（o，o.rec，o.di，o.ti）的條目，其中o是數(shù)據(jù)空間的對象，o.rec是對象o 的邊界矩形，o.di 是對象o 的關(guān)鍵詞標(biāo)識符，o.ti是對象o有效時間的標(biāo)識符.

圖3 TIR-Tree綜合索引結(jié)構(gòu)Fig.3 TIR-Tree comprehensive index structure

5 查詢處理算法

這里首先提出基于TIR-Tree 的剪枝策略，然后介紹ESRA細(xì)化搜索空間算法和解決TDGTP查詢處理的BestTD算法.

5.1 基于TIR-Tree的剪枝策略

5.1.1 基于TIR-Tree的剪枝

引理1 已知一個TDGTP 查詢q=（U，S，D，P，T）和一個區(qū)域Ei，如果q.P ∩ Ei.P=?，則區(qū)域Ei可以被安全地削減.

證明 已知查詢的關(guān)鍵詞集合為q.P，區(qū)域Ei內(nèi)所有對象關(guān)鍵詞的并集為Ei.P.若q.P 與Ei的交集不為空，表示區(qū)域Ei內(nèi)有滿足查詢關(guān)鍵詞要求的對象；反之，區(qū)域Ei內(nèi)的對象都不滿足要求，可以被剪枝.

引理2 已知一個TDGTP 查詢q =（U，S，D，P，T）和一個區(qū)域Ei，如果q.T ∩ Ei.T= ?，則區(qū)域Ei可以被安全地削減.

證明 已知查詢q 的時間信息為q.T，區(qū)域Ei內(nèi)所有對象營業(yè)時間的最大區(qū)間為Ei.T.若q.T 與Ei.T的交集不為空，表示區(qū)域Ei內(nèi)有滿足查詢時間要求的對象；反之，區(qū)域Ei內(nèi)的對象的營業(yè)時間都在查詢給定的時間之外，可以被剪枝.

5.1.2 基于TIR-Tree的剪枝算法KMA

基于TIR-Tree 的剪枝算法KMA 具體流程見算法 1，初始化隊列 Qinit、集合 Ponec和指針 TNode，其中Qinit用來存放候選結(jié)點，Ponec用來保存所有符合約束的興趣點集合（第1行）.將TIR-tree的根結(jié)點放入隊列Qinit（第2 行）.當(dāng)隊列Qinit不為空，則從根結(jié)點自上而下地進(jìn)行處理，遍歷根結(jié)點的子結(jié)點.首先TNode指向隊列Qinit的頭元素，判斷TNode是否滿足查詢關(guān)鍵詞和時間約束；若滿足，繼續(xù)判斷TNode是否為非葉子結(jié)點，若是，則將該結(jié)點的子結(jié)點存入隊列Qinit，否則將該結(jié)點存入集合Ponec（第2-9 行）.遍歷完成后，返回集合Ponec（第10行）.

images/BZ_114_1284_1524_2243_1581.png輸入：一個TDGTP查詢q=（U，S，D，P，T），關(guān)于數(shù)據(jù)集O的TIR-Tree輸出：滿足空間關(guān)鍵詞要求的興趣點集Ponec 1 Ponec=?；Qinit=?；TNode=? 2 將TIR-Tree樹的根結(jié)點R0放入隊列Qinit 3 while Qini≠t? do 4 TNode=Qinit.pop（）5 if TNode的關(guān)鍵詞∩q.P and TNode的時間∩q.T then 6 if TNode是非葉子結(jié)點then 7 Qinit.Push（TNode.children）8 else 9 Ponec ←TNode 10 Return Ponec

5.2 基于搜索區(qū)域的剪枝

5.2.1 搜索空間的剪枝

已知一個TDGTP 查詢q=（U，S，D，P，T）和一個數(shù)據(jù)集搜索空間，將搜索空間從整個搜索區(qū)域減小到TDGTP 查詢區(qū)域.為了計算搜索區(qū)域的邊界，需計算一組橢圓區(qū)域集.首先根據(jù)公式（1）、（2）計算初始成員（此時尚未加入的成員）的起始位置和目標(biāo)位置的質(zhì)心，即橢圓焦點，主軸為Tdist，形成E1橢圓；然后分別計算在某個興趣點新加入成員的起始位置和目標(biāo)位置的質(zhì)心，形成Ei橢圓；最后區(qū)域為所有橢圓的交集，見圖4.

圖4 搜索區(qū)域的細(xì)化Fig.4 The refinement of search area

圖 4 中，U =｛u1，u2，u3，u4，u5｝，小組成員的起始位置為 S=｛s1，s2，s3，s4，s5｝，目標(biāo)位置為 D=｛d1，d2，d3，d4，d5｝.u1和 u3是初始成員，u4和 u5是在第 1 個興趣點加入的成員，u2是在第2 個興趣點加入的成員.第11 個橢圓區(qū)域E1；然后計算第2 個橢圓焦點Cs2=計算第3 個橢圓焦點，因為第3 輪加入的成員只有u2，所以第3個橢圓的焦點就是s2和d2，形成第3個橢圓區(qū)域E3.R是3個橢圓E1，E2，E3的交集區(qū)域.

5.2.2 搜索區(qū)域ESRA算法

橢圓剪枝算法見算法2.兩個隊列Scand，Dcand以及3個集合cvs，cvd，Cur初始化為空，集合Ptwoc初始為O.其中，Scand用來存放成員起點，Dcand用來存放成員目標(biāo)點，Ptwoc用來存放橢圓交集內(nèi)的興趣點，cvs 和cvd分別保存計算的橢圓焦點（第1 行）.將每輪加入行程的成員起點和終點存入Scand，Dcand（第2行）.當(dāng)兩個隊列不為空時，根據(jù)公式（1）、（2）計算每一輪次的幾何質(zhì)點，分別存放在cvs 和cvd 中，然后使用FindElliptic 函數(shù)形成橢圓區(qū)域，并將該區(qū)域內(nèi)的興趣點存入Cur，Ptwoc存放所有橢圓交集區(qū)域的興趣點（第3-9行）；最后返回集合Ponec（第10行）.

images/BZ_115_242_2303_1201_2360.png輸入：S=｛s1，s2，…，si｝，D=｛d1，d2，…，di｝，O=｛o1，o2，…，oi｝輸出：輸出細(xì)化區(qū)域范圍的興趣點集Ptwoc 1 Ptwoc =O ；cvs=? ；cvd=? ；Scand=? ；Dcand=? ；Cur=? 2 將S、D按照加入行程的順序排列分別存入Scand，Dcand 3 while Scand ≠? and Dcand ≠? do 4 Cens=Scand.pop（）5 Cend=Dcand.pop（）6 cvs←按照公式（1）計算Cs 7 cvd←按照公式（2）計算Cd 8 Cur ←將 FindElliptic（cvs，cvd，Tdist）內(nèi)的興趣點9 Ptwoc=Ptwoc ∩Cur 10 Return Ptwoc

5.3 基于時間感知的動態(tài)組旅行規(guī)劃BestTD算法

前兩小節(jié)討論的基本算法分別返回滿足約束條件的興趣點集，在此基礎(chǔ)上，將興趣點按照關(guān)鍵詞排序，得到所有的候選路徑，然后對候選路徑序列進(jìn)行遍歷，根據(jù)公式（4）、（5）計算候選路徑的距離，從而獲得總行程距離最小的最優(yōu)路徑.

查詢算法見算法3.首先初始化3 個集合PT，LTcand和 LT 及一個隊列 PTcand，Lmin被初始化為∞，（PT用來存放算法1 和算法2 剪枝后的興趣點，PTcand用來存放排列后的候選路徑，LTcand用來保存隊列PTcand出隊元素，LT 存放篩選后的最優(yōu)路徑）（第1行）.調(diào)用KMA 算法和ESRA 算法，將返回的集合交集存放在PT，并將PT 中的興趣點按照關(guān)鍵詞排列的候選路徑存入 PTcand（第 2-3 行）.當(dāng) PTcand不為空時，遍歷每條候選路徑，根據(jù)公式（4）和（5）計算出每條候選路徑的總行程距離TD，將TD 與Lmin比較，若TD 小于Lmin，此時的候選路徑存入LT，最小總距離行程的值賦值給Lmin（第4-12 行）.最后返回路徑LT（第13行）.

images/BZ_115_1284_1478_2243_1535.png輸入：一個TDGTP查詢q=（U，S，D，P，T），關(guān)于數(shù)據(jù)集O的TIRTree，O=｛o1，o2，…，oi｝輸出：最優(yōu)路徑LT 1 PT = ?；PTcand = ?；LT= ?；Lmin= ∞；LTcand= ? 2 PT←KMA（q，O）∩ ESRA（S，D，O）3 將PT中的興趣點o按照q.P的順序排列并插入PTcand 4 while PTcand ≠? do 5 LTcand =PTcand.pop（）6 n←|U|7 按照公式（4）計算PD 8 按照公式（5）計算TD 9 if TD ＜Lmin then 10 LT=LTcand 11 Lmin=TD 12 end if 13 查詢結(jié)束，返回LT

算法復(fù)雜度分析：根據(jù)算法1，在整個搜索空間內(nèi)，假設(shè)關(guān)鍵詞的總和為Nk，查詢關(guān)鍵詞數(shù)量為|q.P|，每個興趣點平均分配Ki個關(guān)鍵詞，此時獲得滿足2 是返回橢圓交集區(qū)域內(nèi)的興趣點，此時滿足關(guān)鍵算法2 的基礎(chǔ)上，算法3 檢索到在橢圓交集區(qū)域內(nèi)滿足關(guān)鍵詞和時間約束條件的興趣點，綜上所述，令空間對象總數(shù)為|O|，則滿足條件的對象總數(shù)為

算法3 中，若不采用剪枝策略，此時執(zhí)行次數(shù)m為|O|，則算法3 的最壞時間復(fù)雜度為O（|O|）；當(dāng)剪枝|O|，while 內(nèi)的語句會隨著問題規(guī)模m 的增加呈線性

6 實驗案例

6.1 實驗設(shè)置

本文以路網(wǎng)數(shù)據(jù)集的結(jié)點位置作為興趣點對象位置，使用2 個真實的路網(wǎng)數(shù)據(jù)集——美國California和德國Oldenburg真實路網(wǎng)數(shù)據(jù)在Euclidean空間評估算法，如表3所示.CA 路網(wǎng)有21048個結(jié)點和21693 條邊.使用Zipfian 分布為每個對象分配2-3 個關(guān)鍵詞，每個關(guān)鍵詞中的平均、最大和最小對象數(shù)分別為 319、3024 和 123.OL 路網(wǎng)包含 6105 個結(jié)點和7305條邊，使用Zipfian 分布為每個對象分配2-3 個關(guān)鍵詞，每個關(guān)鍵詞中的平均、最大和最小對象數(shù)分別為103、887 和33.

表3 實驗數(shù)據(jù)集Tab.3 Experiment datasets

本實驗將其數(shù)據(jù)空間歸化成一個1000×1000平方單位面積，使用TIR-Tree結(jié)構(gòu)來索引數(shù)據(jù)對象.對3 個參數(shù)（如表4 所示）進(jìn)行設(shè)置：成員數(shù)量n、查詢關(guān)鍵詞個數(shù)m 以及橢圓長軸的大小Tdist.本次實驗設(shè)備為Intel Core i5-5200U，2.20 GHz CPU，8.00 GB RAM Windows 10 的計算機(jī)，所有算法在Java 1.8.0_191的運(yùn)行環(huán)境下完成.

表4 參數(shù)設(shè)置Tab.4 Parameters setting

6.2 實驗結(jié)果

本節(jié)將展示 BestTD 算法與 TABASSUM 等人［5］提出的NaiveDGTP 算法處理TDGTP 查詢的性能比較分析.

（1）數(shù)據(jù)集的影響.圖5（a）和5（b）分別顯示了兩種算法在CA 和OL 數(shù)據(jù)集下處理時間和內(nèi)存開銷.實驗結(jié)果表明：不管是查詢時間還是內(nèi)存開銷，BestTD 算法都要優(yōu)于NaiveDGTP 算法.這是因為NaiveDGTP 基于動態(tài)規(guī)劃，隨著數(shù)據(jù)結(jié)點的增加，最短路徑和部分行程的計算量也在增加.

圖5 兩種算法在不同數(shù)據(jù)集下的性能Fig.5 Performance of the two algorithms in different datasets

（2）查詢關(guān)鍵詞m的影響.實驗結(jié)果表明（圖6），兩種算法的查詢處理時間均隨查詢關(guān)鍵詞數(shù)量的增加而增加，但BestTD 算法的查詢處理時間遠(yuǎn)小于NaiveDGTP 算法.這是因為隨著查詢關(guān)鍵詞個數(shù)的增加，查詢的搜索范圍變大，查詢處理對象的數(shù)量增加.但BestTD 算法相較于NaiveDGTP 算法效率要高，它能夠根據(jù)查詢關(guān)鍵詞更快地查詢到滿足條件的對象.因此，從圖6 可以看出，在查詢關(guān)鍵詞數(shù)量的影響下，BestTD 算法查詢性能優(yōu)于NaiveDGTP算法.

圖6 查詢關(guān)鍵詞的影響Fig.6 Impact of query keywords

（3）組大小n 的影響.圖7 顯示了組大小對兩種方法的影響，正如預(yù)想的那樣，BestTD和NavieDGTP兩種算法的查詢時間都隨著組大小的增加而增加.因為組大小的增加將導(dǎo)致更大量的路徑計算，從而導(dǎo)致處理時間變長.從結(jié)果中觀察到，BestTD 所需要的處理時間要比NavieDGTP少得多.

圖7 組大小的影響Fig.7 Impact of group size

（4）橢圓主軸大小Tdist的影響.圖8顯示了隨著橢圓主軸大小的增大，兩種方法的處理時間都有所增加.這是因為橢圓主軸越大，搜索區(qū)域越大，查詢的數(shù)據(jù)集越多，從而處理的時間越長.實驗中觀察到 ，BestTD 算 法 要 優(yōu) 于 NaiveDGTP 算 法 . 對 于NaiveDGTP 算法來說，它沒有任何修剪策略來減小搜索空間，而是使用整個數(shù)據(jù)空間來計算最佳團(tuán)體旅行，導(dǎo)致處理時間長；而BestTD 算法采用了橢圓屬性細(xì)化搜索空間，所以其查詢處理時間要遠(yuǎn)遠(yuǎn)低于NaiveDGTP算法.

圖8 橢圓主軸大小的影響Fig.8 Impact of ellipse major axis

7 結(jié)語

本文研究了基于時間感知的動態(tài)組旅行規(guī)劃查詢問題（TDGTP）.為快速定位到組成員需求的興趣點，構(gòu)建了一個綜合索引結(jié)構(gòu)TIR-Tree 并提出相關(guān)的關(guān)鍵詞查詢KMA 算法.此外，提出了一種基于橢圓剪枝方法（ESRA），細(xì)化搜索空間為橢圓交集區(qū)域.提出一種基于KMA 和ESRA 的查詢處理算法BestTD 來分析評估 TDGTP 問題 .通過對 BestTD 與NaiveDGTP 算法在真實路網(wǎng)合成的數(shù)據(jù)集上進(jìn)行對比，證明本文所提方法是高效可行的.