基于時間的空間文本關鍵詞skyline 查詢

李晨陽， 董雷剛， 孫國豪， 于 泉

（1 吉林化工學院信息與控制工程學院， 吉林吉林 132022； 2 白城師范學院計算機科學學院， 吉林白城 137000；3 東華大學計算機科學與技術學院， 上海 201620； 4 螞蟻科技集團股份有限公司， 杭州 310012）

0 引 言

科技的發展產生了海量的數據信息，在移動通信和互聯網技術快速發展的背景下，用戶對互聯網中的數據信息提出了具有特定的查詢需求。 2001年，B?rzs?nyi 等人在文獻［1］中首次將skyline 查詢應用于數據庫領域，作為一種高效的數據檢索方式，被廣泛應用于多目標決策、市場分析和數據挖掘等多個領域中。 Skyline 查詢的結果為一組skyline 對象，這些skyline 對象均不能被同一數據集中其它任何對象支配。

在實際應用中，用戶對查詢的要求越來越多，現有的空間文本skyline 查詢算法在計算時考慮的因素較少，無法滿足用戶需求。 例如，用戶計劃在某天晚上與朋友聚餐，需要預定一個20：00－22：00 時間段可以營業、距離火車站近、價格低、服務質量好，且最好擁有停車場的飯店。 在表1 中列出了4 個飯店的信息，包含了飯店到查詢點的空間距離、飯店的人均消費價格、用戶評分、關鍵詞信息以及營業時間。

表1 飯店信息Tab. 1 Hotel information

由于此類查詢同時包括空間位置、數值型信息、關鍵詞以及時間4 個屬性，以往的空間文本skyline查詢不能直接解決此類問題。 如，文獻［2］中提出了空間多關鍵詞skyline 查詢算法SKS，將空間距離和文本相似度相結合，建立了加權距離的空間文本支配模型。 SKS 算法主要考慮了加權距離和數值型屬性，并沒有考慮時間屬性對查詢結果的影響。 文獻［3］中提出了已知時間的空間文本skyline 查詢TSTSQ，TSTSQ 中考慮了查詢點和對象間的空間距離、查詢關鍵詞與對象包含的關鍵詞間的文本相關性以及查詢時間段和對象包含時間段的時間相關性3 個屬性。 在查詢時通過計算空間文本相關性函數kd（q，o） 和時間文本相關性函數kt（q，o） 來判斷對象間的支配關系。 然而，此查詢并沒有考慮數值型信息對查詢結果的影響，查詢結果集具有一定的缺陷。 當前文獻考慮的都是時間、空間距離、數值型信息和關鍵詞中的若干個因素，并沒有將這4 個因素同時考慮進去進行研究，而同時考慮這4 個因素后將會為用戶返回更適合用戶偏好的結果集。

基于此，本文將時間、空間距離、數值型信息和關鍵詞幾個因素相結合，提出一種基于時間的空間文本關鍵詞skyline 查詢，構建基于時間的空間文本關鍵詞skyline 查詢的索引結構以及查詢算法，滿足用戶更多和更具體的查詢需求。

1 相關工作

最開始對skyline 查詢的研究是以數值型屬性為支配判斷條件找到最優候選集，文獻［4］中介紹了最近鄰NN 算法和分支界限BBS 算法，其中，最近鄰搜索策略是基于R?－Tree 索引對象，BBS 算法是在NN 算法的基礎上進行改進，BBS 算法只對可能包含skyline 點的R 樹節點進行訪問，不會重復檢索，其內存開銷明顯小于NN 算法。 然而，上述查詢沒有考慮空間屬性對查詢結果的影響。 隨著進一步的研究，文獻［5］考慮了空間屬性，提出了歐式空間和路網空間中的skyline 查詢問題；文獻［6］中將K－支配應用到道路網skyline 查詢中，提出了道路網環境下K－支配空間skyline 查詢方法，來處理多屬性數據對象。 在實際應用中只考慮空間屬性并不能滿足用戶的偏好性需求，用戶的偏好性需求一般通過關鍵詞等文本信息來描述，文獻［7］提出將空間位置和查詢關鍵詞作為查詢條件，使用Voronoi 進行空間數據管理，建立路網中每個點的主導區域來求解最優查詢結果。 考慮在實際應用中歐式距離的局限性，文獻［8］ 提出了基于曼哈頓距離的空間skyline 查詢；文獻［9］提出使用R?樹索引空間和文本數據，文本數據采用倒排文件索引結構，并添加到R?樹上，該索引結構插入數據的速度比R 樹快，并且比傳統的空間索引花費時間少；文獻［10］提出了加權空間skyline 查詢，每個興趣點都有不同的重要性，給每個興趣點分配不同的權重，并使用加權歐幾里得距離來獲取skyline 點集。

