利用k-d树索引改进数据流skyline查询算法

唐颖峰, 陈世平

1(上海理工大学 管理学院,上海 200093) 2(上海对外贸经贸大学 教务处,上海 201620)

1 引 言

作为一种重要的数据挖掘技术,skyline查询[3]近来引起了研究者们的广泛关注.面向数据流的skyline查询在交通数据的分析中应用广泛,如基于位置的服务、最佳路线规划与推荐[4-9]等等.近年来,国内外研究者对数据流上的skyline查询问题进行了研究,Lin等人[10]最早研究了数据流上的skyline查询问题,针对数据流中最近的N个元素计算任意最近n(n≤N)个元素的skyline点集合.Tao等人[11]提出了两种方法(Lazy和Eager)用于维持数据流滑动窗口的skyline,但是算法中组织数据点的R-树[12]所产生MBR的重叠使得算法的搜索效率低下.Sun等人[13]对Eager算法进行了改进,提出了StreamSubsky算法,算法采用网格索引来组织数据点,提高了数据点的更新效率.此后,研究者们又针对不同的应用场景,从不同角度对面向数据流的skyline查询问题进行了研究.Tian和Zhang等人[14,15]研究了任意顺序随机增删的数据流上的skyline查询;Zhan等人[16]对面向分布式数据流的K-Skyband连续查询进行了研究;Zhao等人[17]对连续子空间的概率skyline查询进行了研究;Liu等人[18]对不确定数据流上的概率skyline查询进行了研究;Guo等人[19]面向数据流的skyline组查询进行了研究.这些研究所提出的算法均采用网格索引或者R-树索引.

现有的基于网格索引的算法存在较大不足:算法需要事先确定网格宽度K,算法的性能很大程度上依赖于K的合理取值,而实际应用时往往难以确定适合的初始K值;网格宽度K在算法初始时已经固定,网格大小不会随到达数据点的分布情况动态变化,使得算法的自适应性和稳定性较差,难以应对数据点分布变化的高速数据流查询的应用场景,如智能交通系统[1,2]中的数据流等.

本文对现有的面向数据流的skyline增量更新算法进行优化,提出一种基于k-d树的算法kdStreamSky,以一种新型索引结构k-d树来组织数据流对象,并针对此结构提出剪枝规则,来实现增量数据点的高效更新.k-d树的组织无需预先指定空间划分尺度,索引区域的划分根据当前数据点的分布情况自动动态调整,以提高算法的自适应性、稳定性和计算效率,使算法适用于数据点分布变化的高速数据流查询.

2 相关概念

令A1,A2,…,Ad是d个全序集,记全序关系为≤;S=A1×A2×…×Ad是一个d维数据空间,称A1,A2,…,Ad为空间S的属性或维;令包含n个数据点的集合D={p1,p2,…,pn},其中任意数据点pi均来自空间S,将pi在属性Ai上的取值记为pi.ai.

定义1(支配).任意给定两个数据点p,q∈D:如果对于∀Ai∈A,有p.ai≤q.ai;且∃Aj∈A,有p.aj

定义2(skyline).集合D中所有不被其他任意数据点所支配的数据点组成的集合称作D上的skyline集合,若以SK(D)表示skyline集合,则有SK(D)={p∈D|∀q∈D:q≮ p}.

定义3(有效数据点).将数据点p到达系统的时间戳记为p.tarr,不妨设p.tarr为整数,由0开始递增.设一时间窗口大小为W,系统当前时间戳为tn,则当p.tarr∈[tn-W,tn]时,p为有效数据点,否则为过期数据点.

