数据流中ρ-支配轮廓查询算法*

2017-07-31王之琼霸建民信俊昌

计算机与生活 2017年7期

关键词：数据量数据流支配

王之琼，霸建民，黄达，信俊昌+

1.东北大学中荷生物医学与信息工程学院，沈阳 110819

2.东北大学计算机科学与工程学院，沈阳 110819

数据流中ρ-支配轮廓查询算法*

王之琼1，霸建民2，黄达2，信俊昌2+

1.东北大学中荷生物医学与信息工程学院，沈阳 110819

2.东北大学计算机科学与工程学院，沈阳 110819

+Corresponding autho author:r:E-mail:xinjunchang@mail.neu.edu.cn

WANG Zhiqiong,BA Jianm in,HUANG Da,etal.ρ-dom inant skyline com putation on data stream s.Journal of Frontiersof Computer Scienceand Technology,2017,11(7)：1080-1091.

数据流上的轮廓查询算法不能直接处理ρ-支配轮廓查询，而传统的ρ-支配轮廓查询无法在数据更新频繁时满足查询处理的实时性需求。因此，提出了数据流上的ρ-支配轮廓查询算法。首先，系统地介绍了完全支配、ρ-支配和ρ-支配轮廓的定义，进而提出了数据流上ρ-支配轮廓的定义。然后，通过深入分析数据流上的ρ-支配轮廓的性质，得出基于时序支配的数据过滤方法，并提出了基于滑动窗口的ρ-支配轮廓查询算法（ρ-dominant skyline query over sliding w indow，DSSW），提高了数据流上的ρ-支配轮廓计算的效率。最后，通过大量的实验证明，DSSW算法相比较于传统的ρ-支配轮廓查询算法，在响应时间及存储空间上均有明显优势。

ρ-支配关系；ρ-支配轮廓；数据流；滑动窗口

1 引言

近年来，轮廓查询[1-3]被广泛地应用于多标准决策中，例如个性化推荐系统、市场监测系统等。给定一个数据点集合P，则数据集P的轮廓是指P中所有不被其他点支配的点的集合。需要指出的是一个点x支配另一个点y必须满足x在所有维上都不比y差，并且至少在一维上x比y好。不失一般性，假设一个小的值比大的值好，在d维数据空间内，点x支配y可以表示为：（1）∀i∈[1,d],x[i]≤y[i]；（2）∃j∈[1,d],x[j]＜y[j]。图1（a）中的点a、f和g由于不被其他任何点支配，就构成了图1（a）的轮廓。

Fig.1 Exampleof traditionalskylineand dynamic skyline图1 传统轮廓与动态轮廓示例图

动态轮廓[4]为传统轮廓的一种变体，致力于在查询点的变换空间中计算轮廓。给定一个d维空间内查询点q，则对于任意一个d维数据p，都可以关于查询点q变换为p′，并且p′满足p′[i]=|p[i]-q[i]|+q[i],i∈[1,d]。图1（b）是图1（a）中以c为查询点的动态轮廓结果，因为点a′和g′在变换空间中不被其他任何点支配，所以点a′和g′构成了此集合的动态轮廓。动态轮廓比传统的轮廓有更广泛的应用，例如在一个电商平台中，如果一个消费者感兴趣的商品已售空，则电商平台可将与之类似的商品推荐给消费者。相当于以已售空的商品作为查询点，将动态轮廓计算结果推荐给消费者。

由于电商平台的商品数量巨大，通过动态轮廓查询后，推荐给消费者的商品数量仍然很多，无法帮助消费者进行选择，可通过ρ-支配轮廓查询解决，通过调节ρ值的大小完成对轮廓集大小的控制，从而实现向消费者推荐其期望的商品数量。

然而，电商数据具有典型的数据流特点。传统的ρ-支配轮廓查询不能满足具有无限性和实时性的数据流中的查询需求，因而本文将研究数据流中的ρ-支配轮廓查询来满足此类现实应用。平台中商品的更新是频繁的，则很久以前的商品成为推荐商品的概率极小，因此可以只关注最近一段时间内平台中的商品。本文在基于append-only数据流的基础上应用滑动窗口来研究数据流中的ρ-支配轮廓查询算法。

首先，给出了完全支配关系、ρ-支配关系、ρ-支配轮廓和数据流上ρ-支配轮廓的定义。然后，深入地分析了数据流上ρ-支配轮廓的性质，建立了基于时序支配的数据过滤方法，并据此提出了基于滑动窗口的ρ-支配轮廓查询算法（ρ-dom inant skyline query over sliding w indow，DSSW）。最后，通过实验证明DSSW算法提高了数据流上的ρ-支配轮廓计算的效率。

