任佳宇，李艷紅，馮雨

（中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074）

傳統(tǒng)的空間關(guān)鍵詞查詢（SKQ）以一個(gè)地理位置和若干關(guān)鍵詞作為參數(shù)，返回若干個(gè)滿足空間與文本約束、根據(jù)指定公式排列的結(jié)果.SKQ已由歐氏空間擴(kuò)展到了道路網(wǎng)絡(luò)，但現(xiàn)有文獻(xiàn)僅考慮查詢點(diǎn)與空間-文本對(duì)象之間的靜態(tài)距離以確定空間鄰近度，而未考慮現(xiàn)實(shí)生活中用戶從某一時(shí)刻出發(fā)、在一段時(shí)間內(nèi)由查詢點(diǎn)到達(dá)對(duì)象的可能性.

圖1中有3個(gè)對(duì)象o1、o2、o3和一個(gè)查詢點(diǎn)Q.假設(shè)興趣點(diǎn)o1和o2滿足查詢q的關(guān)鍵詞要求，且Q與o1之間的距離小于Q與o2的距離.但在一天中的某些時(shí)刻，由于交通等原因，在給定的時(shí)間間隔內(nèi)從Q到達(dá)o1的可能性小于從Q到達(dá)o2的可能性，那么此時(shí)o1不一定是優(yōu)于o2的選擇.因此將可達(dá)性作為Top-k空間關(guān)鍵詞查詢的一個(gè)因素是很有必要的.

圖1 道路網(wǎng)絡(luò)與空間-文本對(duì)象Fig.1 Road network and spatio-textual objects

為了將可達(dá)性這一因素加入SKQ中，本文提出了一種兼顧可達(dá)性、空間鄰近度和文本相似性的算法，通過(guò)設(shè)計(jì)SRTR-Tree（Spatio-Reachability-Temporal-R-Tree）索引進(jìn)行實(shí)現(xiàn).在查詢過(guò)程中分別根據(jù)可達(dá)性、空間鄰近度和文本相似性進(jìn)行剪枝，以加快查詢速度.

1 相關(guān)工作

1.1 時(shí)空可達(dá)性查詢處理

傳統(tǒng)的可達(dá)性查詢是一種基本的圖操作，查詢一個(gè)有向圖的兩個(gè)節(jié)點(diǎn)之間是否存在路徑.文獻(xiàn)［1-2］構(gòu)造了一個(gè)小而有效的索引解決此類可達(dá)性查詢.文獻(xiàn)［3］用一種圖縮減方法加速可達(dá)性計(jì)算，文獻(xiàn)［4-5］則提出了不同的標(biāo)記方法來(lái)縮減索引大小.

目前可達(dá)性查詢常用于檢測(cè)城市路網(wǎng)中是否存在從一點(diǎn)到另一點(diǎn)的路徑.基于歷史軌跡數(shù)據(jù)集，文獻(xiàn)［6］對(duì)道路進(jìn)行重新分割并將軌跡與地圖匹配，通過(guò)最大邊界區(qū)域搜索和回溯搜索找到所有可到達(dá)路段，從而挖掘時(shí)空可到達(dá)區(qū)域.該方法對(duì)于單位置時(shí)空可達(dá)性查詢（S-query）和多位置時(shí)空可達(dá)性聯(lián)合查詢（U-query）均有效.文獻(xiàn)［7］提出并解決了多位置時(shí)空可達(dá)性交集查詢（I-query）.

