已知時(shí)間的空間文本skyline查詢

郭莎莎，李 爽，閻紅燦

華北理工大學(xué) 理學(xué)院 河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 唐山063210

1 引言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展和5G 網(wǎng)絡(luò)的興起，基于位置的服務(wù)[1]應(yīng)用越來(lái)越流行。隨后，偏好查詢[2-3]引起了研究學(xué)者們的研究興趣。skyline查詢[4]作為一種重要的偏好查詢，自然成為研究熱點(diǎn)。skyline查詢返回的結(jié)果集全部為skyline對(duì)象，skyline對(duì)象指的是不被其他任何對(duì)象所支配的對(duì)象。對(duì)象o1支配對(duì)象o2是指o1在任意維度上的值都不比o2差，且至少在一維上的值優(yōu)于o2。隨著用戶對(duì)查詢的限制條件越來(lái)越多，以往的skyline查詢不能極大地滿足用戶的需求。因此，為了更好地給用戶提供優(yōu)質(zhì)的生活服務(wù)，考慮與生活息息相關(guān)的其他影響因素勢(shì)在必行。

考慮到身邊朋友的影響，文獻(xiàn)[5]將社交應(yīng)用到skyline查詢中；考慮到用戶行走的方向性，文獻(xiàn)[6]將方向應(yīng)用到skyline 查詢中。以上研究均旨在提高查詢應(yīng)用的質(zhì)量。研究發(fā)現(xiàn)，某些對(duì)象并不總是最優(yōu)的，比如加入時(shí)間約束后。時(shí)間信息在空間文本skyline 查詢中有重要的作用，但目前關(guān)于空間文本skyline查詢的文獻(xiàn)中鮮有考慮到時(shí)間信息。因此，本文將位置相關(guān)性、文本相關(guān)性和對(duì)象的有效時(shí)間三個(gè)因素作為篩選條件加入到查詢模型中，提出已知時(shí)間的空間文本skyline查詢。圖1展示了一個(gè)例子，假設(shè)某個(gè)用戶uq想要在6：00至7：00吃早餐，傳統(tǒng)的空間文本skyline 查詢返回的結(jié)果集為{o1} ，因?yàn)樗豢紤]了空間相關(guān)性和文本相關(guān)性，而TSTSQ返回的結(jié)果集為{o2}，因?yàn)樗粌H考慮了空間相關(guān)性和文本相關(guān)性，還考慮了對(duì)象的有效時(shí)間。很顯然，TSTSQ返回的結(jié)果更能令用戶滿意?？梢?jiàn)，將時(shí)間信息應(yīng)用到空間文本skyline 查詢中對(duì)于精準(zhǔn)推薦服務(wù)具有很大的潛在價(jià)值。

圖1 一個(gè)TSTSQ的例子

為了提高查詢效率，本文重新定義評(píng)價(jià)函數(shù)，為空間數(shù)據(jù)集中的對(duì)象創(chuàng)建TKR-Tree 索引，設(shè)計(jì)出解決TSTSQ 查詢的有效算法。查詢時(shí)，首先令評(píng)價(jià)函數(shù)值大（本文規(guī)定：值越大，對(duì)象或結(jié)點(diǎn)的優(yōu)先性越高）的結(jié)點(diǎn)或?qū)ο髢?yōu)先處理，然后根據(jù)有效的裁剪策略對(duì)不必要的結(jié)點(diǎn)或?qū)ο筮M(jìn)行裁剪，最終得到查詢的結(jié)果集。利用TKR-Tree索引和有效的裁剪策略，大大提高了查詢速度。

本文的主要貢獻(xiàn)如下：

（1）提出一種新型的查詢，即已知時(shí)間的空間文本skyline查詢。

（2）定義新的評(píng)價(jià)函數(shù)，并設(shè)計(jì)高效索引結(jié)構(gòu)TKRTree。

（3）設(shè)計(jì)并實(shí)現(xiàn)有效的裁剪策略和查詢算法，提高了查詢的速度。

（4）在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)證研究，實(shí)驗(yàn)結(jié)果表明，TSTSQ查詢不僅滿足時(shí)間要求，同時(shí)提高了查詢性能。

2 相關(guān)工作