2 相关工作

2.1 轮廓查询

一些学者针对非数据流上的轮廓查询进行了大量的研究工作。Borzsonyi等人[1]提出了嵌套循环算法，将某个元组p与其他元组逐一比较，如果p不被任意其他元组支配，则p是轮廓点，并使用轮廓操作去扩展数据库系统；Papadias等人[2]提出了基于最近搜索的BBS（branch-and-bound skyline）算法，此算法仅仅对可能包含轮廓点的R树节点执行一次存取并且不进行重复检索，另外此算法还可以有效地应用于各种变体轮廓查询中；Chen等人[3]提出了定义在动态空间中的动态轮廓查询，通过动态索引给出了一种有效的剪枝技术去计算动态轮廓，并且论证了剪枝后动态轮廓查询的性能；Chan等人[4]提出了考虑不同维度时多久返回轮廓结果的频率轮廓查询，并应用找出top-k频率的轮廓点给出了一种计算方法；Yiu等人[5]应用多维数据索引和深入探究top-k支配的特点给出了一种计算top-k轮廓的算法；Chen等人[6]通过大量的无组织的分布式环境研究了约束轮廓，首先利用一种分割算法将所有的数据分割为一些群组以便可以并发处理这些数据，然后提出了一个并行处理算法。

也有学者针对数据流上的轮廓查询开展了一些研究工作。Kossmann等人[7]第一次提出了持续的轮廓查询算法，首先立刻返回一组轮廓，然后持续不断地返回多组轮廓并且允许使用者控制计算时间；Lin等人[8]第一次提出了在最近N组数据中计算轮廓的n-of-N轮廓查询，提出了一种剪枝技术和一种高效数据存取技术，并且提出了一种持续计算n-of-N轮廓的算法；Zhang等人[9]分析了需要保存数据的特点和轮廓集合的大小，提出了不确定数据流上的轮廓查询算法；Ding等人[10]研究了不确定数据流上的轮廓查询问题；Yang等人[11]提出了DC-Tree算法去计算数据流上的轮廓查询；Zhu等人[12]提出了以DC-tree作为索引的反轮廓查询算法，并且应用剪枝技术缩减了查找空间的大小；Bai等人[13]提出了不确定数据流上概率反轮廓查询的定义以及索引模型，并且提出了一种基于R-tree的不确定数据流上的反轮廓查询算法（probabilistic reverse skyline on uncertain data streams based on R-tree index，RT2RS）；Dellis等人[14]采用多个低维索引来支持任意子空间的限制性轮廓查询；Morse等人[15]提出了LookOut算法来计算连续时间间隔的轮廓查询。

2.2 ρ-支配轮廓查询

2011年，Xin等人[16]首先提出了基于数值间比例值大小的ρ-支配关系和ρ-支配轮廓查询的概念，并建立了一种应用于传统数据集上的基于分支定界的ρ-支配轮廓查询算法（branch and boundρ-dominant skyline algorithm，BBDS）。BBDS算法采用标准的R树索引存储数据，并将所有数据分为两类：ρ-支配轮廓集合S和非ρ-支配轮廓集合SS，初始时两集合均为空。采用广度优先遍历算法遍历R树中的节点e，如果e是中间节点，判断e是否被S+SS中的两个数据支配；若不被两个数据支配，则遍历所有不被两个元素支配的子节点。如果e是叶子节点，判断e是否被S+SS中的数据支配，如果不被支配，继续判断是否被S+SS中的数据ρ-支配，若不被ρ-支配则将e加入到S中，否则将e加入到SS中；接着将S中被eρ-支配的集合加入到SS中。

但是在数据流中，若每当有数据更新时便先维护R树，再调用BBDS算法，必将花费大量的时间和空间代价。总之，传统的ρ-支配轮廓查询无法在数据更新频繁时满足查询处理的实时性需求，而数据流上的轮廓查询不能满足数值间比例关系的轮廓查询。因此，本文将深入研究数据流中的ρ-支配轮廓查询问题。

3 问题描述

首先回顾完全支配关系和ρ-支配关系[16]的定义。

图2（a）显示了二维空间中完全支配的一个例子。因为对任意一维b和q之间的距离比a和q之间的距离短，并且a、b在q的同一侧，所以点b关于查询点q完全支配点a。同理，点h关于查询点q完全支配点g。而点b、c、d、e、f和点h不被其他任一点完全支配。

