交通道路網(wǎng)中時(shí)間感知的空間關(guān)鍵詞查詢

游青華，李艷紅*，黃金亮，盧航，羅昌銀

(1中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074；2 華中師范大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430079)

隨著移動(dòng)網(wǎng)絡(luò)和地理定位技術(shù)的迅速發(fā)展，基于位置的服務(wù)被廣泛地運(yùn)用于日常生活中，擁有位置-文本信息的網(wǎng)絡(luò)數(shù)據(jù)對(duì)象的數(shù)據(jù)量也隨之呈爆發(fā)式增長(zhǎng)，因此空間關(guān)鍵詞查詢的研究引起了研究者及工業(yè)界的廣泛關(guān)注.空間關(guān)鍵詞查詢以一個(gè)地理位置和若干個(gè)關(guān)鍵詞作為輸入?yún)?shù)，以若干個(gè)空間相似度和文本相似度最高的數(shù)據(jù)對(duì)象作為結(jié)果返回.但僅考慮空間相似度和文本相似度的空間關(guān)鍵詞查詢有時(shí)無(wú)法滿足用戶的特殊需求，例如，對(duì)于一名在某個(gè)陌生城市旅游的游客，他會(huì)根據(jù)一些公共場(chǎng)所的開放時(shí)間來(lái)安排自己的旅程.如果只根據(jù)空間相似度和文本相似度來(lái)查詢景點(diǎn)，查詢的結(jié)果就不能幫助該游客做出合理的旅游安排.為了解決這類需求，可以在空間關(guān)鍵詞查詢中考慮時(shí)間信息.為了更符合實(shí)際的應(yīng)用場(chǎng)景，本文考慮在路網(wǎng)下對(duì)這一問(wèn)題進(jìn)行研究，搜索路網(wǎng)中與用戶提出的查詢要求最為相似的k個(gè)對(duì)象.為了解決該問(wèn)題，本文提出了一種能夠同時(shí)使用時(shí)間、空間和文本信息對(duì)搜索空間進(jìn)行剪枝的策略來(lái)削減搜索空間的規(guī)模.同時(shí)基于這種剪枝策略，本文提出了一種新的索引結(jié)構(gòu)----TK，用于索引道路網(wǎng)中的數(shù)據(jù)對(duì)象信息.在TK索引下，本文設(shè)計(jì)了相應(yīng)的查詢算法來(lái)處理路網(wǎng)中時(shí)間感知的空間關(guān)鍵詞查詢.

1 相關(guān)工作

目前，許多文獻(xiàn)對(duì)空間關(guān)鍵詞查詢進(jìn)行了研究，例如文獻(xiàn)[1-3].然而，這些文獻(xiàn)里空間關(guān)鍵詞查詢中僅考慮數(shù)據(jù)對(duì)象的空間、文本維度，忽略了數(shù)據(jù)對(duì)象中包含的時(shí)間屬性，而時(shí)間信息在空間關(guān)鍵詞查詢搜索中也起著十分重要的作用.近幾年，關(guān)于基于時(shí)間的空間關(guān)鍵詞查詢的研究也不斷涌現(xiàn)，例如，文獻(xiàn)[4]中研究的是基于時(shí)間的空間關(guān)鍵詞發(fā)布訂閱的問(wèn)題，其中，CHEN等人提出了條件影響域(CIR)的概念來(lái)表示時(shí)間感知的空間關(guān)鍵詞訂閱查詢(TaSk)，同時(shí)利用CIR設(shè)計(jì)過(guò)濾條件將多個(gè)TaSK查詢進(jìn)行分組處理，從而提高查詢的速度.但該文獻(xiàn)中處理時(shí)間的模型是針對(duì)時(shí)間戳類型的，無(wú)法處理時(shí)間區(qū)間這種形式.文獻(xiàn)[5]研究了時(shí)間感知的空間關(guān)鍵詞覆蓋查詢處理問(wèn)題，并提出了TR-tree索引結(jié)構(gòu)和有效的剪枝策略來(lái)快速地處理該類查詢，但這篇文獻(xiàn)是在歐式空間下研究的，無(wú)法解決復(fù)雜路網(wǎng)中時(shí)間感知的空間關(guān)鍵詞查詢問(wèn)題.文獻(xiàn)[6-7]研究了路網(wǎng)中基于時(shí)間的空間關(guān)鍵詞查詢問(wèn)題，并提出TG索引結(jié)構(gòu)來(lái)索引路網(wǎng)中的信息.然而這種索引在索引路網(wǎng)信息時(shí)存在冗余，且在查詢處理過(guò)程中需要對(duì)整個(gè)搜索空間進(jìn)行查找，影響了查詢處理的效率.因此，本文設(shè)計(jì)了一種新的索引結(jié)構(gòu)----TK來(lái)解決存儲(chǔ)冗余，并基于該索引結(jié)構(gòu)設(shè)計(jì)相應(yīng)的算法提前結(jié)束查詢處理，以避免對(duì)整個(gè)搜索空間的探尋.