與可達(dá)性相關(guān)的應(yīng)用層出不窮.文獻(xiàn)［8］構(gòu)建了基于GIS的高分辨率時(shí)空總線網(wǎng)絡(luò)模型.公共交通從起點(diǎn)到目的地的可達(dá)性通過(guò)計(jì)算總出行時(shí)間來(lái)衡量.文獻(xiàn)［9］提出了一種稱為STRC的時(shí)空可達(dá)面積計(jì)算方案，分別針對(duì)時(shí)間敏感應(yīng)用和距離相關(guān)應(yīng)用設(shè)計(jì)了邊界段選擇策略，提高了其方案在實(shí)際城市交通服務(wù)中的適用性.文獻(xiàn)［10］提出了時(shí)空網(wǎng)絡(luò)結(jié)構(gòu)的線性整數(shù)規(guī)劃模型，以最大限度提高從不同來(lái)源到特殊活動(dòng)地點(diǎn)的全系統(tǒng)交通可達(dá)性.文獻(xiàn)［11］通過(guò)構(gòu)建一個(gè)與時(shí)間相關(guān)的時(shí)空網(wǎng)絡(luò)來(lái)提高可達(dá)性，從而在道路使用者的出行時(shí)間預(yù)算內(nèi)最大限度地增加可訪問(wèn)活動(dòng)地點(diǎn)的數(shù)量.

1.2 空間關(guān)鍵詞查詢

典型的空間關(guān)鍵詞查詢包括查詢位置、查詢關(guān)鍵詞、約束集、排序函數(shù)和返回結(jié)果的數(shù)量，返回滿足約束且綜合排名較高的結(jié)果對(duì)象.文獻(xiàn)［12］將具有地理位置和文本屬性的對(duì)象稱為空間-文本對(duì)象.倒排文件常用于組織對(duì)象的文本信息.R-tree、網(wǎng)格索引及其變體通常用于組織對(duì)象的空間信息.

為了處理Top-k空間關(guān)鍵詞查詢，各種基于R-tree的索引結(jié)構(gòu)被提出.文獻(xiàn)［12］使用R-tree對(duì)所有對(duì)象的地理位置進(jìn)行索引.為每個(gè)葉節(jié)點(diǎn)創(chuàng)建一個(gè)倒排文件，以索引其包含的對(duì)象的文本.文獻(xiàn)［13］將倒排列表與R-tree結(jié)合，設(shè)計(jì)了IR-tree及其變體DIR-tree，將文本相似度與空間鄰近度融合在一起.文獻(xiàn)［14］提出的WIR-tree是IR-tree的另一個(gè)變體，它根據(jù)包含的關(guān)鍵詞對(duì)對(duì)象進(jìn)行分組，以便每個(gè)組共享盡可能少的關(guān)鍵詞，從而加快對(duì)不相關(guān)對(duì)象組的修剪.文獻(xiàn)［15］介紹了一種IR2-tree的索引結(jié)構(gòu)，它將R-tree與疊加的文本簽名結(jié)合.

此外，空間關(guān)鍵詞查詢的一些變體也被提出并解決.文獻(xiàn)［16］研究了連續(xù)移動(dòng)的Top-k空間關(guān)鍵詞查詢，提出了兩種計(jì)算安全區(qū)的算法以保證在任何時(shí)候都能得到正確的結(jié)果.文獻(xiàn)［17］提出了一種支持移動(dòng)Top-k空間關(guān)鍵詞查詢的有效方法.文獻(xiàn)［18］探索了方向感知查詢處理，它返回滿足查詢方向和關(guān)鍵詞約束的k個(gè)最近鄰對(duì)象.文獻(xiàn)［19］研究了一組位置感知對(duì)象上的通用位置感知排名查詢.傳統(tǒng)空間關(guān)鍵詞查詢及其各種變體得到了解決，然而道路網(wǎng)絡(luò)中的可達(dá)性這一重要因素并未受到重視，本文將可達(dá)性計(jì)算與傳統(tǒng)的空間關(guān)鍵詞查詢相結(jié)合，提高了查詢的精確性.

2 問(wèn)題定義

2.1 基本概念

道路網(wǎng)絡(luò)道路網(wǎng)絡(luò)用圖G=（V，E）來(lái)表示，V是頂點(diǎn)集合，E是邊的集合.頂點(diǎn)v∈V表示道路交叉點(diǎn)或端點(diǎn)，邊（v，v′）∈E代表一個(gè)路段.