Fig.2 Example of full-dom inance andρ-dom inance图2 完全支配和ρ-支配示例图

图2（b）展示了当ρ取值为1.5时的ρ-支配关系的例子，在本例中使用x′表示x与q的1/3分位点。因为对任意一维点b′和点q之间的距离比点a和点q之间的距离小，并且b′和a在点q的同一侧，所以点b关于查询点q1.5-支配点a。同理可得，点f关于查询点q1.5-支配点e，并且点e关于查询点q1.5-支配点f，点h关于查询点q1.5-支配点g。而点b、c、d和h不被其他任意点1.5-支配。

由完全支配关系和ρ-支配关系可以容易地得出完全支配轮廓和ρ-支配轮廓[16]的定义，如定义3和定义4所示。

定义3（完全支配轮廓）给定一个数据集合P和一个查询点q，数据集P中所有不被P中其他点关于点q完全支配的点构成数据集P的完全支配轮廓。

定义4（ρ-支配轮廓）给定一个数据集合P和一个查询点q，数据集P中所有不被P中其他点关于点qρ-支配的点构成数据集P的ρ-支配轮廓。

根据定义3可得，如果一个点p不被数据集中其他任一点关于查询点q完全支配，则点p为一个完全支配轮廓点。如图2（a）所示，点b、c、d、e、f和h不被其他任意点完全支配，因此点b、c、d、e、f和h构成了图2（a）的完全支配轮廓。同理可以得出点b、c、d和h组成图2（b）的1.5-支配轮廓。

根据定义3和定义4可以容易地看出完全支配轮廓是ρ-支配轮廓中ρ取值为1时的特例。

类似ρ-支配轮廓，可以得出数据流上的ρ-支配轮廓的定义。用PN表示数据流中最近的N组数据，即滑动窗口中的数据，并且用L(p)表示点p在数据流中的位置，L(p)大的点表示后到，数据流中的ρ-支配轮廓如定义5所示。

定义5（数据流中的ρ-支配轮廓）给定一个数据流P和一个查询点q，则数据流上PN中不被其他任一点ρ-支配的点构成数据流P的ρ-支配轮廓。

4 数据流中的ρ-支配轮廓查询

本文将详细介绍DSSW算法，首先深入分析数据流上的ρ-支配轮廓的性质；接着根据数据流上ρ-支配轮廓的性质建立数据过滤方法；最后详细地给出DSSW算法的具体过程。

4.1 ρ-支配轮廓的性质

当ρ小于等于1时，ρ-支配关系满足传递性，因此ρ小于等于1时的ρ-支配轮廓可以采用类似于轮廓查询的方式来计算，故本文只讨论ρ大于1时的情况。

如图2（a）和图2（b）所示，对于同一个数据集合P，完全支配轮廓包含点b、c、d、e、f和h，而1.5-支配轮廓包含点b、c、d和h，从中可以容易地看出完全支配轮廓点包含1.5-支配轮廓点。此结论更一般的表达如定理1所示。

定理1给定两个值ρ1和ρ2，并且ρ1＞ρ2，如果一个点 p是 ρ1-支配轮廓点，那么 p一定也是 ρ2-支配轮廓点。

由定理1可以看出，通过调节ρ值的大小可以控制结果集的大小，因此 ρ-支配轮廓查询有更广泛的应用。

定理2给定两个点x和y，如果 ρ＞1并且x≻qy，则

由定理2可以看出，如果一个点x被另一个点y完全支配，那么当 ρ＞1时点x也被点yρ-支配。由定理2的证明过程可以容易地得出反之不成立。

定理3给定数据流中的两个点x和y，如果并且L(x)＞L(y)，则点y不可能成为 ρ-支配轮廓点。

证明因为，所以当x属于PN时点y不是ρ-支配轮廓点。又由于在数据流中L(x)＞L(y)，则在PN中y比x先消失，从而y不可能成为一个 ρ-支配轮廓点。 □

引理1给定数据流中的两个点x和y，如果x≻qy并且L(x)＞L(y)，则点y不可能成为 ρ-支配轮廓点。

由定理2和定理3可以容易地证出引理1。

定理4如果x≻qy和，那么

一个点p可能同时被PN中多个点ρ-支配，并且PN中只要存在一个 ρ-支配点 p的点，点 p就不是 ρ-支配轮廓点，因此点 p是否是 ρ-支配轮廓点将由 ρ-支配它的点中最后一个到达的点n是否存在于PN中所决定，并且将点n记为 pre(p)。

