孫一格 馬 昂 吳 雷, 潘 曉 郭景峰(石家莊鐵道大學(xué)經(jīng)濟(jì)管理學(xué)院 河北 石家莊 05004)(河北省高校人文社會科學(xué)重點(diǎn)研究基地(石家莊鐵道大學(xué)) 河北 石家莊 05004)(燕山大學(xué)信息科學(xué)與工程學(xué)院 河北 秦皇島 066004)

0 引 言

智慧旅游是隨著云計(jì)算、下一代通信、數(shù)據(jù)挖掘等技術(shù)發(fā)展起來的一種新型旅游形態(tài)。其以移動終端應(yīng)用為核心，實(shí)現(xiàn)用戶和互聯(lián)網(wǎng)的實(shí)時(shí)交互，使旅行安排更加個(gè)性化，并且便捷、高效，從而具有很大的研究價(jià)值。手機(jī)等各種電子移動設(shè)備以及GPS定位系統(tǒng)的發(fā)展，使得人們出行的地理位置信息很容易獲取[1-3]。一方面，出行者在外出過程中停留形成的空間點(diǎn)連接起來形成了具有時(shí)空信息的軌跡；另一方面，伴隨社交媒體應(yīng)用的流行普及，例如，微博、微信等應(yīng)用，地理位置與文本數(shù)據(jù)的融合變得非常普遍。軌跡中蘊(yùn)含的豐富語義信息，如道路狀況、天氣條件、鄰近朋友等為智慧旅游中越來越多應(yīng)用和研究提供了助力。例如，在旅游系統(tǒng)中，用戶除了記錄自己的位置信息以外，還包括感興趣點(diǎn)類型、地理環(huán)境、用戶評價(jià)、圖片、視頻等數(shù)據(jù)。通過將軌跡中的時(shí)空信息與文本數(shù)據(jù)融合可以得到帶有語義標(biāo)簽的軌跡，被稱為語義軌跡[5-6]。例如用戶A在a點(diǎn)購物，在b點(diǎn)住宿，那么購物、住宿等活動就是與空間點(diǎn)相對應(yīng)的語義信息。由于軌跡的數(shù)量是相當(dāng)龐大的，如何有效地對海量軌跡進(jìn)行查詢，獲取最能滿足客戶需求的軌跡具有重要的應(yīng)用價(jià)值。

在軌跡數(shù)據(jù)上進(jìn)行查詢處理已有大量的研究工作[4-16]。然而，現(xiàn)有大部分工作僅考慮軌跡上的時(shí)空信息，忽略了軌跡上的語義信息。例如，某驢友希望從歷史旅游軌跡線路中尋找滿足一定要求的軌跡作參考。倘若只考慮地理位置的因素，則可以通過布爾查詢[11]、skyline查詢[14]或最近鄰kNN[15]查詢等得到合適的匹配路線。然而，現(xiàn)實(shí)中很多情況下用戶不僅對地理位置有要求，同時(shí)對語義也有要求。如驢友期望在自己預(yù)設(shè)的地點(diǎn)附近進(jìn)行餐飲、參觀和購物等需求。以圖1為例，用戶想在q1點(diǎn)附近進(jìn)行{a,c}兩項(xiàng)活動，在q2點(diǎn)附近進(jìn)行{e}活動。Tr1、Tr2、Tr3是系統(tǒng)中的原有的旅行軌跡，當(dāng)用戶向系統(tǒng)輸入他想進(jìn)行的活動及地點(diǎn)后，系統(tǒng)應(yīng)返回包含用戶所需要的全部活動{a,c,e}且從空間位置上距離查詢點(diǎn)最近的k條軌跡，即語義軌跡的kNN查詢。表1給出查詢點(diǎn)到軌跡點(diǎn)的距離。

表1 示例中Tr1、Tr2軌跡點(diǎn)到查詢點(diǎn)的距離