空間-文本對(duì)象假設(shè)一組空間-文本對(duì)象o∈O在路網(wǎng)G的邊E上，每個(gè)對(duì)象都有空間位置信息o.l（經(jīng)緯度）和文本描述o.doc.

軌跡軌跡是道路網(wǎng)絡(luò)上交通工具行駛的路線信息，由一系列時(shí)空點(diǎn)組成，每個(gè)點(diǎn)包含軌跡ID、空間位置及時(shí)間戳等信息.

軌跡可達(dá)性給定查詢起始位置q.s、路網(wǎng)中的一個(gè)路段Ri、查詢開(kāi)始時(shí)間q.t和持續(xù)時(shí)間q.d，軌跡可達(dá)性反映了歷史軌跡是否在給定持續(xù)時(shí)間內(nèi)從起始位置穿過(guò)給定路段的事實(shí).如果路段Ri在q.d內(nèi)可以到達(dá)，則軌跡可達(dá)性為1，否則軌跡可達(dá)性為0.

可到達(dá)路段給定查詢起始位置q.s、查詢開(kāi)始時(shí)間q.t和持續(xù)時(shí)間q.d，若從q.s到路段Ri的軌跡可達(dá)性為1，則稱Ri為可到達(dá)路段.

路段可達(dá)概率路段可達(dá)概率描述了歷史軌跡數(shù)據(jù)集中在給定持續(xù)時(shí)間q.d內(nèi)，從起始路段R0（q.s所在的路段）到達(dá)目標(biāo)路段Ri（對(duì)象o所在的路段）的概率，可達(dá)概率的大小介于0和1之間.

空間-文本對(duì)象可達(dá)概率空間-文本對(duì)象的可達(dá)概率用它所在路段的可達(dá)概率來(lái)表示.

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

表1 符號(hào)與定義Tab.1 Symbols and definitions

2.2 基本定義

定義1考慮可達(dá)性的Top-k空間關(guān)鍵詞查詢q=＜q.s，q.doc，q.t，q.d，q.r，k＞，其中q.s表示查詢位置；q.doc表示查詢關(guān)鍵詞，是一個(gè)集合；q.t和q.d分別表示查詢的開(kāi)始時(shí)間和持續(xù)時(shí)間；q.r表示用戶指定的可達(dá)概率.考慮可達(dá)性的Top-k空間關(guān)鍵詞查詢q返回滿足可達(dá)性和關(guān)鍵詞要求、總評(píng)分排在前k個(gè)的空間-文本對(duì)象.總評(píng)分綜合考慮查詢q和對(duì)象o之間的可達(dá)性、空間鄰近度和文本相似性.

定義2綜合評(píng)分函數(shù)Rank（q，o）定義如下：

其中Prob（q，o）是從q.t開(kāi)始、在持續(xù)時(shí)間q.d內(nèi)，從q.s到o.l的可達(dá)概率；Sr（q.s，o.l）和Tr（q.doc，o.doc）分別為q與o之間的空間鄰近度和文本相似性.α，β∈（0，1）表示用戶的偏好參數(shù)，用于調(diào)節(jié)可達(dá)性、空間鄰近度和文本相似性在評(píng)分函數(shù)中的比重.對(duì)于空間維度的信息，當(dāng)α=0且β≠0時(shí)，用戶只考慮查詢點(diǎn)到對(duì)象的空間鄰近度；當(dāng)α≠0且β＝0時(shí)，用戶只考慮在給定時(shí)間內(nèi)能否到達(dá)，并不在意查詢點(diǎn)到對(duì)象的距離有多遠(yuǎn).

定義3可達(dá)概率Prob（q，o）是可達(dá)性的量化表示，設(shè)查詢q所在路段為R0，對(duì)象o所在路段為Ri.Prob（q，o）定義為：