早期出現(xiàn)的skyline查詢基本不帶查詢點(diǎn)，屬于靜態(tài)skyline查詢。文獻(xiàn)[4]首次提出了skyline操作。文獻(xiàn)[7]首先將對(duì)象按照一定的規(guī)則排序，然后再計(jì)算skyline對(duì)象。文獻(xiàn)[8]使用R*-Tree來(lái)處理數(shù)據(jù)集，然后調(diào)用最近鄰搜索來(lái)獲取skyline對(duì)象。Papadias等人[9]利用R-Tree索引對(duì)象，通過(guò)最小距離來(lái)尋找skyline對(duì)象。

隨著個(gè)性化推薦應(yīng)用的興起，靜態(tài)skyline查詢的優(yōu)勢(shì)逐漸喪失，動(dòng)態(tài)skyline查詢的優(yōu)勢(shì)越來(lái)越明顯。動(dòng)態(tài)skyline的計(jì)算取決于查詢點(diǎn)。文獻(xiàn)[10]提出了空間skyline 查詢的概念，skyline 對(duì)象的計(jì)算取決于對(duì)象到查詢點(diǎn)的距離。同時(shí)，文中使用了基于Voronoi 圖[11]的預(yù)計(jì)算索引技術(shù)來(lái)提高查詢效率。文獻(xiàn)[12]針對(duì)單個(gè)查詢點(diǎn)，考慮對(duì)象的空間距離和文本相關(guān)性，提出了基于位置的文本skyline（LTS）查詢。文獻(xiàn)[13]考慮多個(gè)查詢點(diǎn)，提出了文本相關(guān)的空間skyline。在文中提出了三種模型，并進(jìn)行了詳細(xì)的分析，尤其第三個(gè)模型（Spatio-Textual Dominance，STD）給出了空間和文本相關(guān)的查詢算法。文獻(xiàn)[14]研究的是給定范圍的skyline 對(duì)象的查找。

以上skyline查詢主要考慮空間距離和文本相關(guān)性，沒(méi)有考慮時(shí)間因素。隨著時(shí)間在用戶生活中扮演著越來(lái)越重要的角色，開(kāi)始考慮將時(shí)間信息應(yīng)用到偏好查詢中。通過(guò)大量的文獻(xiàn)研究，發(fā)現(xiàn)文獻(xiàn)[15]在布爾空間關(guān)鍵字查詢（TABSKQ）中考慮到了對(duì)象的時(shí)間信息。文獻(xiàn)[16]提出了基于時(shí)間的空間關(guān)鍵字覆蓋查詢（TSKCQ），它返回滿足條件的一組對(duì)象。TSKCQ將地理空間對(duì)象的文本信息，位置信息和對(duì)象的有效時(shí)間整合在一起，在一定程度上滿足了用戶的需求。文獻(xiàn)[17]提出了在路網(wǎng)上隨著時(shí)間變化的連續(xù)skyline 查詢。該查詢?yōu)榱烁咝У孬@得對(duì)象和路網(wǎng)的信息，設(shè)計(jì)了兩種數(shù)據(jù)結(jié)構(gòu)，分別是OADM和RDSL。文獻(xiàn)[18]提出了在數(shù)據(jù)流上實(shí)時(shí)的skyline查詢，并提出了一種新穎的算法SLS。這些研究雖然沒(méi)有解決時(shí)間約束的空間文本skyline查詢，但給予人們很多啟發(fā)。

基于以上研究成果，本文將對(duì)象的空間距離、文本相關(guān)性和時(shí)間屬性作為關(guān)鍵條件，構(gòu)建已知時(shí)間的空間文本skyline查詢模型，以滿足用戶的多樣化和個(gè)性化需求。

3 問(wèn)題定義

空間數(shù)據(jù)集中對(duì)象o用(l,k,t)表示，其中o.l表示對(duì)象o在地理空間中的位置；o.k表示對(duì)象o包含的關(guān)鍵字集合；o.t表示對(duì)象o的有效時(shí)間。其中t用[st,et]表示，st,et分別表示開(kāi)始時(shí)間戳和結(jié)束時(shí)間戳。為了方便描述，設(shè)st,et∈[0,24]且st≤et。已知時(shí)間的空間文本skyline查詢q用三元組(l,k,t)表示，其中，q.l表示查詢點(diǎn)的位置，q.k表示查詢點(diǎn)包含的關(guān)鍵字集合，q.t表示查詢的有效時(shí)間段。