本文正是針對智慧旅游中語義軌跡上的k最近鄰查詢問題進(jìn)行研究?；赗-tree融合位置上的文本信息提出了ITS-tree索引結(jié)構(gòu)(包括IT-tree和S-樹兩個(gè)部分)，索引了原始軌跡特征點(diǎn)的空間信息和語義信息，可同時(shí)從空間和文本兩個(gè)方面對軌跡進(jìn)行剪枝。利用最小最佳優(yōu)先原則，首先遍歷IT-tree，從原始的語義軌跡中先獲取候選軌跡集，然后對候選軌跡利用S-樹進(jìn)行軌跡結(jié)果的求精。

1 相關(guān)工作

現(xiàn)有在軌跡數(shù)據(jù)上的查詢工作，按照查詢點(diǎn)的個(gè)數(shù)的不同可分為兩類：一類是單點(diǎn)查詢，即查詢滿足用戶當(dāng)前位置和語義需求的軌跡數(shù)據(jù)；另一類是多點(diǎn)查詢，即查詢中包括的位置可以是一個(gè)點(diǎn)集合，語義可以是用于描述整條軌跡亦可以是描述每一個(gè)位置采樣點(diǎn)的關(guān)鍵字集合。文獻(xiàn)[11]給定用戶查詢位置和語義集合，返回包含用戶語義并且匹配距離最短的k條軌跡。文獻(xiàn)[6]提出的近似關(guān)鍵字查詢 AKQST與傳統(tǒng)空間語義查詢不同，在查詢集合中僅指定語義集合，但并沒有涉及位置信息。該方法返回k條包含最相關(guān)語義且旅行代價(jià)最小的k條子軌跡。文獻(xiàn)[7]中，每一條軌跡上帶有一個(gè)文本關(guān)鍵字集合，提出了面向用戶的軌跡查詢UOTS。該方法返回距離查詢點(diǎn)最近的軌跡，并且查詢點(diǎn)的集合可以是有序序列，也可以是無序序列。文獻(xiàn)[16]在位置空間、語義信息的基礎(chǔ)上，增加了一個(gè)衡量標(biāo)準(zhǔn)即打分信息。在用戶給定起點(diǎn)、終點(diǎn)以及語義信息下，該方法返回包含查詢中所有語義信息、以及軌跡長度滿足距離要求并且評分最高的軌跡段。文獻(xiàn)[5]提出一種GAT新型網(wǎng)格索引結(jié)構(gòu)，以層次的方式組織軌跡片段及其活動信息。利用best-first搜索框架，通過空間鄰近和活動遏制同時(shí)修剪大量不合格的軌跡，有效地處理了空間文本查詢。但由于為每一個(gè)語義構(gòu)建一棵樹，當(dāng)需查詢的語義較多時(shí)，會導(dǎo)致對HICL進(jìn)行多次遍歷，查詢代價(jià)較高。

2 問題的形式化描述

方便起見，本文將游客在某地點(diǎn)上進(jìn)行的活動，如住宿、餐飲、購物等，作為該位置的語義信息，其全集用A表示，小寫字母表示語義實(shí)例。語義軌跡是一系列被賦予活動語義的點(diǎn)序列，用Tr表示，軌跡上的點(diǎn)用p來表示，即Tr={p1，p2，p3，…}，軌跡上的點(diǎn)p同時(shí)具有位置和語義兩方面信息，形式化的表示為pi=(x,y,φ)，其中φ={x|x∈A}表示該點(diǎn)附著的語義信息。用戶輸入的查詢點(diǎn)集用Q{q1，q2，q3，…}表示，其中每一個(gè)查詢點(diǎn)亦是語義位置點(diǎn)。

定義1(點(diǎn)匹配[5]) 給定某一查詢點(diǎn)q，若軌跡上點(diǎn)子集的語義組成的并集是查詢點(diǎn)語義集的超集，即q.φ?∪pi∈Trpi.φ，則稱該點(diǎn)集是查詢點(diǎn)q到軌跡Tr的點(diǎn)匹配，用pm表示。