其中m為歷史軌跡數(shù)據(jù)的總天數(shù)，將每一天的可達(dá)概率求和之后取平均值，即為可達(dá)概率.Probj（q，o）的計(jì)算公式為：

若Ri≠R0，trs是在開(kāi)始時(shí)間q.t經(jīng)過(guò)起始路段R0且最終經(jīng)過(guò)Ri的軌跡集合，tre是在q.t經(jīng)過(guò)起始路段R0且在［q.t，q.t+q.d］經(jīng)過(guò)Ri的軌跡集合.若Ri=R0，trs是在開(kāi)始時(shí)間q.t經(jīng)過(guò)起始路段R0的軌跡集合，tre是在［q.t，q.t+q.d］內(nèi)從未離開(kāi)過(guò)路段R0的軌跡集合.tre的計(jì)算公式為：

若Ri≠R0，根據(jù)索引結(jié)構(gòu)的時(shí)間粒度將q.d劃分為n個(gè)時(shí)間段，若路段Ri是可達(dá)的，那么可能在任何一個(gè)時(shí)間段l內(nèi)到達(dá)，從l=0開(kāi)始進(jìn)行計(jì)算，考慮在q.t所在的時(shí)間間隔內(nèi)從R0可以到達(dá)Ri的這種情況；若Ri=R0，trl是在第l個(gè)時(shí)間段內(nèi)沒(méi)有離開(kāi)路段R0的軌跡集合.

定義4空間鄰近度Sr（q.s，o.l）描述的是查詢q到對(duì)象o之間路網(wǎng)距離的鄰近度，其定義如下：d（q.s，o.l）為q.s與o.l之間的路網(wǎng)距離，dmax是路網(wǎng)中任意兩點(diǎn)之間的最大路網(wǎng)距離.

定義5文本相似性Tr（q.doc，o.doc）.本文采用cosine相似性來(lái)計(jì)算q與o之間的文本相似性，定義如下：

其中關(guān)鍵詞t在對(duì)象關(guān)鍵詞集合o.doc中的權(quán)重wt，o.doc=1+ln(ft，o.doc)，ft，o.doc為t在o.doc中 出現(xiàn) 的 次數(shù)；為空間-文本對(duì)象集合O中對(duì)象的數(shù)量，dft是集合O中關(guān)鍵詞t出現(xiàn)的次數(shù).

3 系統(tǒng)結(jié)構(gòu)

3.1 數(shù)據(jù)預(yù)處理

（1）對(duì)道路進(jìn)行重新分割.對(duì)象的可達(dá)概率由其所在路段的可達(dá)概率表示，路段過(guò)長(zhǎng)會(huì)影響查詢結(jié)果的準(zhǔn)確性，本文根據(jù)一定的空間粒度重新分割原始道路，分割時(shí)如果剩余部分的長(zhǎng)度小于給定空間粒度的一半，則將其合并到相鄰路段中；否則將其作為單獨(dú)的路段.記錄重新分割后新路段的長(zhǎng)度，并插入交叉點(diǎn)連接生成的新路段，以保持道路的連通性.圖2給出了道路重新分割后的部分路網(wǎng)結(jié)構(gòu).

圖2 道路重新分割后的部分路網(wǎng)結(jié)構(gòu)Fig.2 Partial road network structure after road re-segmentation

（2）進(jìn)行地圖匹配.將原始軌跡映射到重新分割的道路網(wǎng)絡(luò).首先將GPS點(diǎn)映射到相應(yīng)路段，然后連接所有路段以構(gòu)成映射的軌跡，并將瞬時(shí)速度、車輛ID和時(shí)間戳等添加為其屬性.一個(gè)移動(dòng)對(duì)象每天只有一條軌跡，該軌跡由包含時(shí)間、速度等屬性的路段序列構(gòu)成.

3.2 SRTR-Tree索引

