基于ρ-支配轮廓及n-of-Nρ-支配轮廓的数据流中关键数据计算方法

霸建民，郭永红，彭龙，赵东阳，邵鹏志，杜宏博

(中国兵器工业集团有限公司 计算机应用技术研究所,北京 100089)

0 引言

目前，随着数据采集手段的迅猛发展，大量的数据得以产生并且呈现出数据流[1-2]的特点。但是很多情况下数据采集区域的网络非常受限，比如网络时断时续、网络带宽较小，而且数据应用和数据采集往往分布在不同的地点，因此怎样将采集的流式数据及时传输到数据应用方至关重要。例如，装甲车通过传感器能够实时获取车辆的油压、水温等状态数据，而远方的数据中心通过这些车辆的状态数据可以判断出车辆的健康状况，指挥官根据车辆的健康状况进行某场战役的指挥，因此在网络受限情况下，如何计算出车辆状态数据中的关键数据进行传输至关重要。

作为多目标决策与数据挖掘的重要手段之一，轮廓查询[3-5]及其变体轮廓查询[6-18]在许多实际应用中都发挥着非常重要的作用，即从海量数据中选取最为关键的数据。给定一个多维元组的集合P，则元组P的轮廓指的是P中所有不被其他多维元组支配的元组集合。一个多维元组x支配另一个多维元组y等价于元组x在所有维度上都不比元组y差并且至少在某个维度上元组x比元组y关键。数据元组在各维度上的关键与否，可以是用户指定的标准，即可以是“大于”、“小于”以及“不等于”等。

当以“小于”作为关键的标准进行轮廓查询时，查询的结果为偏向给定查询点q的数据，此种情况下可以被应用于个性化商品推荐，将轮廓结果反馈给用户。但是由于装甲车状态数据中查询偏向给定查询点的状态数据，在数据中心接收到的为最接近查询点q的状态数据，而存在健康问题的状态数据不能通过轮廓查询算法计算出来发送给数据中心，因此数据中心无法判断哪些装甲车辆存在问题。而当采用“大于”作为关键的标准时，轮廓计算出的数据为偏离查询点的数据，即为相对异常的数据，数据中心能够凭借异常数据鉴定装甲车辆的健康状况。鉴于此，本文采用“大于”作为关键的标准。以“大于”作为标准和以“小于”作为标准对轮廓的影响如图1所示。

图1 关键标准对轮廓的影响Fig.1 Effect of key standards on skyline

传统轮廓查询中的支配关系都是依赖于多维数据对应数值之间的大小关系而进行设计的，均没有考虑数值间的比例关系。然而，在一些实际应用中，数值间的大小关系并不能完全说明两组数据谁更关键，这时就需要使用数值间的比例关系进行关键数据选择。例如，某型装甲车的标准油压和水温为20 kPa和20 ℃，而某一个装甲车有两组状态数据在油压和水温之外其他的状态数据都一样，其中状态A油压为40 kPa、水温为30 ℃，状态B油压为45 kPa、水温为25 ℃，要求从状态A和状态B中选出关键的数据传送到数据中心。状态A在油压和水温上偏离标准状态的偏离值分别为20 kPa和10 ℃，状态B在油压和水温上偏离标准状态的偏离值分别为25 kPa和5 ℃，当考虑数值间大小关系时，在油压维度上状态A的偏离值比状态B的偏离值小5 kPa，而在水温维度上状态A的偏离值比状态B的偏离值大5 ℃，因此不能决定状态A和状态B哪个更关键。这时可以考虑基于数值间比例的支配关系，在油压维度上状态A的偏离值与状态B的偏离值的比值为0.8，在水温维度上状态A的偏离值与状态B的偏离值的比值为2，因此在两维上的比值均≥0.8；在油压维度上状态B的偏离值与状态A的偏离值的比值为1.25，在水温维度上状态B的偏离值与状态A的偏离值的比值为0.5，不均≥0.8，因此可以判定状态A更关键。特别是当各维度上数值不在同一量级时，基于对应数值间比例的支配关系更能计算出关键数据。将对应数值间的比值称之为ρ，因此基于对应数值间比例的支配关系也称之为ρ-支配关系,在此基础上的轮廓查询称之为ρ-支配轮廓[19]查询。

然而，装甲车辆的状态数据具有数据流的特性，王之琼等[20]在ρ≥1时，以“小于”作为关键的标准讨论了ρ-支配关系的性质，并且给出了一种数据流中ρ-支配轮廓计算方法。本文考虑网络受限环境中装甲车辆状态数据传输的实际情况，偏离查询点的状态数据对于评估装甲车辆的健康状态更为关键，因此以“大于”作为关键的标准进行分析，然而当以“大于”作为关键的标准时，ρ-支配关系的性质将发生改变，原算法不能直接应用于以“大于”作为关键标准的数据流中ρ-支配轮廓查询，同时考虑ρ≥1以及ρ<1的不同情况，对ρ-支配关系的性质重新进行分析，进而对原算法进行更改及扩展，在此基础上提出了数据流中n-of-Nρ-支配轮廓查询算法，数据流中n-of-Nρ-支配轮廓查询算法是在滑动窗口(大小为N)最近的n(n≤N)个点中计算ρ-支配轮廓点，进一步满足网络受限环境中关键数据选择传输的要求。归结起来，本文的主要贡献如下：