很明顯，針對某一個(gè)查詢，軌跡上的點(diǎn)匹配存在多個(gè)。

繼續(xù)圖1的例子，{p1,1,p1,2}、{p1,2,p1,3}、{p1,1,p1,2,p1,3}等都是查詢點(diǎn)q1到軌跡Tr1的點(diǎn)匹配，其點(diǎn)匹配距離分別為3.2、5.0、6.0，最短點(diǎn)匹配距離為D(p1,1,q1)+D(p1,2,q1)=3.2。

本文的查詢是點(diǎn)集合。因此，軌跡匹配距離定義與文獻(xiàn)[5]相同。

從定義3可以看出，軌跡匹配距離是所有查詢點(diǎn)到該軌跡的任意一個(gè)點(diǎn)匹配距離的和。軌跡的最短匹配距離是所有匹配距離中的最小值。例如，針對Q={q1,q2}來說，軌跡Tr1的軌跡匹配距離為Dpm(q1,Tr1)+Dpm(q2,Tr1)。Tr1的最短軌跡匹配距離Dmm(Q,Tr1)為Dmpm(q1,Tr1) +Dmpm(q2,Tr1) =3.2+4.8=8.0。

本文的目標(biāo)即從語義軌跡集合D中，根據(jù)查詢點(diǎn)集合Q，尋找包含Q中所有關(guān)鍵字集合并且軌跡匹配距離最小的k條軌跡。具體來講，查詢結(jié)果需要滿足空間與語義兩方面要求：從語義的角度講，查詢結(jié)果中的點(diǎn)集合應(yīng)包含所有查詢點(diǎn)語義，示例中查詢點(diǎn)語義集合是{a,c,e},則軌跡Tr2、Tr3不會出現(xiàn)在結(jié)果集中；從空間的角度講，查詢點(diǎn)到軌跡的軌跡匹配距離最短，以滿足空間上軌跡興趣點(diǎn)接近預(yù)設(shè)地點(diǎn)的要求。

3 ITS-樹索引結(jié)構(gòu)

為提高查詢效率，本文提出了一個(gè)新的ITS-tree (即IT-tree+S-tree)索引結(jié)構(gòu)。該索引結(jié)構(gòu)分為兩部分：(1) IT-tree，索引空間中的語義軌跡，融合了軌跡的空間信息、語義信息以及軌跡標(biāo)識，便于查找候選軌跡集。(2) S-tree查找樹，以語義詞頻為標(biāo)準(zhǔn)為軌跡標(biāo)識號建立分段樹，便于確定軌跡是否包含查詢中的全部語義。

IT-tree：在R-tree的基礎(chǔ)上融合了關(guān)鍵字到軌跡的倒排信息。為提高查找速率，在IT-tree中存儲的是所有語義在整個(gè)數(shù)據(jù)庫的詞頻，方便對語義進(jìn)行比較和剪枝。在軌跡的所有點(diǎn)上建立R-tree，在葉子結(jié)點(diǎn)上建立詞頻到軌跡標(biāo)識的倒排表，在中間結(jié)點(diǎn)上存儲詞頻區(qū)間。具體來講，葉子結(jié)點(diǎn)中的倒排表以該區(qū)域內(nèi)覆蓋的位置點(diǎn)所帶的語義詞頻為關(guān)鍵字，指向一個(gè)軌跡標(biāo)識列表，該列表中存儲的是包含該語義信息的軌跡標(biāo)識。中間結(jié)點(diǎn)存儲該結(jié)點(diǎn)覆蓋語義的降序詞頻區(qū)間，區(qū)間個(gè)數(shù)可由內(nèi)存大小決定[5]。進(jìn)行查詢時(shí)，通過判斷查詢語義的詞頻區(qū)間與結(jié)點(diǎn)詞頻區(qū)間的是否存在交集，對IT-tree的結(jié)點(diǎn)進(jìn)行剪枝(詳見4.1節(jié)方法1)。表2是圖1中的軌跡所帶語義對應(yīng)的詞頻，圖2是這3條軌跡構(gòu)建的IT-tree，圖3是圖2的樹型結(jié)構(gòu)示意圖，圖4示例了葉子結(jié)點(diǎn)N5中存儲的倒排表。

