已知时间的空间文本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查询做进一步的应用研究。