定义4(活动数据点).若有效数据点p满足条件p.tarr≥q.tarr,其中q∈{q |q∈D,q

定义5(影响时间).设任意活动数据点p∈D,活动数据点集合Q={q |q∈D,q

3 算法的概要设计

3.1 算法数据结构

在kdStreamSky算法中,活动数据点以列表的形式存储,称为活动点列表(active point list,简称APL),APL中每个点设置标识,标识该数据点当前是否属于skyline集合;对于用户提交的查询请求,将返回APL中当前标识属于skyline集合的数据点.

kdStreamSky算法沿用文献[11]中Eager算法中所采用的事件链机制.该机制的优点在于,可以在当前窗口上的skyline数据点过期后,直接输出其“继任者”而避免计算其排它支配域上的skyline.事件链(event list,简称EL)是由按时间顺序排列的节点构成的列表,事件链的节点存储同一时间发生的若干事件,事件链处理函数依次对当前时间戳对应的事件链节点中的事件进行处理.事件e可表示为一个三元组e={p,t,o},其中p为事件对应数据点的地址,t为事件发生的时间戳,o为处理事件时要进行的操作方式.算法预先计算数据点p可以加入skyline集合的最早时间或其过期时间t(即影响时间),将p对应事件e加入到事件链对应时间t的节点中.事件链处理函数根据当前时间点中事件e的操作方式o,将对应数据点p加入skyline集合或将其淘汰.

kdStreamSky算法采用k-d树对数据点进行索引.k-d树是一棵满二叉树,树的每个非叶节点代表空间的特定区域,该节点的左右孩子在某一维将该区域分割成两部分;树的每个叶节点代表一个数据点.

kdStreamSky算法中k-d树的节点结构设计如下:

KD_tree

{ KD_tree LeftChild;

KD_tree RightChild;

List

IncludedPoints;

Array UpperBound;

Array LowerBound;

Array AreaUpperBound;}

其中,LeftChild和RightChild存储节点左、右子树的地址,叶节点左、右子树为空.IncludedPoints列表存储当前节点区域中所包含的所有数据点的地址,列表中的数据点地址按照数据点到达的时间戳排序;特别地,当节点为叶节点时,列表中只包含一个数据点的地址.d维向量UpperBound存储该节点所代表区域中全部数据点的最大属性值;而LowerBound则存储该节点所代表区域中全部数据点的最小属性值.d维向量AreaUpperBound存储区域分割所产生的该节点对应区域的最大边界值.

根据k-d树的构造规则,可以得到如下性质:

性质1.(完备性)k-d树的任一非叶节点所代表的区域包含其左右孩子中所包含的全部数据点.

性质2.(互斥性)对于k-d树任意一层,空间内的任意一点p只包含于这一层的其中一个节点.

性质3.(时序性)k-d树上任意节点Q所包含数据点的最大时间戳不小于其任意一孩子所包含数据点的最大时间戳.

由性质1、性质2可知,完全访问k-d树的任意一层节点即可保证空间内的全部数据点均被访问,且只被访问一次.因此,采用k-d树索引数据空间是完备且有效率的.

定理1.对于任意数据点p,k-d树的任意节点Q,若p证明:p由定理1和性质3可以得到访问及更新k-d树的剪枝规则1-4.

剪枝规则1.设有新到达数据点p,k-d树上任一节点Q,满足p

剪枝规则2.设有新到达数据点p,k-d树上任一节点Q,满足p≮ Q.UpperBound,则Q及其子节点均无需从k-d树上删除.

剪枝规则3.若新到达数据点p被k-d树上任一节点Q的属性值上界支配,则更新p的影响时间为Q中时间戳最大数据点的过期时间.

剪枝规则4.若k-d树上任一节点Q中数据点的最大时间戳不大于最近更新新到达数据点p影响时间的数据点的时间戳,则Q及其全部子节点都不更新p的影响时间.

综上所述,算法的数据结构包括三部分:活动点列表APL,事件链EL以及k-d树索引.

3.2 算法的处理流程

算法的总体流程分为三种情况进行相应的处理:

1)当新的数据点p到达时,先以p遍历k-d树,利用剪枝规则1和2对k-d树进行剪枝,将非活动的点从系统中删除;再利用剪枝规则3和4计算p的影响时间,同时可以得到p是否在skyline集合的标识;根据p的影响时间生成相应事件,并加入事件链中;最后将p的地址更新到k-d树上.

2)当时间戳发生跳变时,调用时间处理函数对事件链中的相应事件进行处理.

3)当用户提交查询时,将当前时刻APL中当前标识为skyline集合内的数据点返回给用户.

4 算法的详细实现

4.1 k-d树的剪枝