為了有效組織道路網(wǎng)結(jié)構(gòu)信息、軌跡信息以及空間-文本對(duì)象的信息，在R-Tree基礎(chǔ)上構(gòu)造了一種新的索引SRTR-Tree.首先用R-Tree對(duì)道路網(wǎng)絡(luò)及其上的對(duì)象進(jìn)行劃分并保存劃分結(jié)果.圖3給出了圖2中道路網(wǎng)絡(luò)及其上對(duì)象的劃分結(jié)果.

圖3 路網(wǎng)中的交叉點(diǎn)和空間-文本對(duì)象Fig.3 Intersections and spatio-textual objects in the road network

SRTR-Tree的每個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)除外）都有一個(gè)指向其父節(jié)點(diǎn)的指針和若干個(gè)指向其子節(jié)點(diǎn)的指針.每個(gè)對(duì)象都位于一個(gè)路段上，對(duì)象的位置信息由其到所在路段頂點(diǎn)的距離表示.圖4展示了SRTR-Tree的總體結(jié)構(gòu).

圖4 SRTR-Tree索引Fig.4 SRTR-Tree index

SRTR-Tree的根節(jié)點(diǎn)連接一個(gè)鄰接組件，表2展示了鄰接組件的具體內(nèi)容，它記錄道路網(wǎng)絡(luò)中每個(gè)路段的長(zhǎng)度、其相鄰路段及交叉點(diǎn)，以查找從查詢q到對(duì)象o將經(jīng)過(guò)哪些路段.

表2 鄰接組件Tab.2 Adjacency component

SRTR-Tree的每個(gè)節(jié)點(diǎn)連接一個(gè)基于關(guān)鍵詞的倒排文件，表3為節(jié)點(diǎn)E1的倒排文件，其中包含該節(jié)點(diǎn)所指路網(wǎng)區(qū)域中所有對(duì)象的關(guān)鍵詞的并集，對(duì)每一個(gè)關(guān)鍵詞記錄包含它的子節(jié)點(diǎn)的ID，用于加速與查詢相關(guān)區(qū)域或路段的選擇.

表3 倒排文件Tab.3 Inverted file

圖5展示了SRTR-Tree中的時(shí)間-軌跡組件.時(shí)間信息有兩個(gè)維度：日期和時(shí)間.首先根據(jù)交通情況將一天的時(shí)間劃分為“早高峰時(shí)段”（7：00-9：00）、“晚高峰時(shí)段”（17：00-20：00）和“平峰時(shí)段”（除前兩個(gè)時(shí)段外的其他時(shí)段）；其次將早晚高峰時(shí)段以10 min為間隔進(jìn)行劃分，平峰時(shí)段以30 min為間隔進(jìn)行劃分.因?yàn)楦叻迤谌藗儗?duì)時(shí)間的規(guī)劃比其他時(shí)段更精確，對(duì)可達(dá)性有更高的要求，時(shí)間粒度越小，計(jì)算結(jié)果越準(zhǔn)確；最后根據(jù)“先時(shí)間，后日期”的原則，將通過(guò)某一路段的所有軌跡的ID存儲(chǔ)在相應(yīng)的日期和時(shí)間信息表中.

圖5 時(shí)間-軌跡組件Fig.5 Temporal-trajectory component

4 查詢處理

4.1 剪枝策略

引理1已知一個(gè)RSKQ查詢q=＜q.s，q.doc，q.t，q.d，q.r，k＞和一個(gè)路段R，若Prob（q，R）＜q.r，則路段R及其未被檢索的相鄰路段R′可以被安全地剪枝.

證明對(duì)于路段R上任意對(duì)象o，Prob（q，o）=Prob（q，R）.若Prob（q，R）＜q.r，則Prob（q，o）＜q.r，R上的對(duì)象都不滿足可達(dá)性要求，R可以被安全地剪枝.R的未被檢索的相鄰路段R′與查詢q的距離相較于R與q的距離更遠(yuǎn)，有Prob（q，R′）≤Prob（q，R），可知對(duì)于R′上的對(duì)象o′有Prob（q，o′）＜q.r，故R的未被檢索的相鄰路段R′也可以被安全地剪枝.