2 問(wèn)題定義

表1列出的是本文中出現(xiàn)的符號(hào)及其定義.

表1 符號(hào)與定義

2.1 興趣點(diǎn)

假設(shè)路網(wǎng)G的邊e∈E有一組時(shí)空文本對(duì)象o∈O，每一個(gè)對(duì)象o具有3個(gè)屬性：o.loc，o.doc，o.t，其中o.loc表示對(duì)象o的位置，對(duì)象o到它所在邊(vi，vj)的兩端點(diǎn)之間的網(wǎng)絡(luò)距離可以分別表示為|vi，o|和|o，vj|，而對(duì)象oi與oj之間的路網(wǎng)距離是通過(guò)路網(wǎng)上oi與oj之間最短路徑的長(zhǎng)度來(lái)表示的.o.doc是一組用來(lái)描述對(duì)象o的關(guān)鍵詞集合(例如，sunshine store)，o.doc的形式化定義為o.doc={(o.key1，f1)，(o.key2，f2)，…，(o.keyn，fn)}，其中fi是o.keyi在對(duì)象o的描述中出現(xiàn)的頻率.o.t表示對(duì)象o的有效時(shí)間(例如，Sunshine store 的開放時(shí)間為9∶00～19∶00)，可以形式化定義為o.t=(o.st，o.et)，路網(wǎng)對(duì)象的信息如表2所示.

表2 路網(wǎng)中對(duì)象信息

2.2 時(shí)間感知的空間關(guān)鍵詞查詢

定義2綜合評(píng)分函數(shù)rank(q，o).對(duì)于查詢q和對(duì)象o，評(píng)分函數(shù)rank(q，o)計(jì)算并返回綜合考慮o相對(duì)q的位置鄰近度、文本相似度和時(shí)間重疊率的評(píng)分，具體如下：

rank(q,o)=α·Tsim(o.doc,q.doc)+β·Dsim(o.loc,q.loc)+(1-α-β)·Tolap(o.t,q.t),

(1)

其中，Tsim(o.doc,q.doc)是o和q之間的文本相似度，Dsim(o.loc,q.loc)是o與q之間的位置鄰近度，Tolap(o.t，q.t)是查詢時(shí)間與對(duì)象o的有效時(shí)間的重疊率.α，β∈(0，1)表示用戶的偏好參數(shù)，用于調(diào)整文本相似度、位置鄰近度和時(shí)間重疊率在評(píng)分函數(shù)中的權(quán)重.

定義3文本相似度.對(duì)象o∈O與查詢q之間的文本相似度可以通過(guò)一個(gè)文本相似性度量函數(shù)來(lái)計(jì)算，本文是采用cosine相似性[9]來(lái)計(jì)算q.doc和o.doc之間的文本相似度，其定義如下：

Tsim(o.doc,q.doc)=

(2)

定義4位置鄰近度.位置鄰近度描述的是查詢q到對(duì)象o∈O之間路網(wǎng)距離的鄰近度，其定義如下：

(3)

其中，ds(q.loc，o.loc)為查詢q.loc與o.loc之間的最短網(wǎng)絡(luò)距離，dmax表示路網(wǎng)中任意兩點(diǎn)之間的最大網(wǎng)絡(luò)距離.