1) 以“大于”作为关键的标准，同时考虑ρ≥1以及ρ<1的不同情况重新对ρ-支配关系和ρ-支配轮廓的定义和性质进行了分析；

2) 对数据流中ρ-支配轮廓查询算法进行更改及扩展，在此基础上提出了数据流中n-of-Nρ-支配轮廓查询算法；

3) 设计了详尽的实验，通过实验表明数据流中n-of-Nρ-支配轮廓查询相比于数据流中ρ-支配轮廓查询具有更广泛的应用。

1 相关研究工作

一些学者在传统轮廓查询的基础上提出了轮廓变体查询：Borzsonyi等[3]使用轮廓查询去扩展数据库系统，轮廓操作从一组大数据集合中筛选出一组用户所感兴趣的子数据集合，并提出了嵌套循环算法；Papadias等[4]分析了NN算法的缺陷并提出了BBS算法，此算法采用邻近渐进搜索方式，仅对可能包含轮廓点的R树节点执行单次访问；Ding等[5]提出了在Map-Reduce框架下处理海量数据的轮廓查询算法，另外给出了高效的优化方法用来提高海量数据轮廓查询的效率；Lai等[7]研究了移动物联网应用中特定范围内的RSQ算法，提出了一种有效、非集中的分布式DCRSQ算法，以满足移动环境中的范围轮廓查询的需求；Tian等[8]针对高维数据集合中计算轮廓时检索数据量大的问题，提出了一种在MapReduce框架下的并行k-维轮廓查询算法，提高了k-维轮廓查询的效率；Chen等[13]考虑到现实中的数据具有动态性，将轮廓查询扩展到变换空间中，提出了变换空间中的轮廓查询，并提出了一种剪枝技术提高变换空间中轮廓查询的效率；周剑刚等[14]提出了一种道路网的轮廓查询EI算法，通过分析用户运动状态与查询间的关联关系，根据时间通过协同过滤扩展方法确定初始轮廓结果集，并对数据集进行剪枝，监测用户的运动状态，一旦用户速度发生变化，就快速根据出入点信息动态调整轮廓集；Zou等[15]研究了大型图表中的动态skyline查询，并提出了一种基于图属性的修剪规则，以推导DSG查询的候选对象；Li等[16]提出了一种基于多层网格模型的数据流中动态轮廓查询方法，模型将工作空间划分为多层网格，并基于现有数据集创建每层网格的skyline影响区域，仅当动态数据点在每层网格的skyline影响区域内更新时，才进行连续skyline查询；张丽等[17]为了应对元组在数据流上随机添加和删除的挑战，采用了基于网格的索引来存储元组，并提出了一种基于该索引的算法来计算和维护轮廓集；Bai等[18]提出了一种改进的基于数据流的动态轮廓查询算法IDS2，避免在更新某些点时计算量急剧增加，加快数据流上更新操作的速度，提高动态skyline的计算性能。

也有学者针对ρ-支配轮廓查询开展了一些研究工作。信俊昌等[19]首先通过对实际应用需求进行分析，提出了基于数值间比例值大小的ρ-支配关系，并且根据ρ-支配关系提出了ρ-支配轮廓查询，进一步提出了计算ρ-支配轮廓的BA算法和基于分支定界的BBDS算法，最后通过实验证明了BBDS算法相比于BA算法提升了效率；王之琼等[20]在ρ≥1时，以“小于”作为关键的标准给出了完全支配、ρ-支配以及ρ-支配轮廓的定义，进一步给出了数据流中ρ-支配轮廓的定义，然后分析了数据流中ρ-支配轮廓的性质并提出了基于时序支配的数据过滤方法，最后给出了数据流中ρ-支配轮廓查询的DSSW算法，将ρ-支配轮廓计算方法扩展到数据流中。

2 ρ-支配理论

数据流中ρ-支配轮廓查询算法[20]以“小于”作为关键的标准给出了完全支配和ρ-支配的定义，本文为了解决装甲车辆状态数据中关键数据选择传输的需要，以“大于”作为关键的标准重新给出相关定义。

定义1(完全支配) 一个多维数据点x关于查询点q完全支配另一个多维数据点y当且仅当满足以下两个条件：

∀i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥
0∧|x[i]-q[i]|≥|y[i]-q[i]|，

(1)

∃i∈[1,d],(x[i]-q[i])(y[i]-q[i])>
0∧|x[i]-q[i]|>|y[i]-q[i]|，

(2)

式中：d为数据的维度。

定义2(ρ-支配) 一个多维数据点x关于查询点qρ-支配另一个多维数据点y当且仅当满足以下两个条件：

∀i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥
0∧|x[i]-q[i]|≥ρ×|y[i]-q[i]|，

(3)

∃i∈[1,d],(x[i]-q[i])(y[i]-q[i])>
0∧|x[i]-q[i]|>ρ×|y[i]-q[i]|.

(4)

由定义1和定义2可以看出，以“大于”作为关键的标准时完全支配和ρ-支配的定义与以“小于”作为关键的标准时完全支配和ρ-支配的定义有所不同，所满足的条件由“小于”和“小于等于”变为了“大于”和“大于等于”。