引理2已知一個(gè)RSKQ查詢q=＜q.s，q.doc，q.t，q.d，q.r，k＞和一個(gè)區(qū)域E（或路段R），若E.doc∩q.doc=?（或R.doc∩q.doc=?），則區(qū)域E（或路段R）可以被安全地剪枝.

證明對(duì)于區(qū)域E（或路段R）中的任意對(duì)象o，都有o.doc?E.doc（或o.doc?R.doc）.若E.doc∩q.doc=?（或R.doc∩q.doc=?），有o.doc∩q.doc=?，則對(duì)象o與查詢關(guān)鍵詞無(wú)關(guān)，不會(huì)是結(jié)果對(duì)象.

引理3已知一個(gè)RSKQ查詢q=＜q.s，q.doc，q.t，q.d，q.r，k＞和一個(gè)路段R，若d（q.s，R）＞dmax·［1-Rank（q，ok）］/β，則路段R可以被安全地剪枝，其中d（q.s，R）為查詢點(diǎn)和路段R之間的路網(wǎng)距離，Rank（q，ok）為當(dāng)前排在第k個(gè)的結(jié)果對(duì)象的綜合評(píng)分.此時(shí)，R的未被檢索的相鄰路段R′也可以被安全地剪枝.

證明若d（q.s，R）＞dmax·［1-Rank（q，ok）］/β，對(duì)R上的對(duì)象o有d（q.s，o）＞dmax·［1-Rank（q，ok）］/β，可知Rank（q，o）=1-β·d（q.s，R）/dmax＜1-β·（dmax·［1-Rank（q，ok）］/β）/dmax=Rank（q，ok），因此o不是結(jié)果對(duì)象，路段R可以被安全地剪枝.關(guān)于R′的證明與引理1后半部分的證明類似.

4.2 查詢處理算法

算法1給出了可達(dá)概率的計(jì)算流程.可達(dá)概率的值probability初始化為-∞，軌跡集trs和tre初始化為空（第3行）.m是軌跡數(shù)據(jù)覆蓋的總天數(shù)，Δt是SRTR-Tree中q.t所在時(shí)間區(qū)間的時(shí)間粒度.對(duì)每一天d構(gòu)造集合trs（第5-9行）和tre（第10-14行），從而根據(jù)公式（3）計(jì)算可達(dá)概率（第15行）；然后計(jì)算每一天d的可達(dá)性的平均值，并將其作為可達(dá)概率的結(jié)果值返回（第17-18行）.

?

算法2展示了RSKQ查詢的處理過(guò)程，該方法采用了路網(wǎng)擴(kuò)展的思想，從q所在路段R0開(kāi)始，按路網(wǎng)距離升序依次探索相鄰路段，直至找到k個(gè)結(jié)果對(duì)象或檢索完所有可能的路段.

集合Result、隊(duì)列NR和指針LNode初始化為空，它們分別用于保存結(jié)果對(duì)象、未被訪問(wèn)的候選路段和正在訪問(wèn)的SRTR-Tree葉子結(jié)點(diǎn).變量Rank（q，ok）初始化為-∞，用于保留集合Result中當(dāng)前第k個(gè)結(jié)果對(duì)象的綜合得分.

首先根據(jù)位置信息q.s定位查詢q所在的起始路段R0（第4行）；第6-17行對(duì)起始路段R0上的對(duì)象進(jìn)行處理，若起始路段滿足可達(dá)性要求且尚未找到k個(gè)結(jié)果對(duì)象，則對(duì)其他路段及其上的對(duì)象進(jìn)行處理（第18-32行）.檢索所有可能的路段后，返回結(jié)果集Result（第33行）.