4.2 过滤方法

考虑图3中的例子，其中点按照它们的字母表顺序依次到达，并且 ρ值为2。假设点c刚刚到达滑动窗口，并且滑动窗口的大小大于3，因为点a被点b2-支配，所以点a不可能成为ρ-支配轮廓点，但是如果将a过滤掉，因为点b不能 ρ-支配点c，所以点c将被判断为 ρ-支配轮廓点。然而，从图3中可以看出点aρ-支配点c，因此点c不是 ρ-支配轮廓点，不能直接将不可能成为ρ-支配轮廓点的点过滤掉。

Fig.3 Counterexampleof filtering图3 过滤的反例

如果一个点y被另一个后到的点x完全支配，根据定理4可得，则被点yρ-支配的点也被点xρ-支配，因此当删除点y时，如果有新的被点yρ-支配的点z到达时，点z必将被点xρ-支配，从而不会影响点z是否成为 ρ-支配轮廓点；又根据引理1可得，点y不可能成为一个ρ-支配轮廓点，因此在轮廓计算前可以过滤掉被后到的点完全支配的点。

用SN表示PN中过滤后的点的集合，则SN={p|p∈PN,∃/p′∈PN,L(p′)＞L(p)∧p′≻qp}。进一步可以将SN划分为3类：

（1）ρ-支配轮廓点(DN)，SN中不被其他任何点ρ-支配的点的集合；

（2）候选点(CN)，SN中被先到的点ρ-支配而不被后到的点ρ-支配的点的集合；

（3）辅助点(AN)，SN中被后到的点ρ-支配而不被后到的点完全支配的点的集合。

继续考虑图2（b）的例子，假设滑动窗口的大小不小于8，并且点按照字母表顺序到达。因为点a和g分别被b和h完全支配，所以计算前过滤掉a和g，从而SN={b,c,d,e,f,h}；因为点b、c、d和h不被其他任一点ρ-支配，所以ρ-支配轮廓DN={b,c,d,h}；因为点f被一个先到的点eρ-支配而不被后到的点ρ-支配，所以候选点CN={f}；因为点e被一个后到的点ρ-支配而不被后到的点完全支配，所以辅助点AN={e}。

至此，已经建立了数据流中ρ-支配轮廓查询的过滤方法。根据点集合的划分方式可知一个新到达的点要么属于DN，要么属于CN。由过滤方法可得SN为计算ρ-支配轮廓所需要存储的最小数据集合。

4.3 查询过程

由定义1和定义2可以得出，完全支配关系和ρ-支配关系只能存在于查询点同一侧区域中的两个点之间，因此当滑动窗口中一个新的点到达时只需判断该点同一区域内的点与该点的支配关系（如果一个点与查询点在某几维上相同，则该点属于多个区域）。在Xin等人[16]的算法中采用了R树索引存储方式，将SN中数据分配到2d个区域进行存储。

尽管传统的R树索引存储可以大大减少数据查找的时间消耗，但是当数据流中的数据更新时，删除和插入等操作将花费大量的维护时间，降低了算法的时间效率。本文将使用2d个Map容器对SN中的数据进行存储，当有新的数据更新时只需计算该数据所属的区域R()并存储即可。此方法既加快了数据查找时的效率，又省去了当数据更新时维护R树所需的时间。

算法1描述了DSSW算法的具体查询过程。当n个新的点p1-pn到达时，如果滑动窗口已满，则查找滑动窗口中最先到达的n个点o1-on，并计算点所属的区域R()，然后将点o1-on在相应的R()中删除，并且在CN中查找被o1-on中的点ρ-支配的点的集合DC，将DC中的点从CN中转移到DN中；计算出点p1-pn所属的区域R()，并根据R()将p1-pn分成k组；对于k组中的每一组，在区域R()中查找被p1-pn中的点完全支配的点的集合DF，并且将这些点在PN中删除，然后在R()中查找被p1-pn中的点ρ-支配的点的集合DS，并且将DS中的点从DN和CN中移到AN；如果在区域R(pi)中存在点zρ-支配点pi，将点pi加入到CN中，否则将点pi加入到DN中；最后将点pi存储到区域R(pi)中。

算法1DSSW算法

1.while（新的n个点p1-pn到达）

2.if（滑动窗口已满）

3.查找最先进入窗口的n个点o1-on