以上文獻雖然在一定程度上解決了skyline 查詢和空間文本skyline 查詢等問題，但隨著用戶的偏好性需求不斷增加，以往的skyline 查詢已經不能滿足用戶的需求，需要考慮其他因素對查詢結果的影響。 在移動互聯網環境下，文獻［11］將方向這一屬性應用到空間skyline 查詢中，提出了基于方向的空間skyline，該查詢從不同方向檢索最優候選對象，查詢結果為不同方向上的skyline 對象，并提出了偽skyline 的概念，如果某一方向上沒有skyline 對象，則用偽skyline 對象替代。 考慮到用戶社交對查詢的影響，文獻［12］提出了基于社交的空間文本skyline 查詢，設計了新的評價函數來計算用戶的社交相關性。 為了提高查詢結果的質量，引入了受限skyline，當skyline 查詢返回的結果少于設定的閾值時，需要進行受限skyline 查找，最后返回的是skyline 對象和受限skyline 對象。 文獻［13］將空間關鍵字查詢與社交數據相結合，提出了路網地理社交top－k 和skyline 關鍵詞查詢，通過對象的空間信息、文本信息和社交網絡信息來進行查詢。 考慮到時間在查詢中的重要作用。 文獻［14］將時間信息與空間關鍵詞查詢結合，同時考慮對象與查詢點之間的位置相關性、文本相關性和時間相關性，并且定義了兩個評價函數來滿足用戶的不同需求。 文獻［15］提出了在路網中有效處理具有時變屬性的對象的skyline 查詢問題。 文獻［16］將時間屬性應用到Top－k 查詢中，根據用戶的空間位置和時間，為用戶返回k條旅行時間最短的路線。

綜上所述，現有算法并不能解決帶有時間的空間文本關鍵詞skyline 查詢問題，因此本文提出一種基于時間的空間文本關鍵詞skyline 查詢，獲得那些在時間、空間、文本、數值4 個方面具有最優表現的對象集合，以滿足用戶更具體的偏好需求。

2 問題定義

為了清晰地判斷對象間的支配關系，本節將著重介紹查詢點q與對象o之間的空間距離、關鍵詞相關性、時間相關性以及時空關鍵詞相關性的評價函數。

2.1 空間距離

其中，d（q，o）表示查詢點和對象點間的歐式距離，則查詢點與對象點間的空間距離就是兩點間的歐式距離。

2.2 關鍵詞相關性

假設查詢關鍵詞有n個，對象包含的關鍵詞有m個，則有

其中，｜qki∩okj ｜≠0 表示查詢關鍵詞與對象包含的關鍵詞相交；｜qki∩okj ｜＝0 表示查詢關鍵詞與對象包含的關鍵詞不相交；ωi表示查詢關鍵詞的權重。

每個查詢關鍵詞的權重有兩種設定情況，一是由用戶根據偏好對每個查詢關鍵詞進行設定，其二是默認所有查詢關鍵詞的權重相等。Vi表示每個查詢關鍵詞與對象包含的關鍵詞的相關性，則關鍵詞相關性就是每個查詢關鍵詞與對象包含的關鍵詞的相關性之和。

以表1 中包含的對象為例，其中包含了飯店到查詢點的空間距離、飯店的人均消費價格、用戶評分、關鍵詞信息以及營業時間等信息。 假設用戶查詢的關鍵詞為“wifi”和“空調”，關鍵詞的權重根據用戶的偏好設定，設用戶對“wifi”的偏好權重為0.6，對“空調”的偏好權重為0.4，則對象a、b、c、d的關鍵詞相關性分別為0.4、1、0、0.6，如果用戶沒有設置關鍵詞的權重，則默認所有查詢關鍵詞的權重相等，此時對象a、b、c、d的關鍵詞相關性分別為0.5、1、0、0.5。