图2为二维空间中完全支配和ρ-支配的示意图。图2(a)是完全支配的一个例子，其中：由于数据点a和数据点b在以点q为中心的同一象限内，并且在任意维度上数据点a和点q间的长度都大于数据点b和点q间的长度，所以点a关于查询点q完全支配点b.图2(b)展示了当ρ=2时的ρ-支配关系示例，其中：点a′是点a和点q的中点，点b′是点b和点q的中点；由于数据点a和数据点b在以点q为中心的同一象限内并且点a′与点q的距离并不在任意维度上都大于等于点b与点q的距离，因此点a不能ρ-支配点b，同理点b不能ρ-支配点a.从上述分析中可以看出，当ρ改变时，相同数据集合的ρ-支配关系将发生改变。

图2 完全支配和ρ-支配Fig.2 Full dominance and ρ-dominance

定义3(数据流中ρ-支配轮廓[20]) 给定一个数据流P、滑动窗口大小N和一个查询点q，则数据流上位于滑动窗口的数据集PN中不被其他任何点ρ-支配的点构成数据流中ρ-支配轮廓。

定义4(数据流中n-of-Nρ-支配轮廓) 给定一个数据流P、滑动窗口大小N和一个查询点q，则滑动窗口PN中最近的n(n≤N)个点中不被滑动窗口中其他任何点关于查询点qρ-支配的点构成数据流中n-of-Nρ-支配轮廓。

数据流中最近的N组多维数据点即为滑动窗口中的点，而最近的n组多维数据点为滑动窗口中的部分点。由定义4可知，数据流中n-of-Nρ-支配轮廓点只可能在滑动窗口中最近的n组数据点中产生，因此可以将滑动窗口中的N个数据点分为两部分。如图3所示，其中编号[N-n+1,N]的数据点是最近的n组数据点称为有效部分，编号[1,N-n]的数据点为其余N-n组数据点称为无效部分。对于一个刚刚到达滑动窗口的数据点p来说，由于点p为最近的一个点，所以点p一定位于滑动窗口的有效部分。由定义3和定义4可以看出，数据流中ρ-支配轮廓是数据流中n-of-Nρ-支配轮廓当n=N时的特例。另一种特例为n=1时，代表的是仅仅考虑最新的数据点是否为关键数据，如果是则传输给数据应用方，如果不是则不传输。因此数据流中n-of-Nρ-支配轮廓是数据流中ρ-支配轮廓的扩展，相比于ρ-支配轮廓拥有更广泛的应用。

图3 n-of-N中滑动窗口划分Fig.3 Partition of sliding window in n-of-N

由于王之琼等[20]给出的ρ-支配关系的性质是在ρ≥1时并且以“小于”作为关键的标准来进行的，因此不适用于本文的相关研究。本文以“大于”为关键的标准并且在ρ>0时重新对ρ-支配关系的性质进行讨论。

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

证明：定理1采用反证法，假设点p不是ρ2-支配轮廓点，则存在另一点xρ2-支配点p，根据定义2可得

∀i∈[1,d],(x[i]-q[i])(p[i]-q[i])≥0∧
|x[i]-q[i]|≥ρ2×|p[i]-q[i]|，

(5)

∃i∈[1,d],(x[i]-q[i])(p[i]-q[i])>0∧
|x[i]-q[i]|>ρ2×|p[i]-q[i]|,

(6)

又由于ρ1<ρ2，因此

∀i∈[1,d],(x[i]-q[i])(p[i]-q[i])≥0∧
|x[i]-q[i]|≥ρ1×|p[i]-q[i]|，

(7)

∃i∈[1,d],(x[i]-q[i])(p[i]-q[i])>0∧
|x[i]-q[i]|>ρ1×|p[i]-q[i]|.

(8)

由(7)式和(8)式可得点xρ1-支配点p，与已知条件p是ρ1-支配轮廓点存在矛盾，所以数据点p一定是ρ2-支配轮廓点。

定理1的证明过程与数据流中ρ-支配轮廓查询算法[20]的证明思路类似，但是结论正好相反。由定理1可以看出以“大于”作为关键的标准时，如果一点是较小ρ值的ρ-支配轮廓点，也必将是较大ρ值的ρ-支配轮廓点。

定理2给定数据流中的两组多维数据点x和y，如果点yρ-支配点x并且L(x)

证明：由于点yρ-支配点x，所以当y属于滑动窗口时点x不是ρ-支配轮廓点。又由于L(x)

定理3如果ρ≥1并且点xρ-支配点y以及点yρ-支配点z,则点xρ-支配点z.

证明：由点xρ-支配点y可得

∀i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥0∧
|x[i]-q[i]|≥ρ×|y[i]-q[i]|，

(9)

∃i∈[1,d],(x[i]-q[i])(y[i]-q[i])>0∧
|x[i]-q[i]|>ρ×|y[i]-q[i]|.

(10)

由点yρ-支配点z可得

∀i∈[1,d],(y[i]-q[i])(z[i]-q[i])≥0∧
|y[i]-q[i]|≥ρ×|z[i]-q[i]|，

(11)

∃i∈[1,d],(y[i]-q[i])(z[i]-q[i])>0∧
|y[i]-q[i]|>ρ×|z[i]-q[i]|.

(12)

由(9)式乘以(11)式、(10)式乘以(12)式分别可得