此过程目的是在k-d树中找出非活动数据点,并将其从系统中删除.采用深度优先遍历k-d树的方式,找到被当前到达数据点p支配的区域,并删除该区域内的全部数据点.遍历过程中利用剪枝规则1和2,缩小搜索区域,以提高剪枝效率.k-d树剪枝算法描述见算法1.

算法1.k-d树剪枝算法

输入:剪枝前的k-d树及当前到达数据点p

输出:剪枝后的k-d树

步骤:

由根节点开始深度优先遍历k-d树,当前被访问的节点为Q,其兄弟节点为B,父节点为P;

if p < Q.UpperBound

if p≮Q.LowerBound

继续访问Q.LeftChild及Q.RightChild;

if p

若Q为右孩子,则向下更新B对应子树的

AreaUpperBound为P.AreaUpperBound;

用B替代P节点,并向上递归更新P.LowerBound

以及P.IncludedPoints;

删除Q及其孩子;

删除Q.IncludedPoints在APL中对应的数据点;

删除事件链中Q.IncludedPoints数据点的对应事件;

if p≮Q.UpperBound

if Q为根节点

return;

else

继续访问Q.LeftChild及Q.RightChild;

4.2 计算影响时间

此过程用以计算新到达数据点p的影响时间,以深度优先方式遍历k-d树,找出所有支配数据点p的活动数据点中时间戳最大的数据点q,将q的过期时间作为p的影响时间.通过遍历k-d树,可以判别数据点p是否属于skyline,若是,则p的影响时间为其过期时间.遍历过程中利用剪枝规则3和4,缩小搜索区域,以提高计算.p的影响时间计算算法描述见算法2.

算法2.影响时间计算算法

输入:当前到达数据点p

输出:p的影响时间p.teff

步骤:

p.teff=p.tarr+W;

初始化对p的影响时间进行更新的数据点的时间戳t=0;

由根节点开始深度优先遍历k-d树,当前被访问的节点为Q,其兄弟节点为B;

if max(Q.IncludedPoints.tarr)<=t

if Q为根节点或右孩子

return;

else 继续访问B;

else

if p

if Q为根节点或右孩子

return;

else 继续访问B;

if Q.UpperBound

t=max(Q.IncludedPoints.tarr);

p.teff=t+W;

if Q为根节点或右孩子

return;

else 继续访问B;

else

if Q为非叶节点

继续访问Q.LeftChild及Q.RightChild;

else

if Q为右孩子

return;

else 继续访问B;

4.3 事件链更新及事件处理

数据点影响时间计算完成后,生成相应的事件加入到事件链的相应位置.设事件为e,e的操作类型e.op分为两种:ex代表将当前数据点过期操作;pm代表将当前数据点加入skyline集合操作.则时间链更新算法描述见算法3.

算法3.事件链更新算法

输入:计算影响时间后的数据点p及更新前的事件链 EL

输出:更新后的事件链EL

步骤:

if p.teff>= p.tarr+W

e={p,p.teff,ex};

else

e={p,p.teff,pm};

将事件e加入到EL[p.teffmod W];

当时间戳发生变化时,事件链处理过程即被触发,并对事件链中当前时间戳的节点中的事件进行处理.设事件e对应的数据点为e.p,操作类型为e.op,算法描述见算法4.

算法4.事件处理算法

输入:当前时间戳t,事件链EL

输出:更新后的事件链EL

步骤:

while EL[t mod W]非空

从EL[t mod W]中取出事件e;

if e.op==ex

将e.p从APL中删除;

将e.p从k-d树中删除;

if e.op==pm

将e.p在APL的skyline标识为设置为true;

新建一个事件e′={e.p,e.p.tarr+W,ex}加入到EL[e.p.tarr+W mod W]中;

将e从EL中删除;

4.4 k-d树更新

新到达数据点p的影响时间计算完成后,要将p更新到k-d树上.k-d树更新算法描述见算法5.

算法5.k-d树更新算法

输入:更新前的k-d树及当前到达数据点p,p的各属性 值记为p.attr

输出:更新后的k-d树

步骤:

从根节点深度优先遍历k-d树,当前被访问的节点为Q,其兄弟节点为B,父节点为P;

if Q为空

新建节点Q,将p插入Q.IncludedPoints;

Q.LowerBound=p.attr;

Q.UpperBound=p.attr;