2.3 時間相關性

其中，｜qtq∩otq ｜表示查詢時間段與對象包含的時間段之間相交的數值，｜qtq ｜表示查詢時間段的數值，則時間相關性就是查詢時間段和對象包含的時間段間相交的數值與查詢時間段的數值的比值。 以表1 中包含的對象為例，假設用戶查詢的時間段是20：00－22：00，則對象a、b、c、d的時間相關性分別為0、1、0、1。

為了對某個對象的空間距離、關鍵詞相關性及時間相關性有一個綜合評價，本文提出了時空關鍵詞相關性函數來衡量一個對象同時在空間、時間、文本上的優劣程度。 其中，α是一個平衡系數，用來平衡關鍵詞相關性與時間相關性間的權重，在沒有用戶設定的情況下，默認二者權重相等。 本文設定時空關鍵詞相關性的數值越小對象越優。

2.4 時空關鍵詞相關性

以表1 中包含的對象為例，假設用戶查詢的關鍵詞為“wifi” 和“空調”，用戶查詢的時間段是20：00－22：00，默認所有查詢關鍵詞的權重相等。根據計算，對象c的關鍵詞相關性為0，對象a和對象c的時間相關性都為0。 因此，對象a、c不必進行計算可以根據算法提前裁剪，而對象b、d的時空關鍵詞相關性分別為4、6，說明對象b優于d。

定義1（數值型信息支配） 給定數據集中具有n維數值型屬性的任意兩個對象oi、oj，如果oi在其m維數值型屬性中至少有一維屬性優于oj，則稱在m維數值型屬性上oi支配oj，記為oi?NIoj。

本文設定數值型屬性的數值越小對象表現越優，但在表1 中用戶評分屬性一般是數值越大越好。如果遇到某一數值型屬性值越大對象越優的情況，則先將對象o進行預處理：oi′＝maxi － oi，其中maxi表示第i維數值型屬性的最大值，oi表示對象o在第i維數值型屬性的取值。

定義2（基于時間的空間文本關鍵詞支配）給定查詢點q和空間數據集D中的任意兩個對象oi、oj，如果oi、oj同時滿足oi?NIoj且TSKR（q，oi） ≤TSKR（q，oj），則稱oi基于時間的空間文本關鍵詞支配oj，記為oi?TSTKoj。

以表1 中包含的對象為例，假設用戶需要預定晚上20：00－22：00 與其當前位置距離近、價格低、服務質量好，最好擁有“wifi”和“空調”的飯店。根據計算對象b、d的時空關鍵詞相關性分別為4、6，并且根據對象b和d的數值型信息可知b?NId，所以由定義2 可知，b?TSTKd。

定義3（基于時間的空間文本關鍵詞skyline）

給定一個數據集D，基于時間的空間文本關鍵詞skyline 就是從該數據集中返回那些不能被其它任何對象支配對象的集合。 即，當且僅當?o′ ∈D、o′ ≮TSTKo時o∈TSTKS。

由定義2 中的例子可得，基于時間的空間文本關鍵詞skyline 為｛b｝。

3 STTR－Tree 索引

為了高效地獲取skyline 對象，需要建立相關索引結構。 雖然R－Tree［17］是一種經典的空間索引數據結構，但其只包含對象的空間信息，隨后學者們又提出了IR－Tree［18］、IR2－Tree［19］等空間索引，也不能同時存儲對象的空間、數值型信息、關鍵詞及時間等信息。 因此，本文提出一種可以同時存儲對象的空間、數值型信息、關鍵詞及時間等信息的STTR－Tree 索引。 STTR－Tree 索引結構如圖1 所示。

圖1 STTR－Tree 索引Fig. 1 STTR－Tree index

STTR－Tree 索引中葉子結點主要包含以下信息：對象的空間位置信息（location）、對象在數據集中的標識符（id）、對象包含的時間段信息（time）、指向該結點的文件倒排表的指針（InvertedFile）。 文件倒排表中的關鍵詞是由該結點包含的所有對象關鍵詞的并集組成。 對象o1、o2、o4、o5、o6包含的時間段信息見表2，葉子結點的文件倒排表見表3。