∀i∈[1,d],(x[i]-q[i])(y[j]-q[i])2(z[i]-
q[i])≥0∧|x[i]-q[i]|≥ρ2×|z[i]-q[i]|，

(13)

∃i∈[1,d],(x[i]-q[i])(y[i]-q[i])2(z[i]-
q[i])>0∧|x[i]-q[i]|>ρ2×|z[i]-q[i]|.

(14)

又由于(y[i]-q[i])2≥0并且ρ2>ρ，所以

∀i∈[1,d],(x[i]-q[i])(z[i]-q[i])≥0∧
|x[i]-q[i]|≥ρ×|z[i]-q[i]|，

(15)

∃i∈[1,d],(x[i]-q[i])(z[i]-q[i])>0∧
|x[i]-q[i]|>ρ×|z[i]-q[i]|.

(16)

由(15)式和(16)式可以得出点xρ-支配点y.

从定理3可以看出，以“大于”作为关键的标准，在ρ≥1时ρ-支配关系具有传递性，而在以“小于”作为关键的标准时不具有此性质。

定理4当ρ<1时，给定两个点x和y并且x完全支配y，则xρ-支配y.

由于定理4的证明过程与定理1的证明过程类似，所以此处不再累述。

定理5如果ρ<1并且xρ-支配y以及y完全支配z,则xρ-支配z.

由于定理5与定理3的证明过程类似，所以此处不再累述。

3 数据流中ρ-支配轮廓和n-of-Nρ-支配轮廓

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

当ρ≥1时，由定理3可知ρ-支配关系具有传递性，因此如果一点x被点yρ-支配，则被点xρ-支配的点一定被点yρ-支配。因此如果滑动窗口中的一个点x被后到达的另一个点yρ-支配，则点x不可能影响其他点是否为ρ-支配轮廓点。同时由定理2可得，如果滑动窗口中的一个点x被后到达的另一个点yρ-支配，则点x不可能成为ρ-支配轮廓点。综上可以得出被后到达的点ρ-支配的点不可能成为ρ-支配轮廓点并且对其他点是否为ρ-支配轮廓点不产生影响。因此可以将滑动窗口中被后到达的点ρ-支配的点在ρ-支配轮廓计算之前过滤掉。用SN表示滑动窗口中过滤后点的集合，则SN中不包含被后到的点ρ-支配的点。由于要求计算出的结果是不被其他任意点ρ-支配的点的集合，因此可以将这些点分为一类，称之为ρ-支配轮廓集合。SN中除了ρ-支配轮廓集合之外，还包含被先到达的点ρ-支配而不被后到达的点ρ-支配的点的集合，由于是被先到达的点ρ-支配，因此当ρ-支配它的点流出滑动窗口时，这些点有可能成为ρ-支配轮廓点，所以称之为候选集合。综上所述，在ρ≥1可以将SN分为两类：

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

2) 候选集合CN：SN中不被后到达的点ρ-支配但是被先到达的点ρ-支配的点的集合。

从ρ≥1时的数据过滤方法和数据分类方法可以看出，ρ≥1时滑动窗口中数据过滤方式及集合划分方式与以“小于”作为关键标准时不同，以“小于”作为关键标准时过滤掉的为被后到的点完全支配的点的集合，同时将滑动窗口中的数据分为了3类。

当ρ<1时，由定理2可知，如果滑动窗口中的一个点x被后到达的另一个点yρ-支配，则点x不可能成为ρ-支配轮廓点；然而，如果滑动窗口中的一个点x被后到达的另一个点yρ-支配，则点x不一定不影响其他的点是否为ρ-支配轮廓点，如图4所示，图中的数据点按照点a最先到达，b其次到达，c最后到达，并且ρ值取0.5，某个时刻点c刚刚到达滑动窗口且点a和点b没有滑出滑动窗口。图4中点a′与点q的距离为点a与点q距离的2倍，点b′与点q的距离为点b与点q距离的2倍。从图4中可以看出：当ρ值为0.5时，点a的ρ-支配区域为点a′与点q形成的区域，点b的ρ-支配区域为点b′与点q形成的区域，由于数据点bρ-支配数据点a，所以数据点a不是ρ-支配轮廓点；按照ρ≥1时的数据过滤方法则将点a过滤掉，假如将数据点a过滤掉，由于点c不被点bρ-支配，因此点c为ρ-支配轮廓点。但是从图4中可以看出点c被点aρ-支配，因此点c不是ρ-支配轮廓点，因此不能像ρ≥1时对滑动窗口中的数据进行过滤。

图4 ρ<1时过滤错误示例Fig.4 Example of filtering error for ρ<1

由定理2、定理4、定理5可得，如果滑动窗口中的一个点x被后到达的另一个点y完全支配，则点x被点yρ-支配并且点x不可能影响其他的点是否为ρ-支配轮廓点。综上可以得出被后到达的点完全支配的点不可能成为ρ-支配轮廓点并且对其他点是否为ρ-支配轮廓点不产生影响。因此可以将滑动窗口中被后到达的点完全支配的点在ρ-支配轮廓计算之前过滤掉，同样用SN表示滑动窗口中过滤后点的集合。当ρ≥1时，将SN分成了DN和CN，DN为不被任何数据点ρ-支配的点的集合，CN为被先到的数据点ρ-支配但是不被后到的数据点ρ-支配的点的集合。但是当ρ<1时，由于过滤掉的是被后到的点完全支配的点的集合，因此除了以上两类集合之外，SN中还有一些点是被后到的点ρ-支配而不被后到的点完全支配，这些点不可能成为ρ-支配轮廓点，因此将此类点称之为辅助集合。综上所述，当ρ<1时，可以将SN分为3类：

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