Q.AreaUpperBound=p.attr;

return;

if p

if Q非叶节点

将p插入Q.IncludedPoints;

Q.LowerBound=min(p.attr,Q.LowerBound);

Q.UpperBound=max(p.attr,Q.UpperBound);

继续访问Q.LeftChild;

if Q为叶节点

计算p与Q.IncludedPoints中数据点q各属性的方差,找到方差最大的属性a作为区域分割属性;

新建两个节点M和N;

M.AreaUpperBound=Q.AreaUpperBound;

N.AreaUpperBound=Q.AreaUpperBound;

M.AreaUpperBound.a=min(p.attr.a,q.attr.a);

M.UpperBound= p.attr.a>=q.attr.a? q.attr:p.attr;

M.LowerBound= p.attr.a>=q.attr.a? q.attr:p.attr;

N.UpperBound= p.attr.a<=q.attr.a? q.attr:p.attr;

N.LowerBound= p.attr.a<=q.attr.a? q.attr:p.attr;

M.UpperBound.a=min(p.attr.a,q.attr.a);

N.UpperBound.a=max(p.attr.a,q.attr.a);

将p插入Q.IncludedPoints;

Q.LowerBound=min(p.attr,q.attr);

Q.UpperBound=max(p.attr,q.attr);

Q.LeftChild=M;

Q.RightChild=N;

return;

if p≮Q.AreaUpperBound

if Q非根节点

则继续访问B节点;

if Q为根节点

找出p.attr比Q.AreaUpperBound大的属性集A,计算p.attr与Q.AreaUpperBound在A上的方差,找到方差最大的属性a作为分割属性;

新建两个节点M和N;

M.LowerBound=min(p.attr,Q.LowerBound);

M.UpperBound=max(p.attr,Q.UpperBound);

N.UpperBound= p.attr;

N.LowerBound= p.attr;

M.AreaUpperBound=max(p.attr,

Q.AreaUpperBound);

N.AreaUpperBound= max(p.attr,Q.

AreaUpperBound);

M.LeftChild= Q;

M.RightChild=N;

更新Q子树在A上除属性a之外AreaUpperBound为p.attr;

M.IncludedPoints=Q.IncludedPoints;

将p插入M.IncludedPoints及N.IncludedPoints;

return;

5 算法分析

本文将对比分析网格索引和k-d树索引的访问复杂度.以一次支配检测的时间作为单位时间进行时间复杂度分析.

为方便比较,假设网格结构G为d维,每一维划分为n等分,则G的网格总数为nd.k-d树则假设为一个标准k-d树,即从根节点开始向下,每一层顺次以空间的一维对当前节点对应空间进行分半划分,持续划分直到叶节点总数为nd,此时k-d树的层数为ln(nd).

在网格索引中,对于一个新到数据点p,若要确定p与已有数据点间的支配关系,需要进行两部分的支配检测:网格间的支配检测和网格内数据点的支配检测.网格间的支配检测即是以p所在的网格g与其他网格进行支配检测,排除与g中数据点可以确定支配关系的网格,找出无法确定支配关系的网格集合G*,其复杂的表示为Cg.网格内数据点的支配检测即为p与网格集合G*内所包含的所有数据点逐一进行支配检测,其复杂的表示为Cgp.设网格索引的访问复杂度为CGI,则可表示为:

CGI=Cg+Cgp

(1)

定理2.设p所在网格g1={a1,a2,…,ad},若任意其他网格g2={b1,b2,…,bd},∃i∈{1,2,…,d},使得ai=bi;则g2

∈G*.

由定理2可知,G*中的网格数量为nd-(n-1)d.

在网格索引中,要求出G*,需要用p所在网格与其他网格逐一进行支配检测,因而Cg=O(nd);而网格内数据点的支配检测则是用p与G*内的数据点逐一进行支配检测,设数据点总数为M,则每个网格内的平均数据点数为M/nd,可得Cgp=O(M(nd-(n-1)d)/nd).

对于给定的k-d树,确定p与已有数据点间的支配关系,也需要进行两步操作:首先由根节点遍历k-d树,排除其中数据点可以与p确定支配关系的分枝,找出无法确定支配关系的叶节点集合L,其复杂的表示为Ct.然后再用p与L中所包含的数据点逐一进行支配检测,其复杂的表示为Clp.因此给定k-d树的访问复杂度CKD可表示为:

CKD=Ct+Clp

(2)

由于给定k-d树的叶节点数为nd,即给定k-d树最终将数据空间均等划分为nd个子空间,每个叶节点代表的子空间与网格结构中的每个网格一一重合,有L=G*,即Clp= Cgp=O(M(nd-(n-1)d)/nd),因此要比较CGI和CKD的大小,只需比较Cg和Ct的大小即可.

在k-d树索引中,求集合L可以分为两个过程:首先从根节点以深度优先遍历k-d树,标记k-d树每一层中数据点p所在区域对应的节点;然后自顶向下层次遍历k-d树,对于k-d树的每一层中的节点,以被标记节点对同层其余节点进行支配检测,相当于k-d树的每一层节点将空间划分为一个网格结构,若被检测节点满足定理2的条件则保留,否则连同孩子一起删去,依次遍历到最底层,被保留的叶节点集合即为L.因此Ct即为检测每一层满足定理2条件的节点的时间总和.

设遍历k-d树的第i层为对空间第k维的第l次划分,第i层满足定理2条件的节点数量为Ni,则可将空间的各维分为两类:

1)第l次未划分的维,其数量为d-k;

2)第l次已划分的维,其数量为k;

由此可得:

Ni=2(l-1)(d-k)*2lk-(2(l-1)-1)(d-k)*(2l-1)k

≤2ld-(2l-1)d≈d*2l(d-1)

(3)

而根据给定k-d树的划分规则,有:

l=⎣i/d」≤i/d

(4)

将式(4)代入式(3)可得:

(5)

设遍历到最后一层所访问的总节点数为N,则有:

(6)

将式(5)代入式(6)可得:

N≤d2lnn*n(d-1)

(7)

由式(7)可知,当满足式(8)条件时有N≤nd,即有Ct≤Cg,进而有CKD≤CGI.而若将d2看做常数,当n充分大时,显然总能找到一个数n′,使得当n≥n′时,满足式(8)条件.因此可得,当n较大时,k-d树索引在skyline计算问题上的访问效率优于网格索引.

d2lnn≤n

(8)

以d=2为例,当n=256时,网格索引中Cg=2562=65536;而根据式(3)及式(6)计算可得,k-d树索引中Ct=1769,k-d树索引的访问效率比网格索引高出近37倍.

6 实验及结果分析

为了保证计算结果的准确性,本文讨论的算法采取同步响应的方式,即每次查询提交后,系统需将缓存中当前时间窗口内的数据点全部处理后,再响应查询请求,返回计算结果.因此,新到达数据点的更新时间直接影响查询响应时间,而查询响应时间也是反映实时系统性能的重要指标.因此本文采用查询响应时间作为标准来衡量算法的实际性能.

实验环境为Intel Core i5 2.8GHz处理器,2GB内存,260GB磁盘空间,操作系统采用CentOS6.2.在上述实验环境中对Eager、StreamSubsky和kdStreamSky三种算法进行了实现,并对实验测定结果进行对比分析.

实验数据分别采用标准数据和实际交通数据进行.标准数据采用文献[3]中的标准数据生成工具生成.实际交通数据则采用北京市的真实道路网数据*数据来源: http://www.datatang.com/data/45422,共433391条路段信息,顶点数共计171504个.在此道路网上随机生成30000个固定对象,并设置一个移动对象沿道路网移动,记录移动对象500m半径范围内的固定对象与其的路径长度以及其他随机产生的3维非空间属性值,形成一个4维点集数据流.由于移动对象半径范围内的固定对象数会随着移动对象的移动而变化,因此对应数据流呈现出疏密分布随时间变化的特点.

实验中,标准数据流的流速保持恒定;实际交通数据流中,移动对象的移动速度保持恒定;查询响应时间取相同条件下10次测定结果的平均值;由于StreamSubsky算法的性能与网格宽度相关,本文实验中按照文献[13]中的最优化规则对其网格宽度进行设置.

对于标准数据,在不同的数据维度、数据规模及数据流速条件下,对三种算法的查询响应时间进行了测定.