根據(jù)查詢的需要，首先給出查詢點(diǎn)q與對(duì)象o的空間相關(guān)性、文本相關(guān)性和時(shí)間相關(guān)性的計(jì)算函數(shù)，分別如式（1）～（3）所示。

其中，d(q,o)表示對(duì)象o到查詢點(diǎn)q的歐式距離，dmax表示數(shù)據(jù)集中任意兩對(duì)象間的最大歐式距離。

其中，|q.k|表示查詢點(diǎn)包含的關(guān)鍵字個(gè)數(shù)，|q.k?o.k|表示查詢點(diǎn)關(guān)鍵字集合與對(duì)象o關(guān)鍵字集合取交集的個(gè)數(shù)，α為平衡系數(shù)，它的值很小，本文取0.001。

其中，|q.t|表示查詢點(diǎn)的有效時(shí)間段的長(zhǎng)度，|q.t?o.t|表示查詢點(diǎn)時(shí)間段與對(duì)象o時(shí)間段相交的時(shí)間長(zhǎng)度，α為平衡系數(shù)，它的值很小，本文取0.001。

例如，如圖2所示，數(shù)據(jù)集D={o1,o2,o3,o4,o5}，圖2（b）給出了對(duì)象的有效時(shí)間段，查詢點(diǎn)q的有效時(shí)間段為[8：00，10：00]。以o1為例，根據(jù)式（3）計(jì)算o1與q的時(shí)間相關(guān)性，其中|q.t|=2，|q.t?o1.t|=1，故QT(q,o1)=1/2=0.5。o2,o3,o4,o5的時(shí)間相關(guān)性計(jì)算方法類似，不再贅述。

圖2 對(duì)象分布及有效時(shí)間段

考慮到空間、文本和時(shí)間相關(guān)性的特點(diǎn)，本文將對(duì)象的相關(guān)性函數(shù)進(jìn)行了重新整合。為了對(duì)距離遠(yuǎn)，文本不相關(guān)的對(duì)象有所懲罰，本文提出新的評(píng)價(jià)函數(shù)：空間文本相關(guān)性函數(shù)kd(q,o)，如式（4）所示；為了對(duì)有效時(shí)間的長(zhǎng)度短，文本不相關(guān)的對(duì)象有所懲罰，提出新的評(píng)價(jià)函數(shù)——時(shí)間文本相關(guān)性函數(shù)kt(q,o)，如式（5）所示。

定義1（已知時(shí)間的空間文本支配）給定空間數(shù)據(jù)集D和查詢點(diǎn)q，如果兩個(gè)對(duì)象oi和oj滿足kd(q,oi)≥kd(q,oj)且kt(q,oi)≥kt(q,oj)，并且至少有一個(gè)滿足大于條件，就稱對(duì)象oi支配對(duì)象oj，記為oi?TSToj。

定義2（已知時(shí)間的空間文本skyline）給定空間數(shù)據(jù)集D，返回那些不能夠被其他對(duì)象支配的對(duì)象的集合。即，o∈TSTS，當(dāng)且僅當(dāng)?o′∈D，o′?TSTo。

4 TKR-Tree索引

TSTSQ 查詢中引入了時(shí)間信息、文本信息和空間信息，已有的索引結(jié)構(gòu)R-Tree[19]雖然是一種非常重要的空間索引結(jié)構(gòu)，但它不能索引時(shí)間信息和文本信息，所以創(chuàng)建新的索引成為T(mén)STSQ查詢的關(guān)鍵技術(shù)。為了處理TSTSQ，本文設(shè)計(jì)新的索引結(jié)構(gòu)TKR-Tree，該索引結(jié)構(gòu)包含了時(shí)間信息、文本信息和空間信息。

TKR-Tree 包含兩類結(jié)點(diǎn)：葉子結(jié)點(diǎn)和非葉子結(jié)點(diǎn)。各結(jié)點(diǎn)包含的具體信息如下所述。

葉子結(jié)點(diǎn)包含的對(duì)象表現(xiàn)形式為o(id,l,t)，其中，id是指對(duì)象的編號(hào)；l是對(duì)象在地理空間中的位置；t是對(duì)象的有效時(shí)間段。

每個(gè)葉子結(jié)點(diǎn)包含一個(gè)指針I(yè)nvertFile，指向該葉子結(jié)點(diǎn)的文本倒排表（表1）。表1中的關(guān)鍵字集合是該結(jié)點(diǎn)包含的所有對(duì)象關(guān)鍵字集合的并集。