2) 候选集合CN：SN中不被后到的点ρ-支配但是被先到的点ρ-支配的点的集合；

3) 辅助集合AN：SN中不被后到的点完全支配但是被后到的点ρ-支配的点的集合。

从上述对数据流中ρ-支配轮廓查询的数据过滤和数据分类方法可以看出，以“大于”作为关键标准当ρ<1时的数据过滤和分类方法与数据流中ρ-支配轮廓查询算法[20]中当ρ≥1时的数据过滤和分类方法类似，而以“大于”作为关键标准当ρ≥1时无相关方法。

在此基础上，本文对数据流中ρ-支配轮廓查询算法进行了更改和扩展，算法1使用伪代码描述了数据流中ρ-支配轮廓计算的过程(见表1)。当数据流中有新数据点p到达滑动窗口时：首先判断滑动窗口是否已满，如果是则先删除滑动窗口中最先到达的数据，并且将被删除的点ρ-支配的点从候选集移动到ρ-支配轮廓集；然后将点p插入到相应的空间区域中，在点p所属的区域中查找出被点pρ-支配的集合DS，如果ρ≥1或者点p完全支配DS中的点则删除，否则从ρ-支配轮廓集和候选集中移动到辅助集中；最后判断是否有其他的点ρ-支配点p，如果有则将p加入到候选集，否则加入到ρ-支配轮廓集。

表1 算法1：数据流中ρ-支配轮廓查询Tab.1 Algorithm 1:ρ-dominant skyline query in data stream

3.2 数据流中n-of-Nρ-支配轮廓查询

同3.1节所描述的一样，用SN表示滑动窗口中进行数据过滤后的集合，由于当ρ≥1时ρ-支配关系和ρ-支配轮廓的性质与前面所述的性质没有改变，所以被后到的点ρ-支配的点不可能成为ρ-支配轮廓点并且对其他点是否是ρ-支配轮廓点不产生影响，因此可以在n-of-Nρ-支配轮廓计算之前过滤掉，因此可得SN为不被后到的点ρ-支配的点的集合。在前面叙述中将不被其他点ρ-支配的点称之为ρ-支配轮廓点，然而在n-of-Nρ-支配轮廓计算时，有些数据点虽然不被其他任意点ρ-支配，但由于位于滑动窗口的无效部分中，仍然不是ρ-支配轮廓点。通过n-of-Nρ-支配轮廓的定义可以得到n-of-Nρ-支配轮廓点只可能存在于滑动窗口的有效部分，因此将滑动窗口中有效部分不被其他任意点ρ-支配的点组成的集合称之为n-of-Nρ-支配轮廓集。滑动窗口的有效部分除了n-of-Nρ-支配轮廓集之外，还包含被先到的点ρ-支配的点，由于这些点以后可能成为n-of-Nρ-支配轮廓点，因此将此部分点构成的集合称之为候选集。由于滑动窗口中无效部分的数据点永远不可能成为n-of-Nρ-支配轮廓点，但是可能影响其他点是否为n-of-Nρ-支配轮廓点，因此将无效部分没有被过滤掉的点组成的集合称之为辅助集。综上所述，可以将SN分为3类：

1)n-of-Nρ-支配轮廓集合DN：SN中处于有效部分内并且不被其他任何点ρ-支配的点的集合；

2) 候选集合CN：SN中处于有效部分内并且不被滑动窗口中后到的点ρ-支配但是被先到的点ρ-支配的点的集合；

3) 辅助集合AN：SN中处于无效部分点的集合。

当ρ<1时，由于与ρ≥1时满足不同的性质，所以当ρ<1时存在不同的数据过滤方式。同样用SN表示滑动窗口中进行数据过滤后的集合，采用3.1节所述的同样数据过滤方式，将滑动窗口中被后到达的点完全支配的点在n-of-Nρ-支配轮廓计算之前过滤掉，则可得SN为不被后到的点完全支配的点的集合。由于过滤掉的是被后到的点完全支配的点的集合，因此在滑动窗口的有效部分除了n-of-Nρ-支配轮廓集和候选集之外，还存在着被后到的点ρ-支配但是不被后到的点完全支配的点组成的集合。由于这部分点只是影响其他点是否为n-of-Nρ-支配轮廓点，并不可能成为n-of-Nρ-支配轮廓点，所以将这部分加入到辅助集合中。因此，滑动窗口中的数据点仍然可以分为3部分，只是3部分所包含的数据点与ρ≥1时有所不同。当ρ<1时，对SN的分类方法如下所示：

1)n-of-Nρ-支配轮廓集合DN:SN中处于有效部分内并且不被其他任何点ρ-支配的点的集合；

2) 候选集合CN:SN中处于有效部分内并且不被滑动窗口中后到的点ρ-支配但是被先到的点ρ-支配的点的集合；