定義5時(shí)間重疊率.時(shí)間重疊率是通過(guò)查詢時(shí)間與路網(wǎng)中對(duì)象的有效時(shí)間的交集來(lái)計(jì)算的，其定義如下：

Tolap(o.t,q.t)=

(4)

其中，o.st表示o的有效時(shí)間的起始時(shí)間；q.et表示查詢時(shí)間的結(jié)束時(shí)間；tw表示用戶可以忍受的等待時(shí)間.如第一種情況所示，當(dāng)查詢q的查詢時(shí)間q.t與o.t之間存在交集，即|q.t∩o.t|≠0時(shí)，對(duì)象o與查詢q之間的時(shí)間相關(guān)性為正相關(guān)；如第二種情況所示，當(dāng)查詢的結(jié)束時(shí)間大于對(duì)象o的起始時(shí)間，且對(duì)象的起始時(shí)間與查詢的結(jié)束時(shí)間的時(shí)間差值小于用戶可以忍受的等待時(shí)間，即|o.st-q.et|≤tw時(shí)，對(duì)象o與查詢q之間的時(shí)間相關(guān)性為負(fù)相關(guān)；其他情況，即當(dāng)o.ettw時(shí)，對(duì)象o與查詢q之間的相關(guān)性為-∞.

3 路網(wǎng)中TK索引結(jié)構(gòu)

3.1 路網(wǎng)的劃分

為了使提出的查詢處理方法具有更好的擴(kuò)展性，采用kd-tree方法[12]自適應(yīng)地劃分路網(wǎng).通過(guò)水平方向和垂直方向?qū)⒙肪W(wǎng)劃分成若干個(gè)單元格，使得每個(gè)單元格中數(shù)據(jù)對(duì)象的數(shù)量大致相等.路網(wǎng)的劃分如圖1所示，這里采用的是豎直方向優(yōu)先的劃分方式.首先，令垂直線x=x1將路網(wǎng)劃分成兩部分，使得左邊子網(wǎng)中包含的點(diǎn)有{o1，o2，o3}，右邊子網(wǎng)包含的點(diǎn)有{o4，o5，o6，o7}.接著，令水平直線y=y1將左邊子網(wǎng)劃分成兩部分，使得每部分中數(shù)據(jù)點(diǎn)的數(shù)量大致相等，再對(duì)右邊子網(wǎng)進(jìn)行相同的操作.重復(fù)上述劃分步驟，直到每一個(gè)子網(wǎng)中包含的數(shù)據(jù)點(diǎn)的數(shù)量不超過(guò)預(yù)設(shè)的閾值λ.在劃分過(guò)程中設(shè)置λ=1.劃分結(jié)束后，使用標(biāo)識(shí)符R1，R2，R3，…，R7對(duì)每個(gè)子網(wǎng)進(jìn)行標(biāo)識(shí).

圖1 基于kd-tree方式劃分路網(wǎng)

3.2 距離矩陣

TK索引結(jié)構(gòu)采用的距離矩陣是一個(gè)n×n的二維矩陣Dn×n，其中n是路網(wǎng)中劃分后的區(qū)域總數(shù)，Dn×n中的每一項(xiàng)存儲(chǔ)的是區(qū)域Ri與其他任何區(qū)間之間的最小網(wǎng)絡(luò)距離dNmin(Ri，Rj)和最大網(wǎng)絡(luò)距離dNmax(Ri，Rj).為了得到二維矩陣Dn×n，需要先求出不同區(qū)域的所有邊結(jié)點(diǎn)對(duì)之間的最短路徑距離和每個(gè)區(qū)域中兩個(gè)結(jié)點(diǎn)之間的最長(zhǎng)路徑長(zhǎng)度.路徑長(zhǎng)度的計(jì)算可以采用單源最短路徑算法來(lái)計(jì)算，例如Dijsktra算法[13].計(jì)算dNmin(Ri，Rj)時(shí)，從kd-tree區(qū)域Ri中的一個(gè)邊頂點(diǎn)開始，擴(kuò)展到其他區(qū)域Rj中的邊結(jié)點(diǎn)，并選擇兩個(gè)區(qū)域中最鄰近的兩個(gè)邊頂點(diǎn)之間的距離值作為dNmin(Ri，Rj).在計(jì)算dNmax(Ri，Rj)時(shí)，首先計(jì)算出每個(gè)區(qū)域Ri(Rj)中結(jié)點(diǎn)之間的最大距離即Ri的區(qū)域直徑，則dNmin(Ri，Rj)、節(jié)點(diǎn)Ri的區(qū)域直徑以及節(jié)點(diǎn)Rj區(qū)域直徑之和是dNmax(Ri，Rj).

