基于時間的空間文本關(guān)鍵詞skyline 查詢

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

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

0 引 言

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

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

表1 飯店信息Tab. 1 Hotel information

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

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

1 相關(guān)工作

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

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

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

2 問題定義

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

2.1 空間距離

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

2.2 關(guān)鍵詞相關(guān)性

假設(shè)查詢關(guān)鍵詞有n個，對象包含的關(guān)鍵詞有m個，則有

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

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

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

2.3 時間相關(guān)性

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

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

2.4 時空關(guān)鍵詞相關(guān)性

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

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

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

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

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

定義3（基于時間的空間文本關(guān)鍵詞skyline）

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

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

3 STTR－Tree 索引

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

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

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

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

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

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

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

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

表4 數(shù)值型信息Tab. 4 Numerical information

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

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

4 算法描述

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

4.1 裁剪策略

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

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

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

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

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

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

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

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

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

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

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

證明根據(jù)優(yōu)先隊列的性質(zhì)可知，TSKR（q，o） ≤TSKR（q，o′），根據(jù)定義2 可知，o?TSTKo′。

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

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

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

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

4.2 算法

算法1TSTKSQ 算法

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

輸出查詢結(jié)果集R

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

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

3N＝Stack.pop（）；

4 Ifd（q，N）＜r／ ／ 若結(jié)點在查詢范圍之內(nèi)

5 If qk∩Nk ≠?／ ／若查詢關(guān)鍵詞與結(jié)點包含的關(guān)鍵詞相交

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

7 If N.is Leaf（）then

8 For eachoinNdo

9 Ifqk∩ok≠?

10 Ifqtq∩otq≠?

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

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

13 Else

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

15 end While

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

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

18 returnR；

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

算法2dominateComputing（）算法

輸入候選集C、查詢點q、查詢關(guān)鍵詞qk、查詢時間段qtq

輸出查詢結(jié)果集R

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

2 While notC.isEmpty（）do

3o＝C.Dequeue（）；

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

5 contine；

6 Else

7 insertointoR

8 end While

9 returnR

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

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

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

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

5 實驗結(jié)果與分析

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

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

5.1 查詢關(guān)鍵詞數(shù)量的影響

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

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

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

5.2 數(shù)值型屬性維度的影響

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

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

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

5.3 查詢時間段大小的影響

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

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

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

6 結(jié)束語

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