考慮可達性的Top-k空間關(guān)鍵詞查詢

任佳宇，李艷紅，馮雨

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

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

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

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

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

1 相關(guān)工作

1.1 時空可達性查詢處理

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

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

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

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

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

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

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

2 問題定義

2.1 基本概念

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

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

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

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

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

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

空間-文本對象可達概率空間-文本對象的可達概率用它所在路段的可達概率來表示.

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

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

2.2 基本定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 SRTR-Tree索引

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

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

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

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

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

表2 鄰接組件Tab.2 Adjacency component

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

表3 倒排文件Tab.3 Inverted file

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

圖5 時間-軌跡組件Fig.5 Temporal-trajectory component

4 查詢處理

4.1 剪枝策略

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

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

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

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

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

證明若d（q.s，R）＞dmax·［1-Rank（q，ok）］/β，對R上的對象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é)果對象，路段R可以被安全地剪枝.關(guān)于R′的證明與引理1后半部分的證明類似.

4.2 查詢處理算法

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

?

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

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

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

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

?

5 實驗

5.1 實驗設(shè)置

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

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

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

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

5.2 實驗結(jié)果

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

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

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

圖7 查詢開始時間的影響Fig.7 Impact of the query start time

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

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

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

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

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

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

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

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

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

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

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

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

6 總結(jié)

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