3) 辅助集合AN:SN中处于无效部分的点和有效部分中被后到的点ρ-支配但是不被后到的点完全支配的点的集合。

在此基础上，对数据流中n-of-Nρ-支配轮廓的计算过程给出了伪码描述如算法2所示(见表2)。当数据流中有新数据点p到达滑动窗口时：首先判断滑动窗口是否已满，如果是则先删除滑动窗口中最先到达的数据；然后将点p插入到相应的空间区域中；最后将n-of-Nρ-支配轮廓集返回给用户。其中，滑动窗口中最先到达的数据删除用DeletePoint( )函数来表示，新到达的数据插入用InsertPoint( )函数表示。由算法的描述可以看出算法2的时间复杂度依赖DeletePoint( )函数和InsertPoint( )函数的时间复杂度，由于两个函数的时间复杂度均为O(N)，所以算法2的时间复杂度为O(N)。

表2 算法2：数据流中n-of-Nρ-支配轮廓查询Tab.2 Algorithm 2:n-of-Nρ-dominant skyline query in data stream

算法3描述了在数据流中计算n-of-Nρ-支配轮廓时将滑动窗口中最先到达的数据点p流出滑动窗口的过程(见表3)。第1行描述的是根据点p在数据流中的编号查找点p；第3行描述了计算要删除点p所属的空间区域的过程，在算法中用RegionCalculation( )函数[20]来表示，RegionCalculation( )函数包含两个参数，第一个为所要计算的点p在各维上的数值部分value，第二个为查询点q；第4～12行描述了对于点p所属的每一个空间区域R的处理过程；第5行描述的为在空间区域R中删除点p；第6～11行描述了对于空间区域R中的每一个点x，如果点p为点x的前ρ-支配点并且点x属于候选集合(第7行)，则将点x从候选集合移动到n-of-Nρ-支配轮廓集合中(第8～9行)。通过算法描述可以看出DeletePoint( )函数外层循环为区域个数R=2d，内层循环为滑动窗口中所属R的数据N/2d，因此函数时间复杂度为O(N)。

表3 算法3：滑动窗口中数据删除-DeletePoint( )Tab.3 Algorithm 3:data deletion in sliding window-DeletePoint( )

算法4描述了在数据流中计算n-of-Nρ-支配轮廓时将新到达的点p插入到滑动窗口中的处理过程(见表4)。第1行通过调用RegionCalculation( )函数计算点p所属的空间区域；第2～19行对于所属的每一个区域进行处理，其中第3～17行为对滑动窗口中同一区域的其他数据进行处理，第18行描述的为将点p插入到所在空间区域中；第4～6行描述的为对于点p所属区域中的一个点x，判断其是否ρ-支配点p并且比已经ρ-支配点p的点编号大，如果是则更改点p的前ρ-支配点为x；第7～16行为讨论点pρ-支配点x的情况，其中第8～10行描述的为如果点x属于n-of-Nρ-支配轮廓集或者候选集并且位于滑动窗口的有效部分，则在其所属的集合中将其移除；第11～12行为讨论点x是否符合过滤的要求，如果符合，则将点x过滤掉；第13～15行描述的为点x不符合过滤的条件，如果位于滑动窗口的有效部分，则将点x转换为辅助点；第20～23行描述了滑动窗口的有效部分中最先到达的一个点之前如果没有被过滤掉，则从滑动窗口的有效部分转移到无效部分；第24～28行描述的为如果点p在滑动窗口中不被先到的点ρ-支配，则将点p加入到n-of-Nρ-支配轮廓集，否则将其加入到候选集中。通过算法描述可以看出InsertPoint( )函数外层循环为区域个数R=2d，内层循环为滑动窗口中所属R的数据N/2d，因此函数时间复杂度为O(N)。

表4 算法4：滑动窗口中新数据插入-InsertPoint( )Tab.4 Algorithm 4:new data insertion in slinding window-InsertPoint( )

4 实验说明和实验方案

4.1 实验说明

本节实验中，系统地测试了ρ值、滑动窗口大小、维度对于计算时间和ρ-支配轮廓集大小的影响。由于每次滑动窗口内的数据统计可能存在差异，所以本节采用综合滑动窗口滑动1 000次的情况，即统计ρ-支配轮廓集大小采用滑动窗口滑动1 000次过程中ρ-支配轮廓集大小的平均值，计算时间采用滑动窗口滑动1 000次过程中的计算时间总和。实验中所要考察的主要参数及其变化范围和默认值如表5所示，每次进行实验只变化其中的一个参数，而其他参数设置为默认值。

表5 实验参数变化范围和默认值Tab.5 Changing range and default values of parameters

实验数据为随机生成的独立分布数据，属性包括装甲车辆状态的发动机水温、发动机油压、分动箱温度、电流、储气瓶气压、水上液压油温、变速箱油温及发动机转速等，实验时随机选择其中的两维或者多维。数据自动生成时将数据限定在装甲车辆的各属性真实值域内，其中发动机水温为-50～200 ℃，发动机油压为0～1 000 kPa，分动箱温度为0～150 ℃，电流为0～400 A，储气瓶气压为0～1.5 MPa，水上液压油温0～150 ℃，变速箱油温为0～150 ℃，发动机转速0～3 000 r/min. 部分随机生成数据如表6所示。

表6 实验数据示例Tab.6 Example of experimental data