图1所示为三种算法在不同数据维度下的查询响应时间,其中数据规模为300K,数据流速为300点/秒.由于采用了效率较高的索引结构,StreamSubsky和kdStreamSky相比Eager,在不同数据维度下的性能都有着明显的优势,kdStreamSky比StreamSubsky在低维度上有更好的表现;随着数据维度的增加,三种算法的性能逐渐接近且趋于稳定,这是因为在数据规模恒定条件下,当数据维度增加到一定程度,三种算法的索引结构都会逐渐失效,支配检测时间接近于逐点检测的时间.

图1 三种算法在不同数据维度下的查询响应时间Fig.1 Query response time with different dimesion

图2所示为三种算法在不同数据规模下的查询响应时间,其中数据维度d=4,数据流速为300点/秒.三种算法中,StreamSubsky和kdStreamSky的在不同数据规模下均比Eager存在较大的性能优势;而相比StreamSubsky,kdStreamSky在数据规模较小时,由于需要花费更多的时间维护k-d树索引,因而性能略差,但随着数据规模的增大,其查询响应时间的增长相对平缓,表现出较为明显的优势.

图2 三种算法在不同数据规模下的查询响应时间Fig.2 Query response time with different cardinality

图3所示为三种算法在不同数据流速下的查询响应时间,其中数据维度d=4,数据规模为300K.三种算法中,StreamSubsky和kdStreamSky同样比Eager具有较大优势.kdStreamSky比StreamSubsky在不同数据流速下均有更好的表现,且随着数据流速增大,kdStreamSky的优势更明显.

图3 三种算法在不同数据流速下的查询响应时间Fig.3 Query response time with different data flow velocity

对于实际交通数据,在移动对象保持在5m/s的条件下每隔5s进行一次查询,对三种算法的查询响应时间进行测定;在移动对象不同的移动速度条件下,对三种算法的平均查询响应时间进行了测定.

图4所示为三种算法在移动对象保持恒定移动速度下的查询响应时间.三种算法中,kdStreamSky算法的查询响应时间优于另外两种算法;StreamSubsky算法的响应时间呈现出较大的波动,这主要是因为StreamSubsky算法的索引采用固定的网格宽度,其查询性能受到数据点疏密分布变化的影响较大,相比之下kdStreamSky则呈现出较好的自适应性,查询响应时间基本保持稳定.

图5所示为三种算法在移动对象不同的移动速度条件下的平均查询响应时间.由于时间窗口内的数据点数量随着移动对象的移动速度增大而增加, 因此三种算法的查询响应时间均随着移动对象的移动速度增大而增加.kdStreamSky算法相比另外两种算法均保持较大的优势.

图4 三种算法在移动对象恒定移动时的查询响应时间Fig.4 Query response time when main object keep uniform

图5 三种算法在移动对象不同移动速度下的平均查询响应时间Fig.5 Average query response time with different object moving speed

综上所述,相比StreamSubsky算法和Eager算法,kdStreamSky算法在标准数据环境有着较好的性能表现;在实际交通数据环境下则呈现出良好的自适应性以及明显的性能优势,更适用于疏密分布变化较大的交通数据流skyline查询任务.

7 结 论

本文提出一种基于k-d树的数据流skyline增量更新算法kdStreamSky.该方法通过事件链机制对增量数据点的状态转换进行预计算,通过事件的处理对数据点的状态进行更新;采用一种新型的索引结构k-d树对数据点进行索引,该索引无需指定任何初始参数,且能够根据数据流中数据点分布的变化自适应调整;并在k-d树结构上提出多个剪枝规则来缩小搜索域,提高了搜索效率;算法能够快速响应用户的查询请求,将数据流在任意时间窗口内的skyline点集合返回给用户.kdStreamSky算法在较大规模及高速数据流有着较好的性能表现,能够更好的适应疏密分布变化的高速数据流分析,适用于智能交通系统中数据流skyline查询任务.

kdStreamSky算法与其他同类基于索引结构的算法在处理高维数据时均会遇到索引失效的情况,因此单机处理能力有限,算法并行化是必然趋势;同时,智能交通系统中数据流也多为分布式数据流,因此下一步的工作是将算法扩展分布式数据流环境,并将算法进行并行扩展,以适应智能交通系统中数据流实时分析的需求.