4.分别计算点o1-on的区域R()

5.将o1-on分别在所在的区域R()中删除

6.在CN中查找以o1-on中的点为pre()的集合DC

7.将DC从CN移动到DN

8.计算点p1-pn的区域R()

9.将p1-pn按照所在的区域R()分成k组

10.for（k组中的每一组）

11.在本区域R()中查找被p1-pn中的点完全支配的集合DF

12.将DF中的点过滤掉

13.在本区域R()中查找被点p1-pn中的点ρ-支配的集合DS

14.将DS中的点从DN和CN移动到AN

15. for（p从p1-pn）

16. if（存在点z为pre(p)）

17.pre(p)=L(z)

18.将点p加入集合CN

19. else

20.将点p加入集合DN

21.将点p存储到相应的R(p)中

算法2描述了点p所属区域的计算过程。在此过程中，假设点p和查询点q都是d维。如果在第一维中点p大于点q，则将1放入R(p)容器中，如果在第一维点p小于点q，则将0放入R(p)容器中，否则将0和1同时放入R(p)容器中；然后从第二维到第d维遍历p和q中的数据，假设遍历到第i维，如果在第i维点p大于点q，则将容器R(p)中的每个数与2左移i-1位相加，如果点p等于点q，则将R(p)容器中的数与2左移i-1位相加，并放入R(p)容器中，且R(p)容器中的原数据不变。需要注意的是如果点p和点q在某些维上的值相同，将得到多个区域，那么每个区域都需要进行处理。

算法2计算点p的区域号

input:任意d维数据p和查询点q

output:点p的区域号R(p)

1.定义整型容器R(p)

2.if(p[0]＞q[0])

3.将1加入R(p)

4.else if(p[0]=q[0])

5.将1和0加入R(p)

6.else

7.将0加入R(p)

8.for(i=1;i＜ =d;i++)//表示遍历第i维

9. if(p[i]＞q[i])

10.将R(p)中的数据都加上2＜＜(i+1)

11. else if(p[i]=q[i])

12.将R(p)中数据加上2＜＜(i+1)放入R(p)

13.returnR(p)

5 实验结果

本文系统地测试了扩展的BBDS算法[16]和DSSW算法在ρ值、滑动窗口大小、滑动因子和数据维度变化时的性能。性能评估指标包括响应时间和滑动窗口中的数据量，显然响应时间越短，滑动窗口中保留的数据量越小，在响应时间及存储空间上的优势越明显。所有算法均采用标准C++实现，数据均采用合成的标准测试数据集，本文对独立分布、正相关分布和反相关分布数据分别进行测试。实验环境为Intel Core i5-4590 3.30 GHz CPU和8 GB内存的PC机。实验中参数的主要变化范围及其默认值如表1所示。

Table 1 Experimentalparameters表1 实验参数变化范围

首先，讨论在窗口大小为100，维度为4，滑动因子为1时ρ值对算法性能的影响。图4表示了当ρ值从2变化到6时ρ-支配轮廓集的大小变化情况，从图中可以看出，无论是何种分布数据，随着ρ值的增大，ρ-支配轮廓集都逐渐减小。原因在于ρ值增大导致数据所支配的面积变大，数据越容易被ρ-支配，从而使数据成为ρ-支配轮廓点的概率减小。图5表示了ρ值对响应时间的影响，从图中可以看出，当ρ值变化时响应时间没有太大的改变，但是不管何种分布数据，DSSW算法由于采用了数据过滤技术、近似R树索引和数据分类方法，响应时间都远小于BBDS算法。图6显示了ρ值对滑动窗口中保留的数据量的影响，从图中可以看出，无论是何种分布数据，滑动窗口中保留的数据量都与ρ值无关。原因在于采用的数据过滤方法是过滤掉被后到的点完全支配的点，对于相同的数据流，当ρ大于1时过滤掉的点是相同的，但是DSSW算法由于采用了数据过滤方法，滑动窗口中保留的数据量始终小于BBDS算法滑动窗口中保留的数据量。图5和图6的实验结果都证明了DSSW算法的有效性。

Fig.4 Effectofρon skyline size图4 ρ值对轮廓集大小的影响

Fig.5 Effectofρon response time图5 ρ值对响应时间的影响

Fig.6 Effectofρon data size inw indow图6 ρ值对窗口中保留数据量的影响

Fig.7 Effectof slidingw indow sizeon skyline size图7 滑动窗口大小对轮廓集大小的影响