表2 對象的時間段信息Tab. 2 Time period information of objects

表3 葉子結點文件倒排表Tab. 3 Inverted list of leaf node files

圖1 中，sf 表示該結點對應的簽名文件，結點的簽名文件是由該結點中所有對象的簽名文件進行or操作產生。 在STTR－Tree 中，假設簽名文件為一串8 位的二進制碼，通過設定的hash 函數將關鍵詞映射到每一位二進制碼中。 如果二進制碼中的位為1，則表示該位包含對應的關鍵詞，若二進制碼中的位為0，則表示該位不包含對應的關鍵詞。 例如，在STTR－Tree 中，假設o1、o2、o5的簽名文件分別為10010000、01000100、00010100，將o1、o2、o5的簽名文件進行or 操作， 生成結點N1的簽名文件11010100。 同理，其它結點以同樣的方式生成相應的簽名文件。

算法在執行查詢過程時，首先查詢關鍵詞與結點包含的關鍵詞進行匹配，將查詢關鍵詞的簽名文件與結點包含的簽名文件執行and 操作，若兩個二進制簽名文件執行and 操作的結果與查詢關鍵詞生成的二進制簽名文件相同，則表示該結點包含查詢關鍵詞，反之則不包含。 例如，查詢關鍵詞生成的簽名文件為00000101，對于STTR－Tree 根節點，將查詢簽名文件與根結點的簽名文件進行and 操作，00000101 and 11011111 ＝00000101，此結果表示根結點包含查詢關鍵詞。

NumTextP 表示指向該結點的數值型信息的指針，結點的數值型信息同時包含了該結點的所有對象的數值型信息。 葉子結點的數值型信息見表4。

表4 數值型信息Tab. 4 Numerical information

非葉子結點主要包含以下信息：該結點所有子結點的最小邊界矩形（mbr）、指向該結點的子結點指針（cnp）、該結點包含的所有子結點時間段的并集（Time）、該結點對應的簽名文件（SF），結點的簽名文件是由所有子結點的簽名文件進行or 操作產生的。 結點N1、N2、N5包含的時間段信息見表5。

表5 結點的時間段信息Tab. 5 Time period information of nodes

4 算法描述

本節根據STTR－Tree 索引提出了TSTKSQ 的裁剪策略和算法。 TSTKSQ 算法在遍歷STTR－Tree 索引時，先判斷結點是否在查詢范圍之內，然后將結點包含的關鍵詞和時間段信息與查詢關鍵詞和時間段信息進行相交判定；算法從空間、關鍵詞和時間3 個屬性對空間數據集上的對象進行過濾；當算法遍歷至葉子結點時，將篩選出關鍵詞相關和時間相關的對象進行數值型信息支配和基于時間的空間文本關鍵詞支配關系判斷，最終獲取查詢結果集。

4.1 裁剪策略

TSTKSQ 算法在遍歷STTR－Tree 索引時，對結點采用如下裁剪策略：

（1）若查詢關鍵詞與結點包含的關鍵詞不相交，則不必進行時間段相交的判斷，直接將結點進行剪枝。

（2）若查詢時間段與結點包含的時間段不相交，則不必進行關鍵詞相交的判斷，直接將結點進行剪枝。

（3）若同時滿足查詢關鍵詞與結點包含的關鍵詞相交，以及查詢時間段與結點包含的時間段相交，則對其子結點進行重復判斷，直到篩選出滿足條件的候選對象，否則將結點進行剪枝。

在基于STTR－Tree 的查詢算法和裁剪算法中，本文使用優先隊列對候選集C和結果集R進行維護，優先隊列中的對象按照TSKR 的非遞減順序出隊列。

定理1［3］在按照TSKR 的非遞減順序出隊列的優先隊列中，首個出隊列的對象o必為skyline 對象。

定理2給定數據集中的任意兩個對象oi、oj，如果oi與oj之間不存在數值型信息支配，則oi與oj之間也不存在基于時間的空間文本關鍵詞支配。