本节使用C++语言实现了扩展的数据流中ρ-支配轮廓查询算法和数据流中n-of-Nρ-支配轮廓查询算法。实验环境为Intel(R) Core(TM) i7-7700HQ CPU @2.80 GHz、8.00 G RAM内存和64位Win10操作系统。

4.2 实验方案

4.2.1ρ值对算法的影响

本节测试了ρ值对于算法的影响。图5显示了ρ值对于轮廓集大小的影响，从中可以看出：随着ρ值的增大轮廓集也变大，这是因为当ρ值增大时数据点所支配的面积变小，因此数据越难以被支配；但是无论ρ值如何变化，两种算法的轮廓集都远远小于滑动窗口大小，因此应用于装甲车辆状态数据传输过程中所需传输的状态数据量远远小于原数据量；而且n-of-Nρ-支配轮廓查询算法的轮廓集远远小于ρ-支配轮廓算法的轮廓集，因此在装甲车辆状态传输过程中所需传输的数据量更小。图6显示了ρ值对于计算时间的影响，从中可以看出：当ρ<1时计算时间变化不大，当ρ>1时计算时间随着ρ值的增大而增大，这是由于当ρ<1时过滤掉的为被后到的数据点完全支配的数据，因此过滤掉的数据相同；当ρ>1时过滤掉的数据为被后到的数据点ρ-支配的数据，随着ρ增大，过滤掉的数据减少，因此计算时间变长；无论ρ值如何变化，两种ρ-支配轮廓算法的计算时间相差不大。

图5 ρ值对轮廓集大小的影响Fig.5 Effect of ρ on skyline size

图6 ρ值对计算时间的影响Fig.6 Effect of ρ on computing time

4.2.2 滑动窗口大小对算法的影响

本节测试了滑动窗口大小对于算法的影响。图7为滑动窗口大小对于轮廓集大小的影响，从中可以看出：随着滑动窗口的增大轮廓集也变大；但是无论怎样变化，轮廓集都远远小于滑动窗口的大小，因此在装甲车辆状态数据传输过程中应用ρ-支配轮廓查询算法或者n-of-Nρ-支配轮廓查询算法后所需传输的状态数据量远远小于原数据量；而且n-of-Nρ-支配轮廓查询算法的轮廓集远远小于ρ-支配轮廓算法的轮廓集，因此应用n-of-Nρ-支配轮廓查询算法所需传输的状态数据量更小。图8为滑动窗口大小对于计算时间的影响，从中可以看出：随着滑动窗口的增大计算时间也变大，这是由于随着滑动窗口的增大，所需计算的数据量变大，因而导致计算时间增大，但是无论滑动窗口如何变化，两种算法的计算时间基本一致。

图7 滑动窗口对轮廓集大小的影响Fig.7 Effect of sliding window on skyline size

图8 滑动窗口对计算时间的影响Fig.8 Effect of sliding window on computing time

4.2.3 维度对算法的影响

本节测试了装甲车辆状态数据的维度对于算法的影响。图9显示了轮廓集大小随着数据维度的变化情况，从中可以看出：状态数据的维度越大轮廓集越大，这是由于当维度增大时数据被支配的概率降低，从而使得数据成为轮廓点的概率增加，但是不管维度如何变化，轮廓集都远远小于滑动窗口大小，因此应用于装甲车辆状态数据传输过程中所需传输的状态数据量远远小于原数据量；而且n-of-Nρ-支配轮廓查询算法的轮廓集远远小于ρ-支配轮廓算法的轮廓集，因此在装甲车辆状态传输过程中所需传输的数据量更小。图10显示了计算时间随着维度的变化情况，从中可以看出：计算时间随着维度的变大而变大，这是由于当维度变大时，需要计算的数值增多，从而计算时间变大。

图9 维度对轮廓集大小的影响Fig.9 Effect of dimension on skyline size

图10 维度对计算时间的影响Fig.10 Effect of dimension on computing time

4.2.4 滑动窗口有效部分大小对算法的影响

最后，测试滑动窗口有效部分大小对于轮廓集大小的影响。图11显示了n-of-Nρ-支配轮廓集随着滑动窗口有效部分增加而增大。这是由于只有位于滑动窗口中有效部分的数据点才可能成为n-of-Nρ-支配轮廓点，虽然整个滑动窗口的大小保持不变，但是滑动窗口中的有效部分所占的比例增大，所以滑动窗口中产生轮廓集的区间变大，因此相应的n-of-Nρ-支配轮廓集变大，进而通过调节滑动窗口有效部分的大小可以调整装甲车辆状态数据的传输量。

图11 滑动窗口有效部分大小对轮廓集大小的影响Fig.11 Effect of effectiveness portion of sliding window on skyline size

5 结论