表2 詞頻映射表

圖2 IT-tree構(gòu)建示例

圖3 IT-tree示意圖

圖4 葉子結(jié)點(diǎn)N5存儲的倒排表

S-tree：在IT-tree上進(jìn)行查詢時(shí)，得到的是候選軌跡集。為進(jìn)一步判斷候選軌跡是否包含查詢所需要的全部語義，需要對候選軌跡進(jìn)一步求精，這正是S-tree的作用。S-tree的創(chuàng)建方法如下：通過從高到低排列的語義詞頻將連續(xù)的軌跡id劃分為若干不相交的區(qū)間段，各區(qū)間所攜帶的語義信息用bitmap表來表示。這里假設(shè)軌跡id均是數(shù)字類型，如果軌跡id不是數(shù)字類型可以先將其數(shù)字化。具體劃分方法如下：首先以是否包含最高語義詞頻為標(biāo)準(zhǔn)將軌跡id分為若干區(qū)間。例如，假設(shè)軌跡集包含10條軌跡，軌跡標(biāo)識號為1～10，a為詞頻最高的語義，若Tr1-Tr3、Tr7-Tr10包含語義a，Tr4-Tr6不含語義a，則通過是否包含語義a可將軌跡標(biāo)識號劃分為[1,3], [4,6], [7,10]三個(gè)區(qū)間。接著使用詞頻次高的語義進(jìn)行劃分，與上述過程類似，若次高語義詞頻為b,則用b在由a劃分好的區(qū)間的基礎(chǔ)上再次進(jìn)行劃分，可得含a、b，含a但不含b，不含a但含b以及不含a、b的多個(gè)軌跡段。區(qū)間劃分時(shí)，當(dāng)語義詞頻總和達(dá)到90%時(shí)，劃分停止。為每個(gè)劃分好的區(qū)間建立bitmap表，按區(qū)間劃分時(shí)語義由高到低的次序，每一位置1表示該位代表的語義存在，置0表示該位代表的語義存在，由bitmap表可知軌跡中包含的語義，如圖5所示。所劃分軌跡區(qū)間作為輸入，根據(jù)線段樹建立的方法，建成平衡的二分線段樹，即S-tree。當(dāng)從IT-tree中得到候選軌跡集后，以候選軌跡標(biāo)識作為關(guān)鍵字搜索S-tree，鎖定軌跡id所在葉子結(jié)點(diǎn)區(qū)間。通過查看該區(qū)間的bitmap表，可知該軌跡是否包含全部詞頻在90%以內(nèi)查詢語義。若查詢中包含詞頻小于10%的關(guān)鍵字，則在計(jì)算最短軌跡匹配距離之前查看軌跡活動列表結(jié)構(gòu)，若所有詞頻小于10%的語義均有對應(yīng)點(diǎn)，則進(jìn)行下一步計(jì)算[5]。若候選軌跡包含所有查詢語義則進(jìn)一步計(jì)算查詢點(diǎn)到候選軌跡的最短軌跡匹配距離。詳見4.1節(jié)方法2。

圖5 S-tree示例

4 k最近鄰查詢方法

方法遍歷ITS-tree獲取候選結(jié)果集，并計(jì)算候選結(jié)果集中軌跡的最短軌跡匹配距離。為防止出現(xiàn)查詢結(jié)果遺漏，進(jìn)一步對可能符合要求的軌跡進(jìn)行驗(yàn)證，最終返回含有k條軌跡的結(jié)果集。

4.1 遍歷ITS-tree獲取候選軌跡集