然后，讨论ρ值为2，维度为4，滑动因子为1时滑动窗口的大小对算法性能的影响。图7显示了当滑动窗口大小变化时ρ-支配轮廓集大小的变化情况，从图中可以看出，无论是何种分布数据，ρ-支配轮廓集都随着滑动窗口的增大而增大。原因在于当滑动窗口增大时，参与轮廓计算的数据点增多，从而ρ-支配轮廓集增大。图8显示了滑动窗口大小对算法响应时间的影响，从图中可以看出，当滑动窗口变大时，BBDS算法的响应时间急剧增加，而DSSW算法由于采用了数据过滤、近似R树索引和数据分类，响应时间虽然增加，但始终小于BBDS算法，且滑动窗口越大，差距越明显。图9显示了滑动窗口大小对滑动窗口中保留的数据量的影响，从图中可以看出，BBDS算法的滑动窗口中保留的数据量始终与滑动窗口的大小相同，而DSSW算法随着滑动窗口的变大，滑动窗口中保留的数据量逐渐变多，但DSSW算法由于采用了数据过滤方法，滑动窗口中保留的数据量总是远远小于BBDS算法的滑动窗口中保留的数据量。图8和图9进一步证明了DSSW算法的有效性。

Fig.8 Effectof slidingw indow size on response time图8 滑动窗口大小对响应时间的影响

Fig.9 Effectof slidingw indow sizeon data size inw indow图9 滑动窗口大小对窗口中保留数据量的影响

Fig.10 Effectof dimension on skyline size图10 维度对轮廓集大小的影响

接着，讨论当ρ值为2，滑动窗口大小为100，滑动因子为1时维度对算法性能的影响。图10显示了当维度从2变化到6时ρ-支配轮廓集的大小，从图中可以看出，无论是何种分布数据，ρ-支配轮廓集随着维度的增加而增大。原因在于维度增大时，数据点被ρ-支配的概率降低，数据成为ρ-支配轮廓点的可能性增大，从而ρ-支配轮廓集变大，当维度超过一定限度时，ρ-支配轮廓将为滑动窗口中的全部数据。图11显示了维度对响应时间的影响，从图中可以看出，无论是何种分布数据，当维度增加时响应时间变长，但是DSSW算法的响应时间远小于BBDS算法。图12显示了维度对滑动窗口中保留的数据量的影响，从图中可以看出，BBDS算法的滑动窗口中保留的数据量始终与滑动窗口的大小相同，而DSSW算法滑动窗口中保留的数据量随着维度的增加而逐渐增加，但数据过滤使其总是小于BBDS算法的该值。图11和图12进一步证明了DSSW算法的有效性。

Fig.11 Effectof dimension on response time图11 维度对响应时间的影响

Fig.12 Effectof dimension on data size inw indow图12 维度对窗口中保留数据量的影响

Fig.13 Effectof sliding factor on skyline size图13 滑动因子对轮廓集大小的影响

最后，讨论当ρ值为2，滑动窗口大小为100，维度为4时滑动因子对算法性能的影响。图13显示了当滑动因子从1变化到5时相应的ρ-支配轮廓集的大小，从图中可以看出，无论是何种分布数据，ρ-支配轮廓集都不受滑动因子的影响。原因在于滑动因子只代表数据流更新的快慢，对数据是否成为ρ-支配轮廓点没有影响。图14显示了滑动因子对响应时间的影响，从图中可以看出，无论是何种分布数据，当滑动因子增加时响应时间变长。原因在于滑动窗口中需要更新的数据变多，需要参与ρ-支配计算的数据变多，但是DSSW算法的响应时间始终小于BBDS算法的响应时间。图15显示了滑动因子对滑动窗口中保留的数据量的影响，从图中可以看出，滑动因子对滑动窗口中的数据量几乎没有影响，BBDS算法的滑动窗口中保留的数据量始终与滑动窗口的大小相同，而DSSW算法由于采用了数据过滤方法，滑动窗口中保留的数据量始终小于BBDS算法的滑动窗口中保留的数据量。图14和图15更进一步证明了DSSW算法的有效性。

6 结论

Fig.14 Effectof sliding factoron response time图14 滑动因子对响应时间的影响

Fig.15 Effectof sliding factor on data size in w indow图15 滑动因子对窗口中保留数据量的影响