在网络时断时续、网络带宽较小的网络状况受限情况下，采集的数据难以实时准确地传输到数据应用方，这严重制约着数据应用方利用数据对当前态势进行评判。本文以装甲车辆状态数据传输应用为出发点，以“大于”作为关键的标准，重新对ρ-支配关系和ρ-支配轮廓进行讨论，并对数据流中的ρ-支配轮廓查询算法进行更改和扩展，用来满足装甲车辆状态数据传输问题的需要；更进一步，对数据流中ρ-支配轮廓查询算法进行扩展，提出了数据流中n-of-Nρ-支配轮廓查询算法，进一步满足网络受限环境中装甲车辆状态关键数据选择传输的要求；最后对算法进行了实验，实验表明改进的数据流中ρ-支配轮廓查询算法以及数据流中n-of-Nρ-支配轮廓查询算法能够计算出数据流中的关键数据，对于网络受限情况下装甲车辆状态数据传输起到重要的作用，并且数据流中n-of-Nρ-支配轮廓查询相比于数据流中ρ-支配轮廓查询具有更广泛的应用，更适合应用于装甲车辆状态数据选择传输过程中。

参考文献(References)

[1] TATBUL N,ETINTEMEL U,ZDONIK SB,et al.Load shedding in a data stream manager[C]∥Proceedings of the 29th International Conference on Very Large Data Bases.Berlin,Germany:VLDBEndowment,2003:309-320.

[2] DE ASSUNCAO M D,VEITH A D S,BUYYA R.Distributed data stream processing and edge computing:asurvey on resource elasticity and future directions[J].Journal of Network &Computer Applications,2018,103:1-17.

[3] BORZSONY S,KOSSMANN D,STOCKER K.The skyline operator [C]∥Proceedings of 17th International Conference on Data Engineering.Heidelberg,Germany:IEEE,2001:421-430.

[4] PAPADIAS D,TAO Y F,FU G,et al.An optimal and progressive algorithm for skyline queries[C]∥Proceedings of the 2003 ACMSIGMOD International Conference on Management of Data.San Diego,CA,US:ACM,2003:467-478.

[5] DING L L,XIN J C,WANG G R,et al.Efficient skyline query processing of massive data based on map-reduce[J].Chinese Journal of Computers,2011,34(10):1785-1796.

[6] 余靖,刘盼盼.MapReduce框架下k-支配轮廓查询算法[J].燕山大学学报,2014,38(6):532-537.

YU J,LIU P P.k-dominant skyline query algorithm based on Map Reduce framework[J].Journal of Yanshan University,2014,38(6):532-537.(in Chinese)

[7] LAI C C,AKBAR Z F,LIU C M,et al.Distributed continuous range-skyline query monitoring over the internet of mobile things[J].IEEE Internet of Things Journal,2019,6(4):6652-6667.

[8] TIAN H,SIDDIQUE M A,MORIMOTO Y,et al.An efficient processing ofk-dominant skyline query in MapReduce[C]∥Proceedings of International Workshop on Bringing the Value of Big Data to Users.Hangzhou,China:ACM,2014:29-34.

[9] ZHENG B,LEE K C,LEE W C.Location-dependent skyline query[C]∥Proceedings of International Conference on Mobile Data Management.Beijing,China:IEEE,2008:148-155.

[10] LIU X,YANG D N,YE M,et al.U-Skyline:a new skyline query for uncertain databases[J].IEEE Transactions on Know-ledge and Data Engineering,2013,25(4):945-960.

[11] REN W L,LIAN X,GHAZINOUR K.Skyline queries over incomplete data streams[J].The VLDB Journal,2019,28(6):961-985.

[12] XIE M,WONG C W,LAL L A.An experimental survey of regret minimization query and variants:bridging the best worlds between top-k query and skyline query[J].The VLDB Journal,2020,29(1):147-175.

[13] CHEN L,LIAN X.Dynamic skyline queries in metric spaces[C] ∥Proceedings of the 11th International Conference on Extending Database Technology:Advances in Database Technology.Nantes,France:ACM,2008:333-343.

[14] 周剑刚,秦小麟,张珂珩,等.基于道路网的多移动用户动态Skyline查询[J].计算机科学,2019,46 (9):73-78.

ZHOU J G,QIN X L,ZHANF K H,et al.Dynamic skyline query for multiple mobile users based on road network[J].Computer Science,2019,46 (9):73-78.(in Chinese)

[15] ZOU L,CHEN L,ÖZSU M T,et al.Dynamic skyline queries in large graphs[C]∥Proceedings of International Conference on Database Systems for Advanced Applications.Tsukuba,Japan:Springer,2010:62-78.

[16] LI H,YOO J.An efficient scheme for continuous skyline query processing over dynamic data set[C]∥Proceedings of 2014 International Conference on Big Data and Smart Computing.Bangkok,Thailand:IEEE,2014:1197-1206.

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

ZHANG L,ZOU P,JIA Y,et al.Continuous dynamic skyline queries over data stream[J].Journal of Computer Research and Development,2015,48(1):77-85.(in Chinese)

[18] BAI M,XIN J C,WANG G R,et al.Research on dynamic skyline query processing over data streams[J].Chinese Journal of Computers,2011,34(10):1876-1884.

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

XIN J C,BAI M,DONG H,et al.An efficient processing algorithm forρ-dominant skyline query[J].Chinese Journal of Computers,2011,34(10):1876-1884.(in Chinese)

[20] 王之琼,霸建民,黄达,等.数据流中ρ-支配轮廓查询算法[J].计算机科学与探索,2017,11(7):1080-1091.

WANG Z Q,BA J M,HUANG D,et al.ρ-dominant skyline computation on data streams[J].Journal of Frontiers of Computer Science and Technology,2017,11(7):1080-1091.(in Chinese)