表1 葉子結(jié)點(diǎn)文本倒排表

非葉子結(jié)點(diǎn)包含的實(shí)體表現(xiàn)形式為e(cp,mbr,T)，其中，cp是指向孩子結(jié)點(diǎn)的指針；mbr是指包含所有孩子結(jié)點(diǎn)的最小邊界矩形框（Minimum Bounding Rectangle，MBR）；T是所有孩子結(jié)點(diǎn)的有效時(shí)間段的并集。

每個(gè)非葉子結(jié)點(diǎn)包含一個(gè)指向文本倒排表（表2）的指針I(yè)nvertFile。表2 中的關(guān)鍵字集合是該結(jié)點(diǎn)包含的所有孩子關(guān)鍵字集合的并集。

表2 非葉子結(jié)點(diǎn)文本倒排表

如圖3所示，TKR-Tree的主要性質(zhì)有：

（1）查詢點(diǎn)到父結(jié)點(diǎn)的最小距離小于等于到孩子結(jié)點(diǎn)的最小距離。

（2）所有結(jié)點(diǎn)包含的關(guān)鍵字集合是它的所有孩子關(guān)鍵字集合的并集。

（3）所有結(jié)點(diǎn)包含的有效時(shí)間段是它的所有孩子有效時(shí)間段的并集。

圖3 TKR-Tree

圖4 展示了圖3 中TKR-Tree 的結(jié)點(diǎn)R1、R2、R5及其所包含的對(duì)象對(duì)應(yīng)的有效時(shí)間段信息。

圖4 一個(gè)TKR-Tree的例子

5 查詢算法

本章給出TSTSQ 的裁剪策略、算法思想及其處理的過(guò)程。

定義3（MinDist距離[20]）n維歐式空間中的點(diǎn)p到同一空間內(nèi)某最小邊界矩形框R(s,t)的最小距離MinDist,表示為MinDist(p,R(s,t))：

為了方便后面提出裁剪策略，給出結(jié)點(diǎn)的空間相關(guān)性、文本相關(guān)性和時(shí)間相關(guān)性計(jì)算公式，分別如式（7）～（9）所示。

其中，|q.k?e.k|表示查詢點(diǎn)關(guān)鍵字集合與結(jié)點(diǎn)e關(guān)鍵字集合相交的個(gè)數(shù)。

其中，|q.t?e.t|表示查詢點(diǎn)時(shí)間段與結(jié)點(diǎn)e時(shí)間段相交的時(shí)間長(zhǎng)度。

結(jié)點(diǎn)的空間文本相關(guān)性和時(shí)間文本相關(guān)性函數(shù)如式（10）、（11）所示：

定理1 給定一個(gè)查詢點(diǎn)q，對(duì)于結(jié)點(diǎn)e和它的任意孩子e′，有QK(q,e′)≤QK(q,e)。

證明由TSTSQ 中的TKR-Tree 的性質(zhì)可知，e.k=。故e′.k?e.k，則 |q.k?e′.k|≤ |q.k?e.k|，根據(jù)公式（8）可知：QK(q,e′)≤QK(q,e)。

定理2 給定一個(gè)查詢點(diǎn)q，對(duì)于結(jié)點(diǎn)e和它的任意孩子e′，有QT(q,e′)≤QT(q,e)。

證明由TSTSQ 中的TKR-Tree 的性質(zhì)可知，e.t=。故e′.t∈e.t，則 |q.t?e′.t|≤ |q.t?e.t|，根據(jù)公式（9）可知：QT(q,e′)≤QT(q,e)。

定理3 給定一個(gè)查詢點(diǎn)q，對(duì)于結(jié)點(diǎn)e和它的任意孩子e′，有kd(q,e)≤kd(q,e)。

證明根據(jù)定義3 有，MinDist(q,e′)≥MinDist(q,e)，根據(jù)公式（7）可知：QL(q,e′)≤QL(q,e)。由定理1 可得：QK(q,e′)≤QK(q,e)。因此有：kd(q,e′)=QL(q,e′)×QK(q,e′)≤kd(q,e)=QL(q,e)×QK(q,e)。