算法時(shí)間復(fù)雜度分析：根據(jù)算法1，假設(shè)在查詢起始時(shí)間q.t經(jīng)過(guò)查詢點(diǎn)q的平均軌跡數(shù)量為|TR|、歷史軌跡數(shù)據(jù)集包含的總天數(shù)為m，那么計(jì)算可達(dá)概率的時(shí)間復(fù)雜度最高為O（|TR|×m）.根據(jù)算法2，假設(shè)需要檢索的平均路段數(shù)為|R|、每個(gè)路段上的平均關(guān)鍵詞個(gè)數(shù)為|R.doc|、查詢關(guān)鍵詞的個(gè)數(shù)為|q.doc|，則RSKQ查詢的時(shí)間 復(fù)雜度最高為O（|R|×（|TR|×m+|R.doc|×|q.doc|））.事實(shí)上，m、|TR.doc|和|q.doc|都是常數(shù)，且在使用3種剪枝技術(shù)的情況下，算法的時(shí)間復(fù)雜度小于此處給出的最高值.

?

5 實(shí)驗(yàn)

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

實(shí)驗(yàn)采用了3個(gè)數(shù)據(jù)集：（1）從OpenStreetMap中提取的深圳道路網(wǎng)；（2）一個(gè)合成的對(duì)象集，包含一組隨機(jī)分布在深圳市路網(wǎng)上的對(duì)象，對(duì)象的關(guān)鍵詞從OpenStreetMap中獲??；（3）深圳市出租車的軌跡數(shù)據(jù)集，包含21385輛出租車在2014年11月內(nèi)30天的軌跡，共有407040083個(gè)GPS點(diǎn)，平均采樣率為30 s.

目前還沒(méi)有處理RSKQ查詢的成熟算法.傳統(tǒng)的Top-k空間關(guān)鍵詞查詢通常采用基于IR-Tree的方法，單源最大邊界搜索算法（SQMB）和回溯搜索算法（TBS）共同查詢可達(dá)區(qū)域.因此，本文結(jié)合上述3種方法作為基線方法（稱為“IR-Tree+SQMB+TBS”）與所提出的基于SRTR-Tree的方法進(jìn)行比較.

實(shí)驗(yàn)通過(guò)改變開(kāi)始時(shí)間、關(guān)鍵詞數(shù)量、查詢持續(xù)時(shí)間、空間文本對(duì)象數(shù)量、結(jié)果數(shù)量、可達(dá)性、參數(shù)α和β來(lái)驗(yàn)證這兩種方法的性能，如表4所示.

表4 參數(shù)設(shè)置Tab.4 Parameter settings

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

（1）關(guān)鍵詞數(shù)量的影響.如圖6所示，隨著關(guān)鍵詞數(shù)量的增加，IR-Tree和SRTR-Tree中的候選區(qū)域或路段也增加，計(jì)算候選對(duì)象的綜合得分需要更多的時(shí)間.但基線方法的處理時(shí)間更長(zhǎng)，因?yàn)闊o(wú)論關(guān)鍵詞數(shù)量如何變化，都要首先通過(guò)SQMB+TBS算法獲得可達(dá)路段.

圖6 查詢關(guān)鍵詞數(shù)量的影響Fig.6 Impact of the number of query keywords

（2）查詢開(kāi)始時(shí)間的影響.開(kāi)始時(shí)間主要影響可達(dá)性計(jì)算的效率.由圖7可知，由于高峰時(shí)段的交通擁堵，上午8時(shí)和晚上20時(shí)左右處理時(shí)間明顯低于其他時(shí)段.當(dāng)查詢開(kāi)始時(shí)間為16時(shí)或24時(shí)，處理時(shí)間基本相同.交通狀況越好，可達(dá)面積越大，可達(dá)性計(jì)算時(shí)間越長(zhǎng)，但本文提出的方法較基線方法更優(yōu).

圖7 查詢開(kāi)始時(shí)間的影響Fig.7 Impact of the query start time