證明由于oi與oj之間不存在數值型信息支配關系，根據定義2 可知，oi與oj之間不能同時滿足oi?NIoj且TSKR（q，oi） ≤TSKR（q，oj），所以oi與oj之間也不存在基于時間的空間文本關鍵詞支配。

例如，表1 中的對象a和b，由于a在用戶評分這一屬性上支配b，而b在人均價格這一屬性上支配a，所以二者不存在數值型信息支配關系，因此二者也不存在基于時間的空間文本關鍵詞支配關系。

定理3［3］在按照TSKR 的非遞減順序出隊列的優先隊列中，若已出隊列的對象為o，在o之后出隊列的任意對象為o′ ，必有o′≮TSTKo。

定理4在按照TSKR 的非遞減順序出隊列的優先隊列中，設先出隊列的對象為o，后出隊列的對象為o′，若oi?NIo′，則o?TSTKo′ 。

證明根據優先隊列的性質可知，TSKR（q，o） ≤TSKR（q，o′），根據定義2 可知，o?TSTKo′。

例如定義2 中的例子，對象b和d的TSKR 分別為4、6，因此先出隊列的對象為b，后出隊列的對象為d，又因為b?NId，所以b?TSTKd。

在基于STTR－Tree 的TSTKSQ 算法中，本文對候選對象采用如下裁剪策略：

按照TSKR 的非遞減順序出隊列的優先隊列中，設當前出候選集隊列的對象為o，當前結果集中的任一對象為sp，若sp?NIo，則裁剪o，否則將對象o放入結果集中。

證明根據優先隊列的性質可知， TSKR（q，sp） ≤TSKR（q，o），若sp?NIo，根據定義2 可知sp基于時間的空間文本關鍵詞支配o，此時對象o可以被裁剪，反之，若sp與o之間不存在數值型信息支配關系，根據定理2，sp與o之間也不存在基于時間的空間文本關鍵詞支配，所以o為skyline對象，放入結果集中。

4.2 算法

算法1TSTKSQ 算法

輸入查詢點q、查詢關鍵詞qk、查詢時間段qtq、查詢范圍r、STTR － Tree 索引、空間對象點集O

輸出查詢結果集R

1R＝?；C＝?； ／／R存放查詢結果集，C存放候選集

2 While not Stack.is Empty（）do ／ ／以深度優先遍歷索引

3N＝Stack.pop（）；

4 Ifd（q，N）＜r／ ／ 若結點在查詢范圍之內

5 If qk∩Nk ≠?／ ／若查詢關鍵詞與結點包含的關鍵詞相交

6 Ifqtq∩Ntq≠?／ ／ 若查詢時間段與結點包含的時間段相交

7 If N.is Leaf（）then

8 For eachoinNdo

9 Ifqk∩ok≠?

10 Ifqtq∩otq≠?

11C←NewPriorityQueue； ／ ／按照TSKR的非遞減順序初始化優先隊列

12C.Enqueue（o）；／ ／將對象o放入候選集優先隊列中

13 Else

14 Stack.push（N.ChildNode）；／ ／將孩子結點進棧

15 end While

16R←NewPriorityQueue； ／ ／按照TSKR 的非遞減順序初始化優先隊列

17R＝dominateCompting（q，C）； ／ ／對候選集中的對象進行支配計算

18 returnR；

算法1 是基于時間的空間文本關鍵詞skyline查詢的具體過程。 第2－3 行以棧的方式維護索引，第4－7 行對查詢范圍內的結點進行判斷，篩選出查詢關鍵詞與結點包含關鍵詞相交以及查詢時間段與結點包含時間段相交的結點，直到遍歷至葉子結點。第8－12 行遍歷葉子結點，篩選出查詢關鍵詞與對象包含關鍵詞相交以及查詢時間段與對象包含時間段相交的對象，將對象放入TSKR 的非遞減候選集優先隊列中。 第16－18 行將候選集中的對象進行支配計算，把不被支配的對象放入結果集隊列中。由于第17 行中dominateCompting（）算法需要判斷所有候選對象間的支配關系，導致算法整體查詢效率下降，因此需要加入高效的裁剪策略來提升查詢效率。