[1] Ichiro Masaki.A brief history of ITS[R].USA:Massachusetts Institute of Technology,1999.

[2] Wang Guo-feng,Song Peng-fei,Zhang Yun-ling.Review on development status and future of intelligent transportion system[J].Highway,2012,5(5):217-222.

[3] Borzsonyi S,Kossmann D,Stocker K.The skyline operator[C].Proceedings of the 17th International Conference on Data Engineering,2001:421-430

[4] Fu X,Miao X,Xu J,et al.Continuous range-based skyline queries in road networks[J].World Wide Web：Internet and Web Information Systems,2017，20(6):1443-1467.

[5] Chen Y,Lee C.Skyline path queries with aggregate attributes[J].IEEE Access,2016,4(9):4690-4706.

[6] Xie Jia-meng,Peng Hong,Zhou Bing,et al.Analysis of intelligent traffic information and research on decision support based on data mining techniques [J].Highway,2004,4(4):154-158.

[7] Kriegel H P,Renz M,Schubert M.Route skyline queries:a multi-preference pathplanning approach[C].Proceedings of the 26th International Conference on Data Engineering,2010.

[8] Zheng B,Lee K,Lee W.Location-dependent skyline query[C].Proceedings of the International Conference on Mobile Data Management MDM,2008.

[9] Kodama K,Iijima Y,Guo X,et al.Skyline queries based on user locations and preferences for making location-based recommendations[C].Proc of the 1st ACM SIGSPATIAL Int Workshop on Location Based Social Networks,2009.

[10] Lin X,Yuan Y,Wang W,et al.Stabbing the sky:efficient skyline computation over sliding windows[C].Proceedings of the 25th International Conference on Data Engineering,2005:502-513.

[11] Tao Y,Papadias D.Maintaining sliding window skylines on data streams[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(3):377-391.

[12] Guttman A.R-tree:a dynamic index structure for spatial searching[J].Proc.ACM-CIGMOD Int.Conf.on Management of Data,1994,14(2):47-57.

[13] Sun Sheng-li,Huang Zhen-hua,et al.Efficient computation of subspace skylines over data streams[J].Chinese Journal of Computers,2007,30(8):1418-1428.

[14] Tian Li,Zou Peng,et al.Grid index based algorithm for continuous skyline computation[J].Chinese Journal of Computers,2008,31(6):998-1012.

[15] Zhuang Li,Zou Peng,et al.Continuous dynamic skyline queries over data stream[J].Journal of Computer Research and Development,2011,48(1):77-85.

[16] Zhan Yan-pu,Zhao Lei.Grid index based continuous k-skyband query algorithm over distributed data streams[J].Journal of Chinese Computer Systems,2014,35(2):233-238.

[17] Zhao L,Yang Y,et al.Continuous probabilistic subspace skyline query processing using grid projections[J].Journal of Computer Science & Technology,2014,29(2):332-344.

[18] Liu C,Tang S.An effective probabilistic skyline query process on uncertain data streams[J].Procedia Computer Science,2015,63(2):40-47.

[19] Guo X,Li H,Wulamu A,et al.Efficient processing of skyline group queries over a data stream[J].Tsinghua Science and Technology,2016,21(1):29-39.

附中文参考文献：

[2] 王国锋,宋鹏飞,张蕴灵.智能交通系统发展与展望[J].公路,2012,5(5):217-222.

[6] 谢嘉孟,彭 宏,周 兵,等.基于数据挖掘技术的智能交通信息分析与决策研究[J].公路,2004,4(4):154-158.

[13] 孙圣力,黄震华,等.数据流上高效计算子空间Skyine的算法[J].计算机学报,2007,30(8):1418-1428.

[14] 田 李,邹 鹏,等.基于网格索引的连续Skyline计算方法[J].计算机学报,2008,31(6):998-1012.

[15] 张 丽,邹 鹏,等.数据流上连续动态skyline查询研究[J].计算机研究与发展,2011,48(1):77-85.

[16] 詹彦溥,赵 雷.使用网格索引的分布式数据流上K-Skyband连续查询算法[J].小型微型计算机系统,2014,35(2):233-238.