方法利用best-first思想，首先在IT-tree上進(jìn)行遍歷獲取滿足到某一個(gè)查詢點(diǎn)空間位置較近的k條軌跡。具體遍歷方法如下：遍歷過程維護(hù)隊(duì)列seq，seq中的元素以結(jié)點(diǎn)到各查詢點(diǎn)距離的最小值為排序關(guān)鍵字進(jìn)行升序排序。首先將IT-tree的根結(jié)點(diǎn)放入隊(duì)列seq。當(dāng)seq不為空時(shí)，取出隊(duì)頭。判斷是否存在查詢點(diǎn)的語義關(guān)鍵字對應(yīng)的詞頻落入該結(jié)點(diǎn)的語義區(qū)間中，如果沒有則將這個(gè)結(jié)點(diǎn)及其分支過濾，否則，計(jì)算其孩子結(jié)點(diǎn)到各查詢點(diǎn)的空間最短距離，將其孩子結(jié)點(diǎn)按最短距離升序插入隊(duì)列中。當(dāng)隊(duì)頭中取出的是葉子結(jié)點(diǎn)時(shí)，取出具體軌跡放入軌跡集中。持續(xù)進(jìn)行遍歷，直至軌跡集中包含k條軌跡，具體見方法1。

接下來，利用S-tree檢查這k條軌跡是否滿足查詢語義的要求。針對每一條候選軌跡，若其包含查詢要求的所有語義則進(jìn)一步計(jì)算最短匹配距離。具體來講，針對每一條候選軌跡，根據(jù)該軌跡的標(biāo)識存在的葉子結(jié)點(diǎn)bitmap表，根據(jù)查詢Q中的每一個(gè)查詢語義在bitmap中對應(yīng)位置是否為1判斷該軌跡是否包含該語義。若發(fā)現(xiàn)軌跡未包含全部查詢語義，則將該軌跡從軌跡集中刪去。當(dāng)然，該方法無法判斷軌跡是否包含詞頻小于10%的查詢語義，可以遍歷軌跡活動列表，通過軌跡中是否有詞頻小于10%語義的對應(yīng)點(diǎn)進(jìn)行進(jìn)一步判斷。然而，由于這些語義出現(xiàn)的概率較低，并不影響查詢方法的性能。對于滿足語義要求的軌跡計(jì)算最短軌跡匹配距離[5]，并插入候選結(jié)果集。

方法1遍歷IT-tree

1 輸入：IT-tree，seq

2 輸出：軌跡集

3 維護(hù)隊(duì)列seq存儲結(jié)點(diǎn)編號以及結(jié)點(diǎn)到查詢點(diǎn)距離

4 When 遍歷IT-tree

5 Node N=seq.pop()

6 檢查是否有查詢語義詞頻落在結(jié)點(diǎn)N的詞頻區(qū)間

7 if Y，計(jì)算孩子結(jié)點(diǎn)到當(dāng)前查詢點(diǎn)距mD(cni,q)

8 將cni按當(dāng)前查詢點(diǎn)距離的升序插入seq

9 else 刪除N

10 if (cn==null)

11 取出軌跡Tri

12 if (Tri未經(jīng)過求精)

13 將Tri插入軌跡集

14 if (軌跡集軌跡數(shù)+候選集軌跡數(shù)=k)

15 return 軌跡集

若候選結(jié)果集中軌跡數(shù)i

方法2軌跡求精結(jié)果

1 輸入：軌跡集Q，k

2 輸出：top-k Tr

3 用方法1遍歷IT-Tree

4 When 取得軌跡集TR

5 if (所查詢語義均在90%詞頻范圍內(nèi))

6 遍歷TR中Tri的S-tree查看該軌跡是否包含全部查詢語義

7 else 遍歷TR中Tri的S-tree和APL結(jié)構(gòu)確定軌跡包含全部查詢語義

8 if(Tri包含全部查詢語義)