3.3 TK索引

路網(wǎng)劃分結(jié)束后，以自底而上的方式構(gòu)建TK索引.TK索引包含兩個(gè)部分：(1)改進(jìn)的kd-tree，其葉子節(jié)點(diǎn)可以表示為(Ri，L(Ri)，IU(Ri)，TU(Ri)，Pd(Ri))，其中Ri是區(qū)域的標(biāo)識(shí)符；L(Ri)是區(qū)域Ri中所有對(duì)象的標(biāo)識(shí)符的集合；IU(Ri)是區(qū)域Ri中對(duì)象的文本信息的交集和并集，TU(Ri)是L(Ri)中所有對(duì)象的有效時(shí)間的并集，是一組時(shí)間區(qū)間集合；Pd(Ri)是區(qū)域Ri指向距離矩陣中對(duì)應(yīng)的子項(xiàng)的指針.其非葉子節(jié)點(diǎn)可以表示為((xi||yi)，IU(xi||yi)，TU(xi||yi)，Pc(xi||yi))，其中xi或者yi是劃分平面，IU(xi||yi)是xi或者yi劃分區(qū)域中所有對(duì)象的文本信息的交集和并集，TU(xi||yi)是xi或者yi劃分區(qū)域中所有對(duì)象的有效時(shí)間的并集，Pc(xi||yi)是xi或者yi劃分的區(qū)域中指向(劃分后)子區(qū)域的指針；(2)距離矩陣，存儲(chǔ)了各個(gè)區(qū)域之間的最小網(wǎng)絡(luò)距離和最大網(wǎng)絡(luò)距離.圖2是根據(jù)圖1中路網(wǎng)構(gòu)建的TK索引結(jié)構(gòu)圖，表3是IU(*)中文本信息的交集和并集的集合信息表，每一項(xiàng)(II(ki)，UI(ki))表示劃分區(qū)域的文本信息的交集和并集，其中II(ki)，UI(ki)分別表示某個(gè)區(qū)域中關(guān)鍵詞ki的交集和并集.

圖2 TK索引結(jié)構(gòu)

表3 TK非葉子節(jié)點(diǎn)文本信息交并集合

3.4 基于TK索引的查詢搜索

引理2已知一個(gè)TSKQ查詢q=(q.loc，q.doc，

q.t，q.k)和一個(gè)區(qū)域Ri，如果|q.t∩Ri.t|=0且|Ri.st-q.et|>tw時(shí)，則區(qū)域Ri可以被安全地削減.

引理3已知TSQK查詢q=(q.loc，q.doc，q.t，q.k)和區(qū)域Ri，如果rankmax(Ri，q)dsmin(Ri，Rq)，則區(qū)域Rj也可以被安全地削減.

引理4已知TSQK查詢q=(q.loc，q.doc，q.t，q.k)和有序候選對(duì)象集合Ocand，假設(shè)rankmax(oi，q)

算法1給出了路網(wǎng)下時(shí)間感知的空間關(guān)鍵詞查詢處理過(guò)程.其中，集合Ocand用于存放滿足篩選條件的候選對(duì)象，集合LR用于存儲(chǔ)整個(gè)路網(wǎng)的各區(qū)域.rank(ok-th，q)是結(jié)果集中第k個(gè)對(duì)象的評(píng)分，先將其初始化為-∞.該算法分如下兩個(gè)階段來(lái)實(shí)現(xiàn).