算法2dominateComputing（）算法

輸入候選集C、查詢點q、查詢關鍵詞qk、查詢時間段qtq

輸出查詢結果集R

1 R←getCFirst（）；／ ／將C中首個出隊列對象放入結果集中

2 While notC.isEmpty（）do

3o＝C.Dequeue（）；

4 If sp NumericTypeDominateo／ ／判斷結果集中的對象sp 是否數值型信息支配對象o

5 contine；

6 Else

7 insertointoR

8 end While

9 returnR

算法2 是判斷候選集對象間支配關系的裁剪算法。 第1 行是將候選集中首個出隊列對象放入結果集中。 第2－3 行若候選集隊列非空時，依次取出候選集中的對象進行判斷，第4－7 行若候選對象被結果集中的對象基于時間的空間文本關鍵詞支配則刪除候選對象，否則將對象放入結果集中。

以圖1、表2～表5 中包含的數據為例， 假設查詢關鍵詞為k1、k2、k4， 生成對應二進制簽名文件為110 100 00，查詢時間段為10：00－12：00，默認各結點在查詢范圍之內，并且數值型屬性的要求為人均價格低、用戶評分高。 具體查詢過程如下：

首先，篩選出查詢關鍵詞和查詢時間與對象的關鍵詞和時間相交的候選對象。 從根節點開始，將查詢二進制簽名文件與結點包含的簽名文件進行and 操作，110 100 00 and 110 111 11 ＝110 100 00表示根節點包含查詢關鍵詞，并且根節點的時間段包含查詢時間段，然后對其孩子結點進行重復判定，110 100 00 and 110 101 01 ＝110 100 00 表示結點N5包含查詢關鍵詞，并且結點N5的時間段包含查詢時間段，110 100 00and100 111 11＝100 100 00 表示結點N6不包含查詢關鍵詞，則對N6及其孩子結點進行裁剪，不必進行后續判定提高了查詢效率，繼續對結點N5的孩子結點N1、N2進行判斷，110 100 00 and 110 101 00＝110 100 00 表示結點N1包含查詢關鍵詞，并且結點N1的時間段包含查詢時間段，110 100 00 and 010 101 01＝010 100 00 表示結點N2不包含查詢關鍵詞，直接進行剪枝，此時得到葉子結點N1中的對象o1、o2、o5，由于o1的時間段與查詢時間段不相交，刪除o1，而o2、o5滿足查詢關鍵詞與查詢時間都相交，此時得到候選集對象o2、o5。

之后，判斷候選對象間的支配關系。 假設查詢點與對象o2、o5的空間距離分別為1、2，根據計算o2、o5的TSKR 分別為1.2、2.4， 將o2、o5按照TSKR的非遞減順序放入候選集隊列中，將第一個出隊列的對象o2直接加入結果集中，然后o5出隊列，由于o2與o5間不能構成數值型信息支配，因此將o5加入結果集中，此時遍歷完所有候選對象，得到最終結果集｛o2、o5｝。

5 實驗結果與分析

實驗采用的硬件設備為64 位Windows 10 操作系統，Intel （R） Core （TM） i5 － 7200U CPU ＠2.50 GHz處理器，8 G 內存；采用Java 語言實現算法，集成開發環境為IntelliJ IDEA Community Edition 2021.1.3，JDK 版本為11.0.11。

實驗數據來源于yelp 網站的開源數據集，該數據集中包括克利夫蘭、多倫多等11 個城市150 346個商戶的信息。 實驗將數據集中的經緯度作為對象的空間位置信息，價格、星級等作為對象的數值型信息，商戶的分類作為對象的關鍵詞信息，營業時間作為對象的時間信息。 通過是否使用裁剪策略TSTKSQ 與NTSTKSQ 測試算法的有效性，每次測試均取相同環境下10 次測試的平均值為最終結果。

5.1 查詢關鍵詞數量的影響

為了測試查詢關鍵詞的數量對算法的影響，設置數值型屬性為2 維，查詢點的空間位置和查詢時間段固定不變，查詢關鍵詞1 ～5 個。 查詢關鍵詞數量變化對算法的影響如圖2 所示。

