已知時間的空間文本skyline查詢

郭莎莎，李 爽，閻紅燦

華北理工大學 理學院 河北省數據科學與應用重點實驗室，河北 唐山063210

1 引言

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

考慮到身邊朋友的影響，文獻[5]將社交應用到skyline查詢中；考慮到用戶行走的方向性，文獻[6]將方向應用到skyline 查詢中。以上研究均旨在提高查詢應用的質量。研究發現，某些對象并不總是最優的，比如加入時間約束后。時間信息在空間文本skyline 查詢中有重要的作用，但目前關于空間文本skyline查詢的文獻中鮮有考慮到時間信息。因此，本文將位置相關性、文本相關性和對象的有效時間三個因素作為篩選條件加入到查詢模型中，提出已知時間的空間文本skyline查詢。圖1展示了一個例子，假設某個用戶uq想要在6：00至7：00吃早餐，傳統的空間文本skyline 查詢返回的結果集為{o1} ，因為它只考慮了空間相關性和文本相關性，而TSTSQ返回的結果集為{o2}，因為它不僅考慮了空間相關性和文本相關性，還考慮了對象的有效時間。很顯然，TSTSQ返回的結果更能令用戶滿意。可見，將時間信息應用到空間文本skyline 查詢中對于精準推薦服務具有很大的潛在價值。

圖1 一個TSTSQ的例子

為了提高查詢效率，本文重新定義評價函數，為空間數據集中的對象創建TKR-Tree 索引，設計出解決TSTSQ 查詢的有效算法。查詢時，首先令評價函數值大（本文規定：值越大，對象或結點的優先性越高）的結點或對象優先處理，然后根據有效的裁剪策略對不必要的結點或對象進行裁剪，最終得到查詢的結果集。利用TKR-Tree索引和有效的裁剪策略，大大提高了查詢速度。

本文的主要貢獻如下：

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

（2）定義新的評價函數，并設計高效索引結構TKRTree。

（3）設計并實現有效的裁剪策略和查詢算法，提高了查詢的速度。

（4）在真實數據集上進行實證研究，實驗結果表明，TSTSQ查詢不僅滿足時間要求，同時提高了查詢性能。

2 相關工作

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

隨著個性化推薦應用的興起，靜態skyline查詢的優勢逐漸喪失，動態skyline查詢的優勢越來越明顯。動態skyline的計算取決于查詢點。文獻[10]提出了空間skyline 查詢的概念，skyline 對象的計算取決于對象到查詢點的距離。同時，文中使用了基于Voronoi 圖[11]的預計算索引技術來提高查詢效率。文獻[12]針對單個查詢點，考慮對象的空間距離和文本相關性，提出了基于位置的文本skyline（LTS）查詢。文獻[13]考慮多個查詢點，提出了文本相關的空間skyline。在文中提出了三種模型，并進行了詳細的分析，尤其第三個模型（Spatio-Textual Dominance，STD）給出了空間和文本相關的查詢算法。文獻[14]研究的是給定范圍的skyline 對象的查找。

以上skyline查詢主要考慮空間距離和文本相關性，沒有考慮時間因素。隨著時間在用戶生活中扮演著越來越重要的角色，開始考慮將時間信息應用到偏好查詢中。通過大量的文獻研究，發現文獻[15]在布爾空間關鍵字查詢（TABSKQ）中考慮到了對象的時間信息。文獻[16]提出了基于時間的空間關鍵字覆蓋查詢（TSKCQ），它返回滿足條件的一組對象。TSKCQ將地理空間對象的文本信息，位置信息和對象的有效時間整合在一起，在一定程度上滿足了用戶的需求。文獻[17]提出了在路網上隨著時間變化的連續skyline 查詢。該查詢為了高效地獲得對象和路網的信息，設計了兩種數據結構，分別是OADM和RDSL。文獻[18]提出了在數據流上實時的skyline查詢，并提出了一種新穎的算法SLS。這些研究雖然沒有解決時間約束的空間文本skyline查詢，但給予人們很多啟發。

基于以上研究成果，本文將對象的空間距離、文本相關性和時間屬性作為關鍵條件，構建已知時間的空間文本skyline查詢模型，以滿足用戶的多樣化和個性化需求。

3 問題定義

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