定理4 給定一個(gè)查詢點(diǎn)q，對(duì)于結(jié)點(diǎn)e和它的任意孩子e′，有kt(q,e′)≤kt(q,e)。

證明由定理1可得：QK(q,e′)≤QK(q,e)。由定理2可得：QT(q,e′)≤QT(q,e) 。因此有：kt(q,e′)=QT(q,e′)×QK(q,e′)≤kt(q,e)=QT(q,e)×QK(q,e)。

5.1 裁剪策略

在基于TKR-Tree 的TSTSQ 的查詢算法中，本文使用評(píng)價(jià)函數(shù)F(q,?)=kd(q,?)×kt(q,?)，利用優(yōu)先隊(duì)列，在結(jié)點(diǎn)和對(duì)象的出入隊(duì)過(guò)程中提出了裁剪方法。

定理5 在按照F(q,?)的非遞增順序出隊(duì)列的優(yōu)先隊(duì)列中，首個(gè)出隊(duì)列的對(duì)象p必為skyline對(duì)象。

證明用反證法證明。假設(shè)p不是skyline對(duì)象，則存在對(duì)象p′?TSTp,此時(shí)kd(q,p′)≥kd(q,p)且kt(q,p′)≥kt(q,p) ，故F(q,p′)≥F(q,p) ，與已知矛盾，故假設(shè)不成立。因此，p必為skyline對(duì)象。

定理6 在按照F(q,?)的非遞增順序出隊(duì)列的優(yōu)先隊(duì)列中，設(shè)已出隊(duì)列的對(duì)象為p，在p之后出隊(duì)列的任意對(duì)象為p′，必有p′?TSTp。

證明根據(jù)優(yōu)先隊(duì)列的性質(zhì)可知，F(xiàn)(q,p)≥F(q,p′)。假 設(shè)p′?TSTp，則 有kd(q,p′)≥kd(q,p) 且kt(q,p′)≥kt(q,p)，故F(q,p′)≥F(q,p)，產(chǎn)生矛盾，因此，p′?TSTp。

裁剪規(guī)則1在按照F(q,?)的非遞增順序出隊(duì)列的優(yōu)先隊(duì)列中，設(shè)p為出隊(duì)列的對(duì)象，當(dāng)前的結(jié)果集為R1。如果?o∈R1，o?TSTp，則裁剪p；如果?o∈R1，o?TSTp，則p為skyline對(duì)象，不可被裁剪。

證明若?o∈R1，o?TSTp，根據(jù)定義2可知，p不可能為skyline 對(duì)象，故裁剪；若?o∈R1，o?TSTp，則當(dāng)前結(jié)果集中的任一對(duì)象都不能支配p，由定理6 可知，后續(xù)出隊(duì)列的對(duì)象也不能支配p。因此，根據(jù)定義2可知，p為skyline對(duì)象，不可以被裁減。

裁剪規(guī)則2 在按照F(q,?)的非遞增順序出隊(duì)列的優(yōu)先隊(duì)列中，設(shè)p為出隊(duì)列的結(jié)點(diǎn)，當(dāng)前的結(jié)果集為R1。若?o∈R1,kd(q,p)≤kd(q,o)且kt(q,p)≤kt(q,o)，則裁剪p。

證明根據(jù)定理3，對(duì)于p的任意孩子e，kd(q,e)≤kd(q,p)，根據(jù)定理4 有，kt(q,e)≤kt(q,p)。類似地，若e的孩子為對(duì)象，則會(huì)被o支配，同理，在p.MBR 中的任意對(duì)象p′，都有o?TSTp′。綜上，p可以被裁剪。

5.2 算法

算法1（TSTSQ查詢算法）

輸入：查詢點(diǎn)q，TKR-Tree index；

輸出：結(jié)果集R；

1. R=φ；//R 存放最終的skyline對(duì)象

2. Queue ←NewPriorityQueue() ；/*初始化優(yōu)先隊(duì)列（優(yōu)先隊(duì)列按照F(q,?)的非遞增順序出隊(duì)列）*/

3.Queue.Enqueue(index.RootNode,1,1)；

4.while not Queue.IsEmpty() do

5.e=Queue.Dequeue()；

6. if e 是對(duì)象then

7. if R==φ||!Prunes(e,R) then /*調(diào)用裁剪函數(shù)，若返回true，e 被裁減；若返回false，e 不會(huì)被裁減，為skyline對(duì)象*/