9 計(jì)算該軌跡最短匹配距離Dmm(Q，Tri)

10 將Tri插入候選結(jié)果集CRS，刪除TR中的Tri

11 else 刪除Tri

12 if (CRS軌跡數(shù)i

13 得到候選結(jié)果集CRS

14 驗(yàn)證并更新CRS，得到RS

15 return RS

4.2 候選軌跡求精及得到top-k軌跡

在4.1節(jié)中僅獲得的是距離某一個(gè)查詢點(diǎn)較近軌跡，包含距離一個(gè)查詢點(diǎn)最近鄰的軌跡不一定是距離所有查詢點(diǎn)的距離和最小的軌跡。因此，僅經(jīng)過4.1節(jié)方法計(jì)算獲得的結(jié)果并不能覆蓋全部解。為確保沒有遺漏可行解，本節(jié)對當(dāng)前未出現(xiàn)在候選結(jié)果集，但可能成為查詢結(jié)果的軌跡進(jìn)行進(jìn)一步求證。具體方法如下：以每個(gè)查詢點(diǎn)為圓心，以當(dāng)前候選結(jié)果集中最大的軌跡匹配距離為半徑，在IT-tree上執(zhí)行范圍查詢，查詢獲得的結(jié)果且未在現(xiàn)有候選結(jié)果集中出現(xiàn)的軌跡即是被遺漏的可行解。該可行解進(jìn)行驗(yàn)證，其驗(yàn)證方法是：計(jì)算該軌跡與查詢的最短匹配距離，若該距離小于當(dāng)前結(jié)果集中最大值，則將其依升序插入當(dāng)前結(jié)果集，并刪去結(jié)果集中最后一條軌跡。重復(fù)這個(gè)過程直至最終得到含有top-k條軌跡的結(jié)果集。

5 示例分析

圖2為上文中的實(shí)例，設(shè)置k值為2，原始軌跡集中有Tr1,Tr2,Tr3三條軌跡，有2個(gè)查詢點(diǎn)q1，q2，查詢語義是{a,c,e}，其中q1查詢語義為{a,c}，q2查詢語義為{e}。建立圖3所示IT-tree。

計(jì)算出的IT-tree中各結(jié)點(diǎn)到查詢點(diǎn)的最短距離如表3所示。

表3 計(jì)算得各結(jié)點(diǎn)到查詢點(diǎn)的最短距離

查詢語義為{a,c,e}，其中c語義為語義詞頻小于10%的語義。首先將N1壓入隊(duì)列中，隨后取出隊(duì)列中第一個(gè)結(jié)點(diǎn)N1，所有查詢語義均在N1內(nèi)，得到其三個(gè)子結(jié)點(diǎn)N2,N3,N4。計(jì)算其子結(jié)點(diǎn)到查詢點(diǎn)的距離插入隊(duì)列中，再取頭結(jié)點(diǎn)N2，由于{a,c}語義詞頻落入N2詞頻區(qū)間內(nèi)，取N2孩子結(jié)點(diǎn)計(jì)算距離后插入隊(duì)列中。取隊(duì)頭結(jié)點(diǎn)N5，得到軌跡Tr1，Tr2插入候選軌跡集。此時(shí)候選軌跡數(shù)i=k,返回對軌跡進(jìn)行求精。

遍歷S-tree至葉子結(jié)點(diǎn)可得Tr1的Bitmap表11111，包含語義{a,e}和Tr2的Bitmap表11110，不包含語義e，因此將Tr2刪除。用文獻(xiàn)[5]中計(jì)算Tr1的最短軌跡匹配距離，參照表1可知最短軌跡匹配距離為1.0+2.2+1.5+4.8=9.5，將Tr1插入結(jié)果集中。此時(shí)結(jié)果集中軌跡數(shù)為1，小于k，返回遍歷IT-tree。

取隊(duì)頭結(jié)點(diǎn)N3，語義{a,c,e}的詞頻落入的N3的詞頻區(qū)間，計(jì)算孩子結(jié)點(diǎn)N7、N8到各查詢點(diǎn)的距離插入隊(duì)列中。接著取隊(duì)頭結(jié)點(diǎn)N6，語義a的詞頻落入N6詞頻區(qū)間中，取出軌跡Tr1、Tr2，由于已經(jīng)過遍歷，不對候選結(jié)果集進(jìn)行更新。接下來取隊(duì)頭N7，語義c的詞頻落入N7的詞頻區(qū)間，取出軌跡Tr1，不對軌跡集進(jìn)行更新。取隊(duì)頭N4，語義{a,e}落入其詞頻區(qū)間，取N4的孩子結(jié)點(diǎn)，計(jì)算距離插入隊(duì)列中。如此進(jìn)行下去，可在 取到軌跡Tr3，返回Tr3進(jìn)行驗(yàn)證，在S-tree葉子結(jié)點(diǎn)中3所在區(qū)間可得Bitmap表11111，由軌跡活動列表不含c，將其刪除。由于遍歷結(jié)束，候選結(jié)果集中僅有Tr1。

檢驗(yàn)：以q1、q2為圓心，當(dāng)前結(jié)果集中軌跡Tr1的最短匹配距離8.0為半徑進(jìn)行范圍查詢，檢驗(yàn)從查詢范圍內(nèi)覆蓋的葉子結(jié)點(diǎn)中取得的軌跡是否有未出現(xiàn)在結(jié)果集中的情況。重復(fù)求精過程，對結(jié)果集進(jìn)行更新。由于本例中軌跡數(shù)量較少，因此僅有{Tr1}滿足要求。

本例中只針對每個(gè)查詢點(diǎn)對IT-tree進(jìn)行一次遍歷。若使用文獻(xiàn)[5]工作提供的方法，則要分別針對語義a、c、e對索引結(jié)構(gòu)進(jìn)行多次遍歷，查詢代價(jià)較高。

時(shí)間代價(jià)分析：查詢方法主要分為兩個(gè)部分：第一部分是利用IT-tree和S-tree索引結(jié)構(gòu)找出候選結(jié)果集。假設(shè)查詢點(diǎn)個(gè)數(shù)為|q|，n為軌跡數(shù)據(jù)集中點(diǎn)的個(gè)數(shù)，|D|為語義的值域中值的個(gè)數(shù)，算法的時(shí)間復(fù)雜度為O(|q||D|n2)。第二部分為根據(jù)候選結(jié)果集求解精確匹配距離，在該部分中，我們利用文獻(xiàn)[1]的匹配算法，所以時(shí)間代價(jià)與文獻(xiàn)[1]一致。

本文提出的方法可以進(jìn)一步從下面兩個(gè)問題進(jìn)行提高與改進(jìn)。一是IT-tree是基于軌跡中的離散點(diǎn)來構(gòu)建的，從IT-tree中得到候選軌跡存在重復(fù)計(jì)算的情況。此點(diǎn)增加軌跡訪問數(shù)組visit[]解決。二是雖然S-tree索引結(jié)構(gòu)是基于語義詞頻占總詞頻的前90%的語義構(gòu)建，但S-tree的高度依然是語義信息集合的值域|D|，當(dāng)語義很多時(shí)，S-tree可能過高。此點(diǎn)可利用語義信息的詞頻分布降低S-tree索引結(jié)構(gòu)的樹高，對查詢算法的效率做進(jìn)一步優(yōu)化提升。

6 結(jié) 語

本文針對旅游系統(tǒng)中的kNN語義軌跡查詢問題,介紹了相關(guān)背景及工作，提出ITS-tree索引以期通過改進(jìn)索引結(jié)構(gòu)和方法提高查詢的效率。IT-tree在R-tree索引空間信息的基礎(chǔ)上存儲區(qū)域點(diǎn)的語義信息，并通過葉子結(jié)點(diǎn)中的倒排表獲取候選軌跡；用S-tree結(jié)構(gòu)來檢查軌跡是否滿足語義要求，提高了語義檢查的精確性。在進(jìn)行查詢時(shí)通過同時(shí)考慮查詢點(diǎn)的所有語義，減少查找次數(shù)；使用查詢語義詞頻與中間結(jié)點(diǎn)詞頻區(qū)間是否存在交集，對IT-tree結(jié)點(diǎn)進(jìn)行剪枝，提高查找效率。接下來的工作將進(jìn)一步對索引及方法進(jìn)行優(yōu)化，驗(yàn)證方法的有效性。

[1] 劉曉樂,李博. 隱私保護(hù)下的組最近鄰查詢算法研究[J]. 計(jì)算機(jī)應(yīng)用與軟件,2016,33(5):302- 306.

[2] 林娜,鄭亞男. 基于出租車軌跡數(shù)據(jù)的路徑規(guī)劃方法[J]. 計(jì)算機(jī)應(yīng)用與軟件,2016,33(1):68- 72.

[3] 肖艷麗,張振宇,楊文忠. 基于GPS軌跡的用戶移動行為挖掘算法[J]. 計(jì)算機(jī)應(yīng)用與軟件,2015,32(11):83- 87.

[4] 李萬高. 路網(wǎng)中基于最短路徑的最近鄰查詢算法研究[J]. 計(jì)算機(jī)應(yīng)用與軟件,2014,31(7):59- 61,68.

[5] Zheng K, Shang S, Yuan N J, et al. Towards efficient search for activity trajectories[C]//IEEE International Conference on Data Engineering. IEEE Computer Society, 2013:230- 241.

[6] Zheng B, Yuan N J, Zheng K, et al. Approximate keyword search in semantic trajectory database[C]//IEEE, International Conference on Data Engineering. IEEE, 2015:975- 986.

[7] Shang S, Ding R, Yuan B, et al. User oriented trajectory search for trip recommendation[C]//Proceedings of the 15th International Conference on Extending Database Technology—EDBT ’12. 2012:156- 167.

[8] 李晨, 申德榮, 朱命冬,等. 一種對時(shí)空信息的kNN查詢處理方法[J]. 軟件學(xué)報(bào), 2016, 27(9):2278- 2289.

[9] 丁治明. 一種適合于頻繁位置更新的網(wǎng)絡(luò)受限移動對象軌跡索引[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(7):1448- 1461.

[10] 宋曉宇, 許鴻斐, 孫煥良,等. 基于簽到數(shù)據(jù)的短時(shí)間體驗(yàn)式路線搜索[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(8):1693- 1703.

[11] Gao C, Lu H, Ooi B C, et al. Efficient Spatial Keyword Search in Trajectory Databases[DB]. eprint arXiv:1205.2880, 2012.

[12] Chen Y, Jiang K, Zheng Y, et al. Trajectory simplification method for location-based social networking services[C]//International Workshop on Location Based Social Networks, Lbsn 2009, November 3, 2009, Seattle, Washington, Usa, Proceedings. DBLP, 2009:33- 40.

[13] 趙苗苗. 基于出租車軌跡數(shù)據(jù)挖掘的推薦模型研究[D].北京:首都經(jīng)濟(jì)貿(mào)易大學(xué), 2015.

[14] Aljubayrin S, He Z, Zhang R. Skyline Trips of Multiple POIs Categories[C]//International Conference on Database Systems for Advanced Applications. Springer International Publishing, 2015:189- 206.

[15] Zheng B, Zheng K, Xiao X, et al. Keyword-aware continuous kNN query on road networks[C]//IEEE, International Conference on Data Engineering. IEEE, 2016:871- 882.

[16] Chen W, Zhao L, Xu J J, et al. Trip Oriented Search on Activity Trajectory[J]. Journal of Computer Science & Technology, 2015, 30(4):745- 761.