圖2 查詢關鍵詞數量的影響Fig. 2 Impact of the number of query keywords

從圖2 中可知，隨著查詢關鍵詞數量的增加，算法整體的運行時間也不斷增加。 對于不使用裁剪策略NTSTKSQ 進行查詢時，算法需要遍歷所有數據集中的對象，將查詢關鍵詞與每個對象包含的關鍵詞一一比較，直到篩選出所有包含查詢關鍵詞的對象，而隨著查詢關鍵詞數量的增加，包含查詢關鍵詞的對象也越來越多，因此整體查詢時間呈上升趨勢，而使用裁剪策略TSTKSQ 進行查詢時，算法的查詢時間明顯少于使用裁剪策略NTSTKSQ 的查詢時間。由于使用裁剪策略TSTKSQ 時，算法根據STTRTree 結點的簽名文件進行操作時，提前裁剪了不包含查詢關鍵詞的結點，不必進行后續的判斷，因而極大地提升了算法的執行效率。

5.2 數值型屬性維度的影響

為了測試數值型屬性維度對算法的影響，設置了2 個查詢關鍵詞，查詢點的空間位置和查詢時間段固定不變，數值型屬性維度從1 維變化到5 維。數值型屬性維度的變化對算法的影響如圖3 所示。

圖3 數值型屬性維度的影響Fig. 3 Impact of numerical attribute dimensions

從圖中可知，隨著數值型屬性維度的增加，算法整體的運行時間呈上升趨勢。 對于不使用裁剪策略NTSTKSQ 進行查詢時，算法需要遍歷所有數據集中的對象，判斷對象間的數值型信息支配關系，而隨著數值型屬性維度的增加，對象間的數值型信息支配判斷次數也不斷增加，因此整體查詢時間也不斷增加；而對于使用裁剪策略TSTKSQ 進行查詢時，算法的查詢時間明顯少于不使用裁剪策略NTSTKSQ 的查詢時間。 因為使用裁剪策略TSTKSQ 時，算法過濾了大部分查詢關鍵詞和查詢時間不匹配的對象，大大減少了候選集對象間數值型信息支配次數的判斷，縮短了整體支配判定的時間。

5.3 查詢時間段大小的影響

為了測試查詢時間段大小對算法的影響，設置查詢關鍵詞為2 個，數值型屬性為2 維，查詢點的空間位置固定不變，查詢時間段不斷增加。 查詢時間段的變化對算法的影響如圖4 所示。

圖4 查詢時間段大小的影響Fig. 4 Impact of query time period size

從圖中可知，隨著查詢時間段不斷增加，算法整體的運行時間呈上升趨勢。 對于不使用裁剪策略NTSTKSQ 進行查詢時，算法需要遍歷所有數據集中的對象，將查詢時間段與每個對象包含的時間段一一比較，直到篩選出所有包含查詢時間段的對象，而隨著查詢時間段大小的增加，包含查詢時間段的對象也越來越多，需要比較的次數也不斷增加，因此整體查詢時間呈上升趨勢，而對于使用裁剪策略TSTKSQ 進行查詢時，算法的查詢時間明顯少于不使用裁剪策略NTSTKSQ 的查詢時間。 因為使用裁剪策略TSTKSQ 時，算法根據STTR－Tree 結點包含的時間信息進行匹配時裁剪了不包含查詢時間段的結點，算法因此過濾了大部分不包含查詢時間段的對象，極大地減少了查詢時間。

6 結束語

為了解決用戶在實踐中更多偏好查詢的需求，本文提出了基于時間的空間文本關鍵詞skyline 查詢TSTKSQ，同時考慮了空間距離、數值型信息、關鍵詞和時間等4 個屬性，并構建了相應的空間索引STTR－Tree，同時設計了時空關鍵詞相關性評價函數，以此來衡量一個對象的優劣程度，然后，提出了結點和對象的裁剪策略，并在此基礎上提出了高效的skyline 查詢算法。 最后，在真實數據集上進行測試，實驗結果表明所提算法能夠有效地解決基于時間的空間文本關鍵詞skyline 查詢問題。 之后的工作考慮將TSTKSQ 應用于道路網中，進一步研究道路網中TSTKSQ 問題的解決方法。