輸入:路網(wǎng)下圖G中關(guān)于數(shù)據(jù)集O的TK-tree,TSKQ查詢q=(q.loc,q.doc,q.t,q.k)輸出:q的查詢結(jié)果集合Sr//階段1:對(duì)整個(gè)搜索空間使用篩選條件進(jìn)行過(guò)濾,得到候選區(qū)域及候選對(duì)象1 Ocand=?;rank(ok-th,q)=-∞;Sr=?;LR=?;2 定位到查詢q所在的區(qū)域Rq,并將除Rq以外的其他區(qū)域Ri(1≤i≤n)根據(jù)dNmin(Ri,Rq)從小到大排列在有序列表LR中;3 foreachobjecto∈Rqdo4 ifrank(o,q)>rank(ok-th,q)then5 根據(jù)rank(o,q)將對(duì)象o(o,rank(o,q))從大到小插入到Ocand;6 rank(ok-th,q)←Ocand中評(píng)分最小的第k個(gè)對(duì)象的rank(ok-th,q);7 foreachregionRiinLRdo8 ifrank(Ri,q)=-∞then9 continue;10 ifrankmax(Ri,q)=1-βdsmin(Ri,Rq)dmaxrank(ok-th,q) then15 根據(jù)rankmax(o,q)將對(duì)象o(o,rankmax(o,q))從大到小插入到Ocand;16 rank(ok-th,q)=min(rankmax(ok-th,q));//階段2:對(duì)候選對(duì)象集中的對(duì)象進(jìn)行檢索得到top-k個(gè)對(duì)象作為最終的結(jié)果返回17 whileOcand≠?do18 (oc,rankmax(oc,q))←Ocand.dequeue();//Oc為Ocand中當(dāng)前出隊(duì)的對(duì)象19 計(jì)算rank(oc,q);20 if|Sr|≤kthen21 將對(duì)象oc及rank(oc,q)按照rank(oc,q)的值從大到小的順序插入到Sr中;22 elseifrankmax(oc,q)

4 對(duì)比實(shí)驗(yàn)

下文以基于TG索引結(jié)構(gòu)的算法TIG作為對(duì)照算法，通過(guò)一系列對(duì)比實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的基于TK索引的TIK算法的性能.

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用了兩個(gè)合成的數(shù)據(jù)集CA和SF，CA是通過(guò)真實(shí)的、美國(guó)加利福利亞州的路網(wǎng)數(shù)據(jù)與實(shí)驗(yàn)系統(tǒng)隨機(jī)產(chǎn)生的數(shù)據(jù)對(duì)象合成的，其中，隨機(jī)產(chǎn)生的每個(gè)對(duì)象包含關(guān)鍵詞信息、有效時(shí)間信息和位置信息；SF是由美國(guó)舊金山灣的真實(shí)的路網(wǎng)數(shù)據(jù)與實(shí)驗(yàn)系統(tǒng)隨機(jī)產(chǎn)生的對(duì)象合成的.CA包含1458個(gè)數(shù)據(jù)對(duì)象和46個(gè)關(guān)鍵詞，SF包含10000個(gè)數(shù)據(jù)對(duì)象和215個(gè)關(guān)鍵詞.對(duì)于CA中的每一個(gè)對(duì)象，通過(guò)Zipf分布[14]為其分配2-4個(gè)關(guān)鍵詞，每個(gè)對(duì)象的有效時(shí)間范圍設(shè)置在[1-24]，且遵循高斯分布[15]；對(duì)于SF中的每一個(gè)對(duì)象同樣采用Zipf分布的方式為其設(shè)置3個(gè)關(guān)鍵詞，SF與CA中對(duì)象的時(shí)間信息的設(shè)置方式相同.注意，每個(gè)對(duì)象的位置都隨機(jī)地分布在路網(wǎng)的邊上.由于以上數(shù)據(jù)集是根據(jù)數(shù)據(jù)對(duì)象的時(shí)間特征和關(guān)鍵詞特征進(jìn)行合成的，因此對(duì)實(shí)驗(yàn)結(jié)果沒(méi)有影響.表4描述的是兩個(gè)數(shù)據(jù)集的特征，表5是實(shí)驗(yàn)參數(shù)的設(shè)置.

表4 實(shí)驗(yàn)數(shù)據(jù)集特點(diǎn)

表5 參數(shù)設(shè)置