ρ-支配轮廓查询被广泛应用于数值间比例关系的多标准决策中，但在数据的流特性日益突出的今天，传统的ρ-支配轮廓查询无法在数据更新频繁时满足查询处理的实时性需求，因此本文研究了数据流上的ρ-支配轮廓查询处理技术。首先，通过实际问题对数据流上的ρ-支配轮廓查询的需求进行分析，给出了数据流上的ρ-支配轮廓的概念；然后，通过充分挖掘数据流上的ρ-支配轮廓的性质，建立了基于时序支配的数据过滤方法，并将数据集进行分类；接着，提出了数据流上的基于滑动窗口的ρ-支配轮廓查询处理算法DSSW；最后，通过大量的实验证明了DSSW算法是计算数据流上的ρ-支配轮廓的高效算法。本文基于计数的滑动窗口进行讨论，从中可以看出DSSW算法能够容易地扩展到基于时间的滑动窗口上。

[1]Börzsönyi S,Kossmann D,Stocker K.The skyline operator[C]//Proceedings of the 17th International Conference on Data Engineering,Heidelberg,Germany,Apr 2-6,2001.Washington:IEEEComputer Society,2001:421-430.

[2]Papadias D,Tao Yufei,Fu G,etal.An optimal and progressive algorithm for skyline queries[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Managementof Data,San Diego,USA,Jun 9-12,2003.New York:ACM,2003:467-478.

[3]Chen Lei,Lian Xiang.Dynamic skyline queries inmetric spaces[C]//Proceedings of the 11th International Conferenceon Extending Database Technology:Advances in Database Technology,Nantes,France,Mar 25-29,2008.New York:ACM,2008:333-343.

[4]Chan CY,Jagadish H V,Tan K L,etal.On high dimensional skylines[C]//LNCS 3896:Proceedings of the 10th International Conference on Extending Database Technology,Munich,Germany,Mar 26-31,2006.Berlin,Heidelberg:Springer,2006:478-495.

[5]Yiu M L,Mamoulis N.Efficient processing of top-kdominating queries on multi-dimensional data[C]//Proceedings of the 33rd International Conference on Very Large Data Bases,Vienna,Austria,Sep 23-27,2007.New York:ACM,2007:483-494.

[6]Chen Lijiang,Cui Bin,Lu Hua.Constrained skyline query processing against distributed data sites[J].IEEE Transactionson Know ledge and Data Engineering,2011,23(2):204-217.

[7]Kossmann D,Ramsak F,Rost S.Shooting stars in the sky:an online algorithm for skyline queries[C]//Proceedings of the 28th International Conference on Very Large Data Bases,Hong Kong,China,Aug 20-23,2002.New York:ACM,2002:275-286.

[8]Lin Xuemin,Yuan Yidong,Wang Wei,et al.Stabbing the sky:efficientskyline computation over sliding w indows[C]//Proceedings of the 21st International Conference on Data Engineering,Tokyo,Japan,Apr 5-8,2005.Piscataway,USA:IEEE,2005:502-513.

[9]ZhangWenjie,Lin Xuemin,Zhang Ying,etal.Probabilistic skyline operator over sliding w indow s[C]//Proceedings of the 25th International Conference on Data Engineering,Shanghai,Mar 29-Apr 2,2009.Washington:IEEEComputer Society,2009:1060-1071.

[10]Ding Xiaofeng,Lian Xiang,Chen Lei,et al.Continuous monitoring of skylinesoveruncertain data streams[J].Information Sciences,2012,184(1):196-214.

[11]Yang Jing,Qu Bo,LiCuiping,etal.DC-Tree:an algorithm for skyline query on data streams[C]//LNCS 5139:Proceedings of the 4th International Conference on Advanced DataM ining and Applications,Chengdu,China,Oct8-10,2008.Berlin,Heidelberg:Springer,2008:644-651.

[12]Zhu Ling,LiCuiping,Chen Hong.Efficient computation of reverse skyline on data stream[C]//Proceedings of the 2009 International Joint Conference on Computational Sciences and Optim ization,Sanya,China,Apr24-26,2009.Washington:IEEEComputer Society,2009:735-739.

[13]Bai Mei,Xin Junchang,Wang Guoren,et al.Probabilistic reverse skyline query processing on uncertain data streams[J].Journal of Computer Research and Development,2011,48(10):1842-1849.

[14]Dellis E,V lachou A,V ladim irskiy I,etal.Constrained subspace skyline computation[C]//Proceedingsof the 15th International Conference on Information and Know ledge Management,Arlington,USA,Nov 6-11,2006.New York:ACM,2006:415-424.

[15]Morse M,Patel J,Grosky W.Efficient continuous skyline computation[J].Information Sciences,2007,177(17):3411-3437.

[16]Xin Junchang,Bai Mei,Dong Han,et al.An efficient processing algorithm forρ-dominant skyline query[J].Chinese Journalof Computers,2011,34(10):1876-1884.

附中文参考文献：

[13]白梅,信俊昌,王国仁,等.不确定数据流上的概率反轮廓查询处理[J].计算机研究与发展,2011,48(10):1842-1849.

[16]信俊昌,白梅,东韩,等.一种 ρ-支配轮廓查询的高效处理算法[J].计算机学报,2011,34(10):1876-1884.

王之琼（1980—），女，黑龙江哈尔滨人，2014年于东北大学计算机软件与理论专业获得博士学位，现为东北大学副教授、硕士生导师，主要研究领域为数据处理，计算机图像处理，大数据分析等。发表学术论文40余篇，作为负责人承担了国家自然科学基金、辽宁省自然科学基金和中国博士后科学基金等课题5项。

BA Jianm in was born in 1990.He is an M.S.candidate atNortheastern University.His research interest is Skyline query.

霸建民（1990—），男，河北景县人，东北大学计算机科学与工程学院硕士研究生，主要研究领域为Skyline查询处理。

HUANG Da was born in 1983.He is an M.S.candidate at School of Computer Science and Engineering,Northeastern University.His research interests include data stream,computernetwork andmachine learning,etc.

黄达（1983—），男，湖南浏阳人，东北大学计算机科学与工程学院硕士研究生，主要研究领域为数据流，计算机网络，机器学习等。

XIN Junchang was born in 1977.He received theM.S.and Ph.D.degrees in computer science and technology from Northeastern University in 2005 and 2008 respectively.Now he is an associate professor at School of Computer Science and Engineering,Northeastern University,and themember of CCF.His research interests include big data management,sensory datamanagement,uncertain datamanagement,cloud computing andmachine learning,etc.

信俊昌（1977—），男，辽宁辽阳人，2005年和2008年于东北大学分别获得硕士和博士学位，现为东北大学计算机科学与工程学院副教授，CCF会员，主要研究领域为大数据管理，感知数据管理，不确定数据管理，云计算，机器学习等。

ρ-Dom inant Skyline Com putation on Data Stream s*

WANG Zhiqiong1,BA Jianm in2,HUANG Da2,XIN Junchang2+
1.Schoolof Sino-Dutch Biomedicaland Information Engineering,Northeastern University,Shenyang 110819,China
2.Schoolof Computer Scienceand Engineering,Northeastern University,Shenyang 110819,China

Skyline query on data stream can'tdirectly compute ρ-dominantskyline query,and traditionalρ-dominant skyline query can'tmeet the real-time need when data are updated frequently.So this paper proposesρ-dom inant skyline query algorithm on data stream.Firstly,the definitions of full-dom inance,ρ-dom inance and ρ-dominant skyline are introduced,and the definition ofρ-dom inant skyline on data stream is proposed.Next,a data filtering method based on time sequence dom inance is proposed by thoroughly analyzing properties aboutρ-dominantskyline on data stream,and an algorithm,calledρ-dom inantskyline query over slidingw indow(DSSW),is developed to increase the efficiency of skyline computing on data stream.Finally,extensive experiments show that the DSSW algorithm has obvious advantages in response time and storage space compared w ith traditionalρ-dominant skylinealgorithm.

iong was born in 1980.She

the Ph.D.degree in computer software and theory from Northeastern University in 2014.Now she is an associate professor and M.S.supervisor at Northeastern University.Her research interests include data processing,computer image processing and big data analytics,etc.

：TP311.13

*The NationalNatural Science Foundation of China underGrantNos.61402089,61472069,61502215(国家自然科学基金);the Fundamental Research Funds for the Central Universities of China under GrantNos.N161904001,N161602003(中央高校基本科研业务费专项资金);the Natural Science Foundation of Liaoning Province under Grant No.2015020553(辽宁省自然科学基金);the Postdoctoral Science Foundation of ChinaunderGrantNo.2016M 591447(中国博士后科学基金);the Postdoctoral Science Foundation of Northeastern University underGrantNo.20160203(东北大学博士后科研基金).

Received 2016-07,Accepted 2016-09.

CNKI网络优先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1047.028.htm l

Keywords:ρ-dom inant relationship;ρ-dom inantskyline;data stream;slidingw indow