（3）查詢持續(xù)時(shí)間的影響.如圖8所示，SQMB+TBS算法的處理時(shí)間隨著q.d的增加而增加.基于IR-Tree的空間關(guān)鍵詞查詢方法，在更大的可達(dá)區(qū)域中有更多的候選對(duì)象需要檢索，因此運(yùn)行時(shí)間增加.當(dāng)q.d增加時(shí)，本文方法的處理時(shí)間增加，但少于基線方法.

圖8 查詢持續(xù)時(shí)間的影響Fig.8 Impact of the query duration

（4）可達(dá)概率的影響.SQMB+TBS算法的查詢處理時(shí)間對(duì)q.r的依賴性較小.如圖9所示，可達(dá)概率越大，候選對(duì)象數(shù)量減少，查詢處理時(shí)間縮短.本文的方法從起始路段R0開(kāi)始按照路網(wǎng)距離的升序探索相鄰的可達(dá)路段，以找到結(jié)果對(duì)象.當(dāng)q.r為0時(shí)，需要探索的路段最多，處理時(shí)間最長(zhǎng)，q.r增大時(shí)，處理時(shí)間不斷減少.

圖9 可達(dá)概率的影響Fig.9 Impact of the reachable probability

（5）對(duì)象數(shù)量的影響.由圖10可知，路網(wǎng)中對(duì)象數(shù)量的增加使得基線方法的運(yùn)行時(shí)間增加，但對(duì)象在路網(wǎng)上分布得更加密集，需要檢索的路段變少，本文所提方法的處理時(shí)間減少.

圖10 對(duì)象數(shù)量的影響Fig.10 Impact of the number of objects

（6）結(jié)果對(duì)象數(shù)量的影響.k的增加不影響SQMB+TBS算法的處理時(shí)間，基于IR-Tree的方法卻必須檢索更多的對(duì)象，但SKQ查詢所需的時(shí)間比可達(dá)概率計(jì)算少幾個(gè)數(shù)量級(jí)，基線法的處理時(shí)間變化很小.本文方法的處理時(shí)間隨k值的增大而增加，見(jiàn)圖11.

圖11 結(jié)果對(duì)象數(shù)量的影響Fig.11 Impact of the number of result objects

（7）α的影響.α為0時(shí)，查詢只關(guān)心q與o之間的路網(wǎng)距離.此時(shí)RSKQ查詢相當(dāng)于傳統(tǒng)的SKQ查詢，兩種方法的處理時(shí)間幾乎相同；α大于0時(shí)，查詢處理應(yīng)考慮對(duì)象的可達(dá)性，處理時(shí)間遠(yuǎn)高于傳統(tǒng)SKQ查詢，但增加的幅度不大，見(jiàn)圖12.

圖12 α的影響Fig.12 Impact of α

（8）β的影響.當(dāng)β為0時(shí)，只考慮從q到o的可達(dá)性.隨著β逐漸增大，查詢q和o之間的空間鄰近度的權(quán)重增加，對(duì)遠(yuǎn)離查詢q的更多區(qū)域和路段進(jìn)行修剪，減少了處理時(shí)間，見(jiàn)圖13.

圖13 β的影響Fig.13 Impact of β

6 總結(jié)

本文研究了基于可達(dá)性的Top-k空間關(guān)鍵詞查詢（RSKQ）處理問(wèn)題.將對(duì)象可達(dá)性引入到傳統(tǒng)的SKQ中，從而提高查詢結(jié)果的有效性.設(shè)計(jì)了一種高效的索引SRTR-Tree，有效地組織了道路網(wǎng)絡(luò)、軌跡和道路網(wǎng)絡(luò)上的空間-文本對(duì)象的信息.此外，還提出了幾個(gè)引理來(lái)修剪大量不相關(guān)的查詢空間對(duì)象.基于SRTR-Tree提出了解決RSKQ查詢的算法，并通過(guò)大量實(shí)驗(yàn)證明了其有效性.