實(shí)驗(yàn)設(shè)備為AMD Radeon，Intel Core i5-4210U，2.40 GHz CPU，8.00GB RAM Windows 10 的電腦，所有算法是在Java 1.8.0_191的運(yùn)行環(huán)境下完成的.

4.2 實(shí)驗(yàn)結(jié)果

(1)k值的影響.首先研究查詢返回的對(duì)象數(shù)(k值)對(duì)算法的影響.由圖3可以看出，隨著k值的增加，兩種算法在兩個(gè)數(shù)據(jù)集上的查詢性能都比較穩(wěn)定；總體而言，TIK算法的查詢處理速度比TIG算法要快一些，這是因?yàn)門IK算法是通過(guò)時(shí)間、空間和文本信息同時(shí)對(duì)搜索空間進(jìn)行削減，而TIG采用的是時(shí)間和文本信息分開的剪枝策略.

(a)CA (b)SF

(2)查詢關(guān)鍵詞的影響.從圖4可以看出，隨著查詢關(guān)鍵詞的增加，兩種算法在兩個(gè)數(shù)據(jù)集上的查詢處理時(shí)間也隨之增加.這是因?yàn)殡S著查詢關(guān)鍵詞個(gè)數(shù)的增多，查詢的搜索空間變大，且查詢待處理的對(duì)象的規(guī)模也變大.但是，從圖4可以看到，TIK的查詢性能仍然優(yōu)于TIG.

(a) CA (b) SF

(3)偏好參數(shù)的影響.

1)α的影響.如圖5(a)所示，在CA和SF數(shù)據(jù)集上，TIG算法查詢時(shí)間會(huì)隨α的增大而增大，增大幅度略大，而在CA上TIK算法代價(jià)隨著α增大也會(huì)慢慢地增長(zhǎng)，增長(zhǎng)幅度相對(duì)于TIG要小一些；

2)β的影響.從圖5(b)可以看出，兩種算法查詢時(shí)間是隨著β增大而減小，這是因?yàn)楫?dāng)β增大時(shí)，位置臨近度權(quán)重加大，更多離查詢點(diǎn)遠(yuǎn)的區(qū)域或?qū)ο蟊幌鳒p掉.因此，β對(duì)兩種算法的影響相似；

(a)α 值的影響 (b)β 值的影響

3)1-α-β的影響.此處效果圖(省略)類似于圖3.兩種算法在兩個(gè)數(shù)據(jù)集上的查詢性能是比較穩(wěn)定的，其查詢時(shí)間并不會(huì)隨著1-α-β的增大而增加.總體而言，TIK算法查詢性能優(yōu)于TIG算法.

(4)查詢時(shí)間長(zhǎng)度的影響.此處效果圖(省略)類似于圖3中的兩幅圖.在CA上，隨著查詢時(shí)間長(zhǎng)度增大，TIG查詢時(shí)間也在緩慢地增加，而TIK查詢時(shí)間較TIG來(lái)說(shuō)比較平穩(wěn).在SF上，隨著時(shí)間的增長(zhǎng)，兩種算法查詢時(shí)間都比較穩(wěn)定，但圖中TIK算法查詢性能優(yōu)于TIG算法.

5 總結(jié)

本文研究了道路網(wǎng)中時(shí)間感知的空間關(guān)鍵詞查詢問(wèn)題.為了便于該類查詢的處理，設(shè)計(jì)了相應(yīng)的索引結(jié)構(gòu)——TK來(lái)組織路網(wǎng)中的信息.TK包括兩部分：一個(gè)是改進(jìn)的kd-tree，另一個(gè)是一個(gè)路網(wǎng)中的距離矩陣.基于TK索引結(jié)構(gòu)，設(shè)計(jì)了可以同時(shí)使用文本、空間和時(shí)間信息對(duì)搜索空間進(jìn)行削減的剪枝策略，并設(shè)計(jì)了相應(yīng)的TIK查詢處理算法.最后，采用兩個(gè)真實(shí)路網(wǎng)的合成數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集，通過(guò)TIK與TIG算法的一系列對(duì)比實(shí)驗(yàn)，證明了所提出方法的可行性與高效性.