根據查詢的需要，首先給出查詢點q與對象o的空間相關性、文本相關性和時間相關性的計算函數，分別如式（1）～（3）所示。

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

其中，|q.k|表示查詢點包含的關鍵字個數，|q.k?o.k|表示查詢點關鍵字集合與對象o關鍵字集合取交集的個數，α為平衡系數，它的值很小，本文取0.001。

其中，|q.t|表示查詢點的有效時間段的長度，|q.t?o.t|表示查詢點時間段與對象o時間段相交的時間長度，α為平衡系數，它的值很小，本文取0.001。

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

圖2 對象分布及有效時間段

考慮到空間、文本和時間相關性的特點，本文將對象的相關性函數進行了重新整合。為了對距離遠，文本不相關的對象有所懲罰，本文提出新的評價函數：空間文本相關性函數kd(q,o)，如式（4）所示；為了對有效時間的長度短，文本不相關的對象有所懲罰，提出新的評價函數——時間文本相關性函數kt(q,o)，如式（5）所示。

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

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

4 TKR-Tree索引

TSTSQ 查詢中引入了時間信息、文本信息和空間信息，已有的索引結構R-Tree[19]雖然是一種非常重要的空間索引結構，但它不能索引時間信息和文本信息，所以創建新的索引成為TSTSQ查詢的關鍵技術。為了處理TSTSQ，本文設計新的索引結構TKR-Tree，該索引結構包含了時間信息、文本信息和空間信息。

TKR-Tree 包含兩類結點：葉子結點和非葉子結點。各結點包含的具體信息如下所述。

葉子結點包含的對象表現形式為o(id,l,t)，其中，id是指對象的編號；l是對象在地理空間中的位置；t是對象的有效時間段。

每個葉子結點包含一個指針InvertFile，指向該葉子結點的文本倒排表（表1）。表1中的關鍵字集合是該結點包含的所有對象關鍵字集合的并集。

表1 葉子結點文本倒排表

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

每個非葉子結點包含一個指向文本倒排表（表2）的指針InvertFile。表2 中的關鍵字集合是該結點包含的所有孩子關鍵字集合的并集。

表2 非葉子結點文本倒排表

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

（1）查詢點到父結點的最小距離小于等于到孩子結點的最小距離。

（2）所有結點包含的關鍵字集合是它的所有孩子關鍵字集合的并集。

（3）所有結點包含的有效時間段是它的所有孩子有效時間段的并集。

圖3 TKR-Tree

圖4 展示了圖3 中TKR-Tree 的結點R1、R2、R5及其所包含的對象對應的有效時間段信息。

圖4 一個TKR-Tree的例子

5 查詢算法

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

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

為了方便后面提出裁剪策略，給出結點的空間相關性、文本相關性和時間相關性計算公式，分別如式（7）～（9）所示。

其中，|q.k?e.k|表示查詢點關鍵字集合與結點e關鍵字集合相交的個數。

其中，|q.t?e.t|表示查詢點時間段與結點e時間段相交的時間長度。

結點的空間文本相關性和時間文本相關性函數如式（10）、（11）所示：

定理1 給定一個查詢點q，對于結點e和它的任意孩子e′，有QK(q,e′)≤QK(q,e)。

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

定理2 給定一個查詢點q，對于結點e和它的任意孩子e′，有QT(q,e′)≤QT(q,e)。

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

定理3 給定一個查詢點q，對于結點e和它的任意孩子e′，有kd(q,e)≤kd(q,e)。

證明根據定義3 有，MinDist(q,e′)≥MinDist(q,e)，根據公式（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 給定一個查詢點q，對于結點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 的查詢算法中，本文使用評價函數F(q,?)=kd(q,?)×kt(q,?)，利用優先隊列，在結點和對象的出入隊過程中提出了裁剪方法。

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

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

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

證明根據優先隊列的性質可知，F(q,p)≥F(q,p′)。假 設p′?TSTp，則 有kd(q,p′)≥kd(q,p) 且kt(q,p′)≥kt(q,p)，故F(q,p′)≥F(q,p)，產生矛盾，因此，p′?TSTp。

裁剪規則1在按照F(q,?)的非遞增順序出隊列的優先隊列中，設p為出隊列的對象，當前的結果集為R1。如果?o∈R1，o?TSTp，則裁剪p；如果?o∈R1，o?TSTp，則p為skyline對象，不可被裁剪。

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