8. R ←e；

9. else //e 是結(jié)點(diǎn)

10. if !Prunes(e,R) then /*調(diào)用裁減函數(shù)，若返回true，e 直接被裁減；若返回false，e 不可以被裁剪*/

11. for e 中的每個(gè)孩子p do

12.Queue.Enqueue(p,kd(q,p),kt(q,p))；

13. end while

14. return R；

算法1 是實(shí)現(xiàn)已知時(shí)間的空間文本skyline 查詢處理的具體算法。4～13 行表示隊(duì)列非空時(shí)查詢的處理過(guò)程。6～8 行表示如果出隊(duì)列的是對(duì)象所執(zhí)行的操作。7行表示e是首個(gè)出隊(duì)列的對(duì)象或者對(duì)象e不能被裁剪，則e是skyline對(duì)象，所以加入到結(jié)果集R中。9～12行表示e是結(jié)點(diǎn)時(shí)所進(jìn)行的操作。10行說(shuō)明如果結(jié)點(diǎn)e不能被裁剪掉，則繼續(xù)執(zhí)行，11～12行表示將e中的所有孩子入隊(duì)列。14行返回最終的結(jié)果集R。

算法2（裁剪算法Prunes(p,R)）

輸入：對(duì)象或結(jié)點(diǎn)p，結(jié)果集R；

輸出：p 的狀態(tài)；

1. if p 是對(duì)象then

2. if R=φ then

3. return false；//定理5

4. else if (?o ∈R,o ?TSTp) then //裁剪規(guī)則1

5. return true；

6. else if (?o ∈R,o ?TSTp) then //裁剪規(guī)則1

7. return false；

8. else // p 是結(jié)點(diǎn)

9. if R=φ then

10. return false；

11. else if (p 符合裁剪規(guī)則2）then

12. return true；

13. else

14. return false；

算法2為判斷skyline對(duì)象的裁剪算法Prunes(p,R)。2～3行表示如果p為第一個(gè)出隊(duì)列的對(duì)象，則p一定是skyline 對(duì)象，在定理5 中已經(jīng)證明。4～5 行說(shuō)明如果p滿足裁剪規(guī)則1 中的情形?o∈R，o?TSTp，則p不是skyline 對(duì)象，直接被裁剪，6～7 行說(shuō)明如果p滿足裁剪規(guī)則1 中的情形?o∈R，o?TSTp，則p是skyline 對(duì)象，不能被裁剪。9～10 行表示R為空時(shí)，p不能被裁剪，需要進(jìn)一步處理，11～12 行說(shuō)明如果p滿足裁剪規(guī)則2，p能夠被裁剪，所以它的孩子無(wú)需再處理，無(wú)需進(jìn)隊(duì)列，13～14行表示其他情況下，p不能被裁剪，故需要繼續(xù)處理。

對(duì)算法1和算法2的時(shí)間復(fù)雜度進(jìn)行分析。由于算法1調(diào)用了算法2，故先分析算法2的時(shí)間復(fù)雜度。算法2用于判斷某個(gè)對(duì)象或結(jié)點(diǎn)p的狀態(tài)，假設(shè)當(dāng)前結(jié)果集R中skyline 對(duì)象個(gè)數(shù)為m。在最好的情況下，直接根據(jù)裁剪策略判斷出p的狀態(tài)，此時(shí)的時(shí)間復(fù)雜度為O(1)。在最壞的情況下，裁剪策略失效，p需要與R中所有skyline對(duì)象進(jìn)行比較，此時(shí)時(shí)間復(fù)雜度為O(m)。因此，算法2的時(shí)間復(fù)雜度為O(m)。

在算法1（TSTSQ查詢）的處理過(guò)程中，假設(shè)數(shù)據(jù)集中含有n個(gè)對(duì)象，通過(guò)TKR-Tree 將n個(gè)對(duì)象索引在nR個(gè)結(jié)點(diǎn)中。在TSTSQ 查詢的優(yōu)先隊(duì)列中，結(jié)點(diǎn)和對(duì)象不斷進(jìn)入隊(duì)列進(jìn)行相應(yīng)的處理操作，隊(duì)列處理的元素最多為n+nR個(gè)，每一個(gè)元素的處理均調(diào)用算法2。因此，算法1的時(shí)間復(fù)雜度為O((n+nR)×m)。

為了便于理解TSTSQ查詢處理過(guò)程中裁剪的具體過(guò)程，給出一個(gè)實(shí)例。對(duì)象o1～o5在空間中的分布，對(duì)象的時(shí)空和文本信息以及查詢過(guò)程中隊(duì)列的變化如圖5所示。

圖5 算法1的處理示例

在查詢處理的過(guò)程中，首先根結(jié)點(diǎn)入隊(duì)列，然后它的孩子N1和N2入隊(duì)列。由于結(jié)點(diǎn)N2的評(píng)價(jià)函數(shù)F(q,N2)值要比F(q,N1)大，所以結(jié)點(diǎn)N2出隊(duì)列，然后它的孩子o4和o5入隊(duì)列，此時(shí)隊(duì)列中有對(duì)象o4和o5以及結(jié)點(diǎn)N1，經(jīng)過(guò)計(jì)算，F(xiàn)(q,o4)最大，因此，o4出隊(duì)列，o4是首個(gè)出隊(duì)列的對(duì)象，根據(jù)定理5可知，o4必為skyline對(duì)象，加入結(jié)果集R,R={o4}。此時(shí)隊(duì)列中剩余的為對(duì)象o5和結(jié)點(diǎn)N1，經(jīng)過(guò)計(jì)算，F(xiàn)(q,o5)較大，因此，o5出隊(duì)列，根據(jù)裁剪規(guī)則1 可知，o5為skyline 對(duì)象，加入結(jié)果集R,R={o4,o5}。此時(shí)隊(duì)列中剩余的只有結(jié)點(diǎn)N1,N1出隊(duì)列，由于F(q,N1)小于F(q,o4)和F(q,o5)，根據(jù)裁剪規(guī)則2可知，結(jié)點(diǎn)N1被裁減，它的孩子o1、o2和o3無(wú)需入隊(duì)列，無(wú)需再進(jìn)行相關(guān)的計(jì)算，從而節(jié)省了算法的運(yùn)行時(shí)間。

圖6 TSTSQ中關(guān)鍵字個(gè)數(shù)k 的影響

6 實(shí)驗(yàn)與結(jié)果分析

本文使用數(shù)據(jù)集North America（簡(jiǎn)稱NA）和Oldenburg（簡(jiǎn)稱OL），并為數(shù)據(jù)集中的每個(gè)對(duì)象分配關(guān)鍵字信息和有效時(shí)間信息。其中，NA數(shù)據(jù)集有167 331個(gè)對(duì)象，266 個(gè)不同的關(guān)鍵字；OL 數(shù)據(jù)集有6 105 個(gè)對(duì)象，59 個(gè)不同的關(guān)鍵字。使用zipf 分布[21]為兩個(gè)數(shù)據(jù)集中的每個(gè)對(duì)象分配5～10 個(gè)關(guān)鍵字，使用正態(tài)分布為每個(gè)對(duì)象分配開(kāi)始時(shí)間戳和結(jié)束時(shí)間戳。每一次的實(shí)驗(yàn)結(jié)果都是通過(guò)50次隨機(jī)查詢?nèi)∑骄档玫降摹?/p>

實(shí)驗(yàn)環(huán)境為Intel Core i5-6500 3.20 GHz 的CPU，8 GB內(nèi)存，使用Windows 10操作系統(tǒng)和Eclipse集成開(kāi)發(fā)環(huán)境。算法使用Java語(yǔ)言實(shí)現(xiàn)，JDK版本為13.0.1。

為了測(cè)試所提裁剪策略的效果，分別在NA 和OL數(shù)據(jù)集上比較了使用裁剪策略（TSTSQ）和不使用裁剪策略（TSTSQ'）的方法。

6.1 查詢關(guān)鍵字個(gè)數(shù)的影響

圖6（a）和圖6（b）為關(guān)鍵字個(gè)數(shù)對(duì)運(yùn)行時(shí)間影響的對(duì)比圖。從圖中可以看出，隨著關(guān)鍵字個(gè)數(shù)的增加，運(yùn)行時(shí)間逐漸上升。因?yàn)閷?duì)于查詢者給定的任一關(guān)鍵字，在倒排表中都要被訪問(wèn)。隨著關(guān)鍵字個(gè)數(shù)的增加，倒排表被頻繁訪問(wèn)，存在更多的候選skyline對(duì)象，需要更多的比較次數(shù)。因此，訪問(wèn)文本倒排表的時(shí)間變長(zhǎng)，從而計(jì)算文本相關(guān)性的時(shí)間變長(zhǎng)，程序的運(yùn)行時(shí)間變長(zhǎng)。同時(shí)，發(fā)現(xiàn)TSTSQ 的運(yùn)行時(shí)間少于TSTSQ'的運(yùn)行時(shí)間，這是因?yàn)?，TSTSQ在計(jì)算skyline對(duì)象時(shí)，根據(jù)裁剪策略將某些結(jié)點(diǎn)或者對(duì)象直接裁剪掉，減少了計(jì)算代價(jià)，節(jié)省了時(shí)間。因此，運(yùn)行時(shí)間要比TSTSQ'變短。

圖6（c）為關(guān)鍵字個(gè)數(shù)對(duì)裁剪率影響的對(duì)比圖，其中裁剪率在75%以上。裁剪率為被裁減的結(jié)點(diǎn)個(gè)數(shù)與總結(jié)點(diǎn)個(gè)數(shù)之比，其中NA數(shù)據(jù)集中有2 837個(gè)結(jié)點(diǎn)，OL數(shù)據(jù)集有501個(gè)結(jié)點(diǎn)。隨著關(guān)鍵字個(gè)數(shù)的增加，裁剪率逐漸下降，主要是因?yàn)殡S著關(guān)鍵字個(gè)數(shù)的增加，結(jié)點(diǎn)中的候選skyline對(duì)象變多，能夠被直接裁減掉的結(jié)點(diǎn)個(gè)數(shù)減少，因此，裁剪率呈下降趨勢(shì)。

6.2 查詢時(shí)間段間隔的影響

圖7（a）和圖7（b）為查詢時(shí)間段間隔對(duì)運(yùn)行時(shí)間影響的對(duì)比圖。從圖中可以看出隨著查詢時(shí)間段間隔的增加，運(yùn)行時(shí)間逐漸上升，這是因?yàn)殡S著有效時(shí)間段間隔的增加，可能更多的對(duì)象滿足條件，從而候選skyline對(duì)象增多，故需要比較的次數(shù)增加，運(yùn)行時(shí)間變長(zhǎng)。同時(shí)，由于TSTSQ應(yīng)用了裁剪策略，候選skyline對(duì)象在計(jì)算過(guò)程中直接被裁減掉，減少了計(jì)算時(shí)間。而TSTSQ'則是將全部對(duì)象進(jìn)行檢查，明顯運(yùn)行時(shí)間要比TSTSQ變長(zhǎng)。

圖7 TSTSQ中查詢時(shí)間段間隔的影響

圖7（c）為查詢時(shí)間段間隔對(duì)裁剪率影響的對(duì)比圖，其中裁剪率在70%以上。隨著查詢時(shí)間段間隔的增加，裁剪率幾乎不變，說(shuō)明查詢時(shí)間段間隔對(duì)裁剪的影響很微小。

由圖6（a）、6（b）和圖7（a）、7（b）可以看出，使用裁剪策略的算法比不使用裁剪策略算法的運(yùn)行時(shí)間要少。此外，由于NA數(shù)據(jù)集的對(duì)象比OL數(shù)據(jù)集的對(duì)象多，因此，運(yùn)行時(shí)間更長(zhǎng)。

7 結(jié)束語(yǔ)

本文提出了一種新型的查詢，即已知時(shí)間的空間文本skyline 查詢TSTSQ。與空間文本skyline 查詢相比，TSTSQ 不僅考慮了對(duì)象的空間信息和文本信息，還考慮了對(duì)象的有效時(shí)間，極大地滿足了查詢者的個(gè)性化需求。在TSTSQ中，引入了新的評(píng)價(jià)函數(shù)，構(gòu)建了新型的索引結(jié)構(gòu)TKR-Tree，提出了有效的裁剪策略，實(shí)現(xiàn)了解決該查詢的高效算法，并用Java語(yǔ)言實(shí)現(xiàn)了真實(shí)數(shù)據(jù)集上的查詢，驗(yàn)證了所提算法的有效性。下一步考慮將查詢擴(kuò)展到路網(wǎng)上，對(duì)范圍受限的已知時(shí)間的空間文本skyline查詢做進(jìn)一步的應(yīng)用研究。