裁剪規則2 在按照F(q,?)的非遞增順序出隊列的優先隊列中，設p為出隊列的結點，當前的結果集為R1。若?o∈R1,kd(q,p)≤kd(q,o)且kt(q,p)≤kt(q,o)，則裁剪p。

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

5.2 算法

算法1（TSTSQ查詢算法）

輸入：查詢點q，TKR-Tree index；

輸出：結果集R；

1. R=φ；//R 存放最終的skyline對象

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

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

4.while not Queue.IsEmpty() do

5.e=Queue.Dequeue()；

6. if e 是對象then

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

8. R ←e；

9. else //e 是結點

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

11. for e 中的每個孩子p do

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

13. end while

14. return R；

算法1 是實現已知時間的空間文本skyline 查詢處理的具體算法。4～13 行表示隊列非空時查詢的處理過程。6～8 行表示如果出隊列的是對象所執行的操作。7行表示e是首個出隊列的對象或者對象e不能被裁剪，則e是skyline對象，所以加入到結果集R中。9～12行表示e是結點時所進行的操作。10行說明如果結點e不能被裁剪掉，則繼續執行，11～12行表示將e中的所有孩子入隊列。14行返回最終的結果集R。

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

輸入：對象或結點p，結果集R；

輸出：p 的狀態；

1. if p 是對象then

2. if R=φ then

3. return false；//定理5

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

5. return true；

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

7. return false；

8. else // p 是結點

9. if R=φ then

10. return false；

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

12. return true；

13. else

14. return false；

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

對算法1和算法2的時間復雜度進行分析。由于算法1調用了算法2，故先分析算法2的時間復雜度。算法2用于判斷某個對象或結點p的狀態，假設當前結果集R中skyline 對象個數為m。在最好的情況下，直接根據裁剪策略判斷出p的狀態，此時的時間復雜度為O(1)。在最壞的情況下，裁剪策略失效，p需要與R中所有skyline對象進行比較，此時時間復雜度為O(m)。因此，算法2的時間復雜度為O(m)。

在算法1（TSTSQ查詢）的處理過程中，假設數據集中含有n個對象，通過TKR-Tree 將n個對象索引在nR個結點中。在TSTSQ 查詢的優先隊列中，結點和對象不斷進入隊列進行相應的處理操作，隊列處理的元素最多為n+nR個，每一個元素的處理均調用算法2。因此，算法1的時間復雜度為O((n+nR)×m)。

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

圖5 算法1的處理示例

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

圖6 TSTSQ中關鍵字個數k 的影響

6 實驗與結果分析

本文使用數據集North America（簡稱NA）和Oldenburg（簡稱OL），并為數據集中的每個對象分配關鍵字信息和有效時間信息。其中，NA數據集有167 331個對象，266 個不同的關鍵字；OL 數據集有6 105 個對象，59 個不同的關鍵字。使用zipf 分布[21]為兩個數據集中的每個對象分配5～10 個關鍵字，使用正態分布為每個對象分配開始時間戳和結束時間戳。每一次的實驗結果都是通過50次隨機查詢取平均值得到的。

實驗環境為Intel Core i5-6500 3.20 GHz 的CPU，8 GB內存，使用Windows 10操作系統和Eclipse集成開發環境。算法使用Java語言實現，JDK版本為13.0.1。

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

6.1 查詢關鍵字個數的影響

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

圖6（c）為關鍵字個數對裁剪率影響的對比圖，其中裁剪率在75%以上。裁剪率為被裁減的結點個數與總結點個數之比，其中NA數據集中有2 837個結點，OL數據集有501個結點。隨著關鍵字個數的增加，裁剪率逐漸下降，主要是因為隨著關鍵字個數的增加，結點中的候選skyline對象變多，能夠被直接裁減掉的結點個數減少，因此，裁剪率呈下降趨勢。

6.2 查詢時間段間隔的影響

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

圖7 TSTSQ中查詢時間段間隔的影響

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

由圖6（a）、6（b）和圖7（a）、7（b）可以看出，使用裁剪策略的算法比不使用裁剪策略算法的運行時間要少。此外，由于NA數據集的對象比OL數據集的對象多，因此，運行時間更長。

7 結束語

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