高效多子空间Skyline查询处理算法*

王潇逸，秦小麟，王　宁，史文浩



高效多子空间Skyline查询处理算法*

王潇逸+，秦小麟，王宁，史文浩

南京航空航天大学计算机科学与技术学院，南京210016

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(05)-0646-11

E-mail: fcst@vip.163.com http:

//www.ceaj.org Tel:

+86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61373015, 61300052, 41301047 (国家自然科学基金); the Priority Academic Development Program of Jiangsu Higher Education Institutions (江苏高校优势学科建设工程资助项目); the Foundation of Graduate Innovation Center in Nanjing University of Aeronautics and Astronautics under Grant No. kfjj20151607 (南京航空航天大学研究生创新实验室开放基金).

Received 2015-07,Accepted 2015-09.

CNKI网络优先出版: 2015-09-16, http://www.cnki.net/kcms/detail/11.5602.TP.20150916.0958.002.htm l

摘要：随着Skyline查询应用的增多，子空间Skyline查询成为热点。针对实际应用中用户从多角度审视某一数据集的需求，充分研究了多子空间Skyline查询问题。在分析现有子空间Skyline查询算法解决该问题不足的基础上，提出了子空间立方体群（subspace skycube group，SSG）结构，并给出了基于该结构的同时计算任意多个子空间Skyline查询的MSSC（multiple subspace skycube）算法。该算法采用子空间候选集（subspace candidate sets，SCS），并充分利用了子空间立方体群结构中各子空间Skyline结果间的共享关系；在此基础上，算法采用求和过滤以及最大值过滤等方法，对数据集进行剪枝和过滤，从而进一步提高算法效率。最后，分别用人造数据和真实数据对算法进行实验，并与现有算法进行比较，结果表明MSSC算法可以高效地解决多子空间Skyline查询问题。

关键词：多子空间Skyline查询；子空间序列；子空间立方体群；子空间候选集

1 引言

近年来，Skyline计算[1]及其计算方法得到众多研究者的关注，这主要因为Skyline查询结果在很多应用中都有非常重要的作用，例如多目标决策[2]、数据挖掘及可视化以及用户偏好查询等。数据库领域最初的Skyline查询研究主要集中在全空间Skyline查询，随着数据库中数据呈高维海量的趋势发展，全空间上得到的极大Skyline结果集失去意义。在许多场景中，用户很可能只对数据集的某几个维度感兴趣，而非全部维度。为此，研究者们提出子空间Skyline[3]查询概念。例如，某航班信息数据包含价格、起飞时间、历时、经停站等属性，用户发出一个查询“查找一个从北京到南京的价格便宜且历时短的航班”，该查询就是子空间（价格和历时）Skyline查询。值得注意的是，全空间上的Skyline结果对象未必是子空间Skyline的查询结果。

传统子空间Skyline查询算法主要集中于对某一特定子空间的查询[3]和对全部子空间[4-5]的查询。而实际应用中，用户往往有从多角度审视数据集的需求。因此多数情况下用户并非关注某一特定子空间，同时全部子空间上的Skyline结果对大多用户意义不大。用户通常根据自身的兴趣点关注不同子空间的组合，主要可以概括为以下两种情况：

（1）某用户同时关注一个数据集的多个不同维度组合。例如，足球队员数据集包括速度、体能、射门精度、抢断、力量5个维度。教练为掌握球员的状况，对于前锋和后卫，同时发出两条查询：

查询1查询速度快并且射门精度高的球员。

查询2查询抢断次数多并且力量大的球员。

（2）多个用户分别关心一个数据集的不同组合。例如，饭店数据集包括距离、价位、服务态度、餐厅环境、菜量、口味6个维度。甲乙丙3人相约聚餐，分别根据自己不同的喜好发出3条查询：

查询3查询位置近并且价格便宜的餐厅。

查询4查询口味好并且菜量大的餐厅。

查询5查询服务态度好并且环境好的餐厅。

上述问题概括为：对于某数据集，系统中同时存在多个不同维度组合上的子空间Skyline查询，称为多子空间Skyline查询问题。目前有关子空间Skyline查询的算法大多集中在某一特定子空间以及全部子空间，在解决任意数量的子空间Skyline查询时效率低下。对此，本文提出一种可以高效处理多个子空间Skyline查询的算法，主要贡献如下：

（1）深入研究多子空间Skyline查询问题，分析现有算法无法适用于该问题的原因。

（2）基于Skycube的定义[4]，提出子空间立方体群（subspace skycube group，SSG），给出生成该群结构的方法，并利用结构中各子空间Skyline结果的共享关系提高查询效率。

（3）基于子空间立方体群结构，提出一种求解多子空间Skyline查询的MSSC（multiple subspace skycube）算法。算法采用子空间候选集、求和过滤及最大值过滤3种优化方法，有效降低支配关系判定次数，提高了效率。

（4）同时采用人造数据和真实数据对算法性能进行评估，实验结果证明，MSSC算法能高效解决多子空间Skyline查询问题。

本文结构如下：第2章介绍Skyline查询的基础知识及相关工作，并分析现有方法在解决多子空间Skyline查询时的不足；第3章提出MSSC算法，并对算法进行详尽的解析；第4章对MSSC算法进行实验评估，并与现有算法进行性能对比；最后对本文工作进行总结。

2 背景知识

2.1 Skyline查询概述

首先介绍支配的概念，为便于描述，假定数据集在每个维度上均越小越优。

定义1（支配[1]）给定一个d维数据集S，ai(1≤i≤d)表示每个维度，D为d个维度的集合，D= {a1,a2,…,ad}。p、q分别为S中的两个数据点，其在维度ai上的值分别用p(ai)和q(ai)表示。对于任意维度组合U⊆D,如果∀ai∈U, p(ai)≤q(ai),并且∃aj∈U, p(aj)

在Skyline查询中，把数据集所有维度组成的集合称为全空间，在全空间上的Skyline查询称为全空间Skyline查询，即用户关心数据的所有属性。

定义2（全空间Skyline查询）给定一个d维数据集S，以及维度组合U，如果U=D，则称查询U上所有不被任何其他点支配的数据点的集合，为全空间Skyline查询。

子空间Skyline查询，即用户关心查询对象的部分属性。

定义3（子空间Skyline查询）给定一个d维数据集S，以及维度组合U，如果U⊂D，则称查询U上所有不被任何其他点支配的数据点的集合，为子空间Skyline查询。

表1为简化的旅馆信息数据集，该数据集有4个维度，10个数据点。根据上述定义，若用户甲发出查询“查找价格低、等级高、房间大并且距离小的宾馆”，则为全空间Skyline查询，其查询结果为{P1,P2, P3,P4,P5,P6,P7}。可见全空间Skyline结果集包含的数据点数过多（占总数的70%），并没有为用户带来较高的参考价值。因此，更多的用户可能只关注少数几个维度的组合，比如用户乙发出查询“查找价格低并且距离小的宾馆”，该查询为子空间Skyline查询，其结果为{P3,P4}。表2为该数据集上所有子空间的Skyline结果集。

Table 1 Simplified hotel information data set表1 简化的旅馆信息数据集

Table 2 A ll subspace Skyline queries results表2 所有子空间Skyline查询结果

2.2相关工作

数据库领域对Skyline查询的研究主要分为全空间Skyline查询[1,6]和子空间Skyline查询[3-5,7]。全空间Skyline查询算法主要包括BNL（block-nested-loops）算法[1]、DC（divide and conquer）算法[1]和SFS（sort first Skyline）算法[6]。此外，Tan等人提出bitmap和index两种算法[8]，避免了遍历整个数据集；Kossmann等人[9]在R树索引基础上提出最近邻（nearest neighbor，NN）算法，该算法递归搜索区域的最近邻点，并通过区域剪枝技术删除被最近邻点支配的所有对象。

随数据库中数据维数的增大以及数据量的扩增，全空间Skyline查询结果包含极多的数据点，意义不大，用户更多关注子空间上的Skyline查询。关于子空间Skyline查询的研究主要包括以下工作：

首先，BNL和SFS算法没有创建任何附加索引，因此也可以解决子空间Skyline查询问题；Tao等人[3,10]研究了任意单个子空间上的Skyline查询，并给出Subsky算法；Dellis等人[11]研究了约束子空间的Skyline查询，并提出了一种利用多索引求解的STA（thresholdbased Skyline algorithm）算法；文献[12]研究了如何在高维数据集上求解某一子空间的Skyline结果。这些算法虽然在处理某一特定子空间Skyline查询时性能优于MSSC算法，但处理多子空间Skyline查询问题时性能低下。

此外，研究者还围绕全部子空间的Skyline查询进行研究。Yuan等人[4]研究了如何高效计算某一数据集所有子空间Skyline查询的结果，并提出Skycube概念，给出计算Skycube的算法；Pei等人[5]在Skycube的基础上，提出Skyline分组概念，并对其在语义层面进行解释，之后又在文献[13]中提出一种Stellar算法来计算压缩的Skycube，这种方法避免了枚举所有子空间；与之相似，Xia等人[14]提出一种压缩Skycube层次数据结构（compressed skycube，CSC），并在此基础上给出一个有效处理Skyline查询的方法QueryCSC。上述方法均是一次性求解所有子空间的Skyline结果。

除上述外，研究者们在Skyline查询的其他方向也取得诸多成果。Kailasam等人[15]利用位图结构计算Skycube中所有子空间结果；文献[16]研究了对等网络中的子空间Skyline查询；文献[17]研究了Skyline分组问题，并给出QSkycube算法；此外，在分布式环境中，文献[7]提出了分布式不确定数据上概率Skyline查询的低通信开销算法，文献[18]研究了分布式环境中特定子空间Skyline求解方法。

经调研，现有算法没有针对求解任意多个子空间Skyline查询的研究。虽然少数已有算法可以用来解决多子空间Skyline查询问题，却有以下不足：

（1）一些算法[1,6]求解每个子空间Skyline结果时均需要遍历整个数据集至少一遍，效率较低。

（2）无需遍历整个数据集的算法[8,11]需要建立索引结构，而在解决多子空间Skyline查询时，则需要建立多个索引（最多建立2n-1个索引）。而建立索引的开销非常大，因此类方法对于解决多子空间Skyline查询问题显然效率低下。

（3）现有算法用来解决该问题时，一类是要运行多次逐个求解每个子空间Skyline结果[3,5]，效率很低；另一类是一次性计算出所有2n-1个子空间Skyline结果[4-5,13]，计算结果冗余，耗时高。

综上，多子空间Skyline查询问题是一个具有挑战性的问题，提出的MSSC算法可以高效地同时求解任意多个子空间Skyline查询。

3 多子空间Skyline查询算法

此部分将给出求解多子空间Skyline查询问题的MSSC算法。首先基于Skycube概念提出子空间立方体群结构，基于此，有效实施了MSSC算法。算法执行过程中，采用多种剪枝方式进行优化，最终，算法有效返回系统中所有的子空间Skyline查询结果。后文中，用skyV表示子空间V上的Skyline结果集，并假设数据集所有维度上的值越小越好。

3.1子空间立方体群

为充分利用子空间结果集之间的共享关系，减少算法的时间开销，在Skycube结构基础上，提出子空间立方体群概念。

文献[4]第一次提出Skycube概念。对于一个d维的数据集S，一共有2d-1个不同的维度组合，Skycube结构是由这2d-1个维度组合组成的分层结构。图1所示为旅馆信息数据集的Skycube结构。从底向上，Skycube被分为4层，对于Skycube中的两个子空间U和V，共存在3种关系：（1）如果U⊂V，且二者相差大于一层，则称V是U的祖先，例如子空间abc与b；（2）如果U⊂V，且二者只相差一层，则称V 是U的父亲，例如子空间abc与ab；（3）如果U与V在同一层，则称U与V是兄弟，例如子空间ab与bc。

Fig.1 Skycube of hotel information data set图1 旅馆数据集的Skycube结构

基于Skycube结构，定义4给出子空间立方体概念。

定义4（子空间立方体）对于子空间序列中的任意一个子空间Vi，将其构造成满足如下性质的结构，称之为子空间立方体(SSC)：（1）该结构为分层结构，层数为Vi的维数|Vi|，所有节点均为一个子空间；（2）最顶层为当前子空间Vi；（3）第j层为从Vi包含的维度中取出j个维度的所有组合，共有个子空间；（4）有向边集{}连接相邻两层的各节点，由上层节点指向下层节点，其中|Ut|=|Uk|-1，且Ut⊂Uk。

定义5（子空间立方体群）由n(n≥1)个子空间立方体构成的群结构。

系统中同时存在多个不同子空间Skyline查询时，不妨假设共有v个子空间Skyline查询，形成一个子空间序列SKS={V1,V2,…,Vv}，下面给出子空间有序列的定义。

定义6（子空间有序列）对于子空间序列SKS={V1, V2,…,Vv}，如果满足如下条件，则称该序列为子空间有序列：∀Vi,Vj∈SKS，如果locate(Vi)< locate(Vj)，则必有|Vi|≥|Vj|。其中，locate(Vi)为Vi在序列SKS中的位置，|Vi|为子空间Vi的维数。

算法1子空间立方体群生成算法createSSG(O)

输入：子空间集合O={V1,V2,…,Vv}

输出：子空间立方体群SSG

1. SSG←∅//将SSG集合初始化为空

2.SKS←createlist (V1,V2,…,Vv）

3.for i←0 to v do

4.if ! contain(SSG,Vi) then //如果子空间Vi不

在SSG中

5.SSC←createSSC(Vi) //Vi生成一个子

空间立方体

6.add SSC to SSG //将该SSC放入SSG中

7.end if

8.end for

9.return SSG //将子空间立方体群结构返回

算法1有效地将系统中多个子空间转化成子空间立方体群结构。首先将子空间集合O转化为子空间有序列，该过程的时间复杂度为O(v lb v)；之后按子空间有序列中的顺序依次将每个子空间构造成子空间立方体，并放入SSG中。其中，判断Vi是否在SSG中的时间复杂度为O(v lb v)，将Vi生成子空间立方体的时间复杂度为O(2|Vi |)。综上，算法1的时间复杂度为O(v lb v+2max(|Vi |))。其中，v为子空间个数，max(|Vi|)为待求子空间的最大维数。例如，表1旅馆信息数据集中，4个维度分别为a、b、c、d。假定系统中存在待求子空间集合为O={ab, abc, acd, a}，则通过算法1可以生成图2所示结构，该子空间立方体群包括两个子空间立方体，其中标有下划线的子空间在后续计算时只需计算一次。

Fig.2 Subspace skycube group图2 子空间立方体群

3.2子空间候选集

通过对子空间立方体群结构中子空间Skyline结果集的充分实验及观察，发现结构中相邻两层的子空间U和V(U⊂V)的Skyline结果集skyU和skyV之间并不存在一种明显的包含关系。例如前文例子中，skya为{P4, P5}，而skyab为{P1, P5, P6}。这种现象是由于数据集中存在多个数据点在某一维度上的值相同而产生的。经分析，定理1可以描述skyU和skyV中数据点之间的隐含关系。

定理1对于给定的d维数据集S，其全空间为D，U和V为两个子空间，U,V⊂D，且V是U的父亲，则∀q∈skyU，在子空间V上满足下面两种情况中的一种：（1）属于skyV；（2）被skyU中的另外某一数据点p所支配。

证明对于skyU中的数据点q，如果在skyU中存在数据点p，p与q在U的所有维度上的值都相等，那么若p在子空间V-U上支配q，则p在V上支配q；如果不存在这样的数据点p，则q一定属于skyV，因为在V上没有任何数据点能支配q。□

根据定理1描述的父亲子空间Skyline结果集与孩子子空间Skyline结果集的关系，提出了子空间候选集的概念。对于正在被计算的子空间V,其候选集的计算方法为：先对V所有孩子子空间结果集求并，之后排除在V上被其他数据点支配的数据点，得到的集合则为子空间V的候选集。子空间候选集作用为：第一，实现子空间Skyline结果共享，保证MSSC算法并非独立地求子空间立方体群中的所有子空间Skyline结果，上层求解过程建立在下层已求结果的基础上；第二，对于每个子空间的计算过程，减小了数据输入量；第三，由于候选集中的数据点一定属于当前子空间V的Skyline结果，有效避免了对这一部分数据点的支配关系判断过程，大量减少了比较次数。因此子空间候选集的使用，有效提高了算法效率。算法2子空间候选集生成算法createSCS(V,SSC)输入：当前正在计算的子空间V；以V为顶点的子空间立方体SSC

输出：子空间V的候选集SCS 1. SCS←union(SSC)

//将SCS初始化为V的所有孩子空间Skyline结果集的并

2. for i←0 to |V| do//对于V的每一个孩子子空间Ui

3.for every point p∈skyUido //对于skyUi中的每

个数据点p

4.BUF←getEqualPoint(p, Ui)

//找出与p在Ui上相同的点，放入BUF

5.if BUF≠∅then //如果存在与p在Ui上相同的点

6.BUF←p //将p也放入BUF

7.TEMP←BUF-getSkyline(BUF,V-Ui)

//将不是V上的Skyline结果的点找出

8.SCS←SCS-TEMP

//从SCS中将非V上Skyline点删除

9.end if

10. end for

11. end for

12. return SCS

算法2依据定理1中描述的子空间Skyline结果集之间的关系，保证了结果集的有效性和正确性，对每个子空间生成一个候选集。算法的输入为正在计算的子空间V以及以V为顶点的除V外全部计算完成的子空间立方体。首先，对V下一层所有子空间（V的孩子子空间）Skyline结果集求并，并赋给SCS，时间复杂度为O(1)；之后，只需将不属于skyV的数据点从SCS中删除即可。根据定理1，判断skyU中的一个数据点p是否属于skyV，只需将skyU中与p在U上相等的数据点与p进行比较，当skyU中不存在与p 在U上相等的点时，则p一定属于skyV；如果存在这样的点，则在V-U上判定这些点中有哪些属于skyV。由于各子空间U上的Skyline结果集都是按照数据点在U上各维度数值和的非递减排序方式存储，上述操作的时间开销非常小。当SCS中不存在非skyV数据点时，为最优情况，时间复杂度为O(m lb m)，其中m为skyU所包含数据点的个数；当求得的BUF均不为空时，为最差，时间复杂度为O(m lb m+mt2)，其中t为BUF中包含的数据个数，该值一般极小。

3.3求和过滤方法

计算某一子空间V的Skyline结果集skyV时，支配关系判定过程不可避免。传统方法是将待判定数据点p与当前skyV中数据点在V空间上逐个比较，从而得出p点是否可以放入skyV，这一过程的时间复杂度为O(d)。当数据维度较高时，时间开销会很大，而该过程在算法执行过程中会被重复调用很多次。因此若能降低该过程的时间复杂度，则算法效率会大幅度提升。对此，采用求和过滤方法对该过程进行优化（对应于算法3中的第16行），该过滤条件执行的时间复杂度为O(1)，若满足该条件，则不必对数据点p进行支配关系判定。显然，通过该方法，在算法执行过程中，时间复杂度为O(d)的支配关系判定过程次数将大大减少。

该过滤条件是利用数据点在子空间V上的维度值的和进行过滤，对于某一数据点p，p在子空间V上的过滤器设计为：

该公式表明，p点在V上的过滤值为FV(p)，该值等于p点在V上所有维度值的和。通过该过滤器，很容易初步判定两个数据点p和q的支配关系，如果FV(p)≤FV(q)，显然表明q在V空间上不可能支配p，因为在V上，q至少有一个维度上的值大于p。

MSSC算法执行过程中，两处利用该过滤值提高效率。首先，所有子空间Skyline结果集中的数据点均按照该过滤值从小到大排序；此外，在计算skyV时，判定数据点p与当前skyV中数据点q的支配关系之前进行过滤条件测试，若FV(p)≤FV(q)，则显然skyV中数据点q无法支配p，并且因为skyV中数据点按过滤值非递减排序，所以q之后的点也无法支配p点，则p点直接放入skyV中即可；若FV(p)>FV(q)，才需对数据点p和q进行逐个维度上的数值比较以确定支配关系。

3.4 MSSC算法

本节提出基于子空间立方体群结构的多子空间Skyline查询算法——MSSC算法。

算法3 MSSC算法

输入：数据集S；子空间集合O={V1,V2,…,Vv}

输出：每个子空间上的Skyline结果skyV1,skyV2,…, skyVv

1.SSG←createSSG(O) //生成子空间立方体群

2.lai←sort data on each aiin the first level of SSG //将数据集S分别在SSG中的第一层各维度ai(1

3.skyai←points with min value on aiin lai

// SSG中第一层的子空间结果直接得出

4.for every SSC in the SSG do

//对于SSG中的每个子空间立方体

5.for every subspace V from level 2 to top do

//对于第二层开始到顶端的每个子空间V

6.if V is done then continue

//V已经被计算过，则跳过该子空间

7.skyV←∅

8.SCS←createSCS(V, SSC) //求出当前子空间的候选集

9.choose a list lai(ai∈V) //从当前子空间V中选一个排好序的维度序列

10.for every point p in lai

do //对于序列中的每个数据点

11.if m in (p)≥max (skyV) then continue

12.else if p∈SCS then //当前点属于候选集，直接将p放入skyV

13.insert p into skyVaccording to FV(p) //根据过滤值大小插入到skyV相应位置

14.else

15.for every point q in skyVdo

16.if FV(p)≤FV(q) then //满足求和

过滤条件，则直接将p放入skyV

17.insert p into skyVaccording to

FV(p)

18.break

19.else if q dom inate p then break

// p被q支配，则删除当前p点

20.end for

21.if skyVis end then //说明没有能支

配p的数据点，则将p放入skyV

22.insert p into skyVaccording to FV(p)

23.end for

24.end for

25.end for

26. return skyV1,skyV2,…, skyVn

如算法3所示，首先利用算法1将待求子空间集合O转化为子空间立方体群，时间复杂度为O(v lb v+2max(| |Vi))；之后将数据集分别在第一层各维度上排序，这样既可保证生成子空间候选集过程的高效性，又可直接得出第一层子空间的Skyline结果，该过程最多只要进行d次排序，相比传统算法的2d-1次排序有很大提升；接下来从第二层开始每个子空间的Skyline求解过程，均建立在已计算的所有子空间Skyline结果的基础上，先利用算法2生成当前子空间的候选集，时间复杂度为O(m lb m+mt2)，然后选取一个数据序列lai对数据集进行遍历，逐个生成每个子空间的Skyline结果（10行至23行）。

对数据序列遍历并生成结果集时，最耗时、调用最频繁的操作是数据点间支配关系判定运算（第19行），因此对该过程的优化是提高算法效率的关键所在。MSSC算法主要采用以下方法进行优化。

（1）最大值裁剪（第11行）：采用最大值裁剪方法，即数据点p在子空间V上的最小值若大于目前skyV中的最大值，则显然数据点p会被skyV中的某一点支配，因此可以直接删除这些数据点。

（2）子空间候选集过滤（第12、13行）：通过3.2节可知，子空间候选集SCS中的数据点必定为当前子空间的Skyline结果，因此这些数据点可以直接被加入到skyV中，显然子空间候选集将数据输入量从原始数据集的n减小到n-count(SCS)。

（3）求和过滤方法（第16至18行）：根据3.3节对求和过滤器的描述，当数据点p的过滤值小于等于skyV中某一点的过滤值时，说明p点不可能被skyV中任何一点所支配，因此这样的数据点p一定为当前子空间V的Skyline结果。

从上述描述可以发现，3种方法的过滤效果主要体现在两个方面：第一，3种方法将大部分数据点的复杂度为O(d)的支配关系判定操作排除，时间复杂度降低为O(1)；第二，将每个子空间的数据输入量缩减到n-count(SCS)，而越上层的子空间所对应的count(SCS)越大，效果越明显。综上所述，很容易得出MSSC算法的时间复杂度为O[vn(t1+(n-count(SCS)))]。其中v为子空间个数，n为数据点数，t1为生成子空间候选集的耗时，count(SCS)为子空间候选集中包含数据点的个数。值得注意的是，t1值较小，而count(SCS)值一般较大，因此n-count(SCS)趋近于常数。

4 实验及分析

下面验证MSSC算法的有效性及性能。目前没有专门针对同时计算多个子空间Skyline查询的算法，因此通过实验与可以解决该问题的Subsky算法和BUS算法进行对比。其中Subsky算法需要多次执行来完成多子空间Skyline计算，每次选取前n个点为anchor，设定n为10，而BUS算法将全空间作为输入执行一次即可。

MSSC算法的有效性从两方面得到证明：首先，实验利用表1中数据对算法进行测试，计算结果与表2中的理论结果相同；其次，实验过程中，MSSC算法与Subsky算法、BUS算法的执行结果相同。因此MSSC算法具备有效性。

分别采用人造数据集和真实数据集对MSSC算法进行测试，其中人造数据的生成方法在文献[1]中有介绍，分为3种：（1）相关数据集，一个数据点在某个维度上相对较优，那么在其他维度上也较优；（2）独立数据集，数据集中所有维度上的数值都是独立分布的，即各维度直接没有相关关系；（3）反相关数据集，数据点在某个维度上较优，则在其他维度上相对较差，3种数据集的全空间维数均为8维。真实数据为NBA球员技术统计数据集（http://www.basketballreference.com）。

实验分别采用查询时间和支配关系判定次数两个指标来对算法性能进行衡量。其中查询时间为从算法开始直到得出所有子空间Skyline结果的运行时间；支配关系判定次数为算法运行过程中执行的所有支配关系判定的总数，对应于算法3中的第19行。为避免随机性对实验结果产生的影响，所有结果均取10次测试的平均值。

实验所用计算机的操作系统为Windows7，CPU主频为3.3 GHz，内存为4 GB。所有算法均用C++语言实现，编译器为Visual Studio2013。

4.1数据量对算法性能的影响

为分析数据量对MSSC算法的影响，本实验采用相关、独立和反相关3种人造数据集进行测试，数据点个数n从1×105到5×105变化。系统随机生成10组子空间组合，每组包含8个子空间，其中最大维度均为6，所求时间和支配关系判定次数为10组子空间求解的平均值。

图3（a）、（b）、（c）展示了相关、独立和反相关数据集下3种算法查询时间对比。可以发现算法的耗时均随数据量增大而增加，而MSSC算法在3种情况下均明显优于其他算法，且数据量越大优越性越明显，主要是因为MSSC算法中的几种过滤机制。图4 （a）、（b）、（c）分别展示了3种算法在不同数据集下支配关系判定次数的对比。MSSC算法的表现与查询时间有着相同的特性，主要由于MSSC算法有效地避免了大量数据点的支配关系判定。此外，相关、独立和不相关数据集中包含的Skyline数据点数是依次递增的，因此3种数据集下的查询时间和支配关系判定次数也相应增加。

4.2待求子空间最大维数对算法性能的影响

从上节实验中可以发现，正相关数据集下的Skyline结果集包含的数据点数较少，算法性能均较好。因此，实验利用独立数据集和反相关数据集进行测试，数据点个数为1×105个。系统随机生成10组子空间组合，每组包含8个子空间，其中最大维度从2维到8维变化，实验采取执行时间对算法进行评估，时间为10组子空间求解的平均值。

图5（a）、（b）分别为独立数据集和反相关数据集的测试结果。可以发现Subsky算法在子空间维度较小时性能较好，而当最大维度高于6时效率会骤降。BUS算法为完成实验中的8个子空间计算，要计算数据集的所有子空间，因此查询效率只与数据的全空间维数和数据量有关，在本实验中查询时间基本稳定。而MSSC算法在子空间最大维数较小时的性能与Subsky算法不相上下，主要是因为此时子空间候选集并不能很好地发挥过滤作用，MSSC算法的共享机制无法较好地体现，而计算子空间候选集又耗费一定时间；相反，当维数较高时，性能会明显优于Subsky算法。

Fig.3 Effect of cardinality on query time under different data sets图3 不同数据集下数据量对执行时间的影响

Fig.4 Effect of cardinality on dom inance test time under different data sets图4 不同数据集下数据量对支配关系判定次数的影响

4.3待求子空间个数对算法性能的影响

本实验主要考察待求子空间个数对算法性能的影响，实验同样采用独立和反相关数据集进行测试，数据点个数为1×105个。在保证最大维数为6的条件下，实验中子空间个数从1到10变化。从上述两个实验中可以发现，在数据量和数据维度不变的情况下，BUS算法的性能不发生变化，因此本实验主要将MSSC算法与Subsky算法进行对比。

图6（a）、（b）分别为独立数据集和反相关数据集的测试结果。可以看出，Subsky是对每个子空间分别计算，因此该算法的查询时间几乎与子空间个数成正比。而MSSC算法在子空间个数增长时，子空间立方体的数目不会过多增长，因此算法时间并不会成倍增加。此外，在独立数据集下，当子空间个数小于3时，MSSC算法并不优于Subsky算法。这主要是由于MSSC算法执行之前要做一部分准备工作，当子空间个数较少时，算法的性能不能很好地体现，而个数增加后，准备工作的作用将很好地展现，因此性能会远高于多次执行的Subsky算法。

4.4真实数据下的算法性能

Fig.5 Effect of max dimensionality on query timeunder different data sets图5 不同数据集下最大查询维数对查询时间的影响

Fig.6 Effect of subspace number on query timeunder different data sets图6 不同数据集下子空间个数对查询时间的影响

图7和图8为真实数据下的实验结果，可以发现测试结果与人造标准数据下的结果保持一致。其中，BUS算法由于数据量和数据全空间维度均未发生改变，性能平稳；Subsky算法性能依然随子空间个数和最大维度的增加而大幅下降，MSSC算法在高维和多子空间条件下均呈现优良性能。

Fig.7 Effect of subspace number on query time图7 子空间个数对查询时间的影响

Fig.8 Effect of max dimensionality on query time图8 最大维数对查询时间的影响

5 结束语

本文从用户多角度审视数据集的需求出发，提出了一种针对多子空间Skyline查询问题的解决方案。首先，提出了子空间立方体群的概念，并给出由待求子空间集合生成子空间立方体群结构的算法；基于该结构，提出了一种同时处理多个子空间Skyline查询的算法——MSSC算法，有效地解决了多子空间Skyline查询问题。算法实施过程中，充分利用共享孩子子空间Skyline结果集的方法，直接将子空间候选集中的数据放入结果集，减少了支配关系判定次数；此外，算法还采用最大值剪枝、求和过滤等方法进一步降低支配关系判定次数，有效地提高了算法效率。最后，利用多个数据集对MSSC算法性能进行全方位的评估。实验结果显示，MSSC算法解决了现有子空间Skyline算法在解决多子空间Skyline查询问题时的不足，具有明显的优势。

下一步研究工作将重点关注如何将MSSC算法用于云平台，以实现分布式环境下的多子空间Skyline查询。

References:

[1] Borzsony S, Kossmann D, Stocker K. The skyline operator [C]//Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Germany, 2001. Piscataway, USA: IEEE, 2001: 421-430.

[2] Deb K. Multi-objective optim ization[M]//Search Methodologies. New York: Springer US, 2014: 403-449.

[3] Tao Yufei, Xiao Xiaokui, Pei Jian. Subsky: efficient computation of skylines in subspaces[C]//Proceedings of the 22nd International Conference on Data Engineering, Atlanta, USA, 2006. Piscataway, USA: IEEE, 2006: 65.

[4] Yuan Yidong, Lin Xuem in, Liu Qing, et al. Efficient computation of the skyline cube[C]//Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway,Aug 30-Sep 2, 2005: 241-252.

[5] Pei J, Jin W, Ester M, et al. Catching the best views of skyline: a semantic approach based on decisive subspaces[C]// Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, Aug 30-Sep 2, 2005: 253-264.

[6] Chomicki J, Godfrey P, Gryz J, et al. Skyline with presorting: theory and optimizations[C]//Proceedings of the 2005 International Conference on Intelligent Information Processing and Web M ining, Gdansk, Poland, Jun 13-16, 2005. Berlin, Heidelberg: Springer, 2005: 595-604.

[7] Wang Xiaowei, Huang Jiuming, Jia Yan. Probabilistic Skyline computation on distributed uncertain data[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4 (10): 951-960.

[8] Tan K L, Eng P K, Ooi B C. Efficient progressive skyline computation[C]//Proceedings of the 27th International Conference on Very Large Data Bases, Roma, Italy, Sep 11-14, 2001: 301-310.

[9] 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, 2002: 275-286.

[10] Tao Yufei, Xiao Xiaokui, Pei Jian. Efficient skyline and topk retrieval in subspaces[J]. IEEE Transactions on Know ledge and Data Engineering, 2007, 19(8): 1072-1088.

[11] Dellis E, Vlachou A, V ladimirskiy I, et al. Constrained subspace skyline computation[C]//Proceedings of the 15th International Conference on Information and Know ledge Management, Arlington, USA, Nov 6-11, 2006. New York, USA:ACM, 2006: 415-424.

[12] Jin Wen, Tung A K H, Ester M, et al. On efficient processing of subspace skyline queries on high dimensional data[C]// Proceedings of the 19th International Conference on Scientific and Statistical Database Management, Banff, Canada, 2007. Washington, USA: IEEE Computer Society, 2007: 12. [13] Pei Jian, Fu A W C, Lin Xuem in, et al. Computing compressed multidimensional skyline cubes efficiently[C]//Proceedings of the 23rd International Conference on Data Engineering, Istanbul, Turkey, Apr 15-20, 2007. Piscataway, USA: IEEE, 2007: 96-105.

[14] Xia Tian, Zhang Donghui. Refreshing the sky: the compressed skycube w ith efficient support for frequent updates [C]//Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, Chicago, USA, 2006. New York, USA:ACM, 2006: 491-502.

[15] Kailasam G T, Lee J S, Rhee J W, et al. Efficient skycube computation using point and domain-based filtering[J]. Information Sciences, 2010, 180(7): 1090-1103.

[16] Banafaa K M, Li Ruixuan. Efficient algorithms for constrained subspace skyline query in structured peer-to-peer systems[C]//LNCS 7418: Proceedings of the 13th International Conference on Web-Age Information Management, Harbin, China, Aug 18-20, 2012. Berlin, Heidelberg: Springer, 2012: 334-345.

[17] Lee J, Hwang S. Toward efficient multidimensional subspace skyline computation[J]. The VLDB Journal, 2014, 23 (1): 129-145.

[18] Vlachou A, Doulkeridis C, Kotidis Y, et al. Efficient routing of subspace skyline queries over highly distributed data[J]. IEEE Transactions on Know ledge and Data Engineering, 2010, 22(12): 1694-1708.

附中文参考文献：

[7]王晓伟,黄九鸣,贾焰.分布式不确定数据上的概率Skyline计算[J].计算机科学与探索, 2010, 4(10): 951-960.

WANG Xiaoyi was born in 1992. He is an M.S. candidate at Nanjing University of Aeronautics and Astronautics. His research interests include data management and query, distributed database and cloud computing, etc.

王潇逸（1992—），男，吉林公主岭人，南京航空航天大学计算机科学与技术学院硕士研究生，主要研究领域为数据管理与查询，分布式数据库，云计算等。

QIN Xiaolin was born in 1953. He is a professor and Ph.D. supervisor at Nanjing University of Aeronautics and Astronautics, and the senior member of CCF. His research interests include spatial and spatio-temporal databases, data management and security in distributed environment, etc.

秦小麟（1953—），男，江苏南京人，南京航空航天大学教授、博士生导师，CCF高级会员，主要研究领域为空间与时空数据库，分布式数据管理与安全等。

WANG Ning was born in 1987. He is a lecturer and Ph.D. candidate at Nanjing University of Aeronautics and Astronautics. His research interests include data management and secure localization for w ireless sensor network, etc.

王宁（1987—），男，山东威海人，南京航空航天大学讲师、博士研究生，主要研究领域为数据管理，无线传感器网络位置安全等。

SHI Wenhao was born in 1988. He is an M.S. candidate at Nanjing University of Aeronautics and Astronautics. His research interests include access control and cloud computing, etc.

史文浩（1988—），男，河北衡水人，南京航空航天大学计算机科学与技术学院硕士研究生，主要研究领域为访问控制，云计算技术等。

Efficient Algorithm for M ultiple Subspace SkylineQueries Processingƽ

WANG Xiaoyi+, QIN Xiaolin, WANG Ning, SHI Wenhao
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
+ Corresponding author: E-mail: xywang515829@nuaa.edu.cn

WANG Xiaoyi, QIN Xiaolin, WANG Ning, et al. Efficient algorithm for multip le subspace Skylinequeriesprocessing. Journal of Frontiersof Computer Scienceand Technology, 2016, 10(5)：623-634.

Abstract:As Skyline queries are w idely used, subspace Skyline query processing has attracted lots of attention. Aiming at meeting the need that users want to evaluate a dataset from multiple perspectives, this paper makes a full study of multiple subspace Skyline queries. Motivated by the deficiency of existing algorithms, this paper proposes the structure of subspace skycube group, and puts forward an efficient method called MSSC (multiple subspace skycube) based on that structure. The MSSC algorithm can efficiently process any number of subspace Skyline queries simultaneously. Firstly, the MSSC algorithm uses subspace candidate sets to share the results of different subspace Skyline queries in the subspace Skycube group. Then it adopts sum filter and max-value filter to cut and filter data, which further improves the performance of the MSSC algorithm.At last, the experiments conducted on both synthetic data sets and a reallife data set demonstrate that the MSSC algorithm can solve the multiple subspace Skyline queries problem efficiently. Key words: multiple subspace Skyline queries; subspace list; subspace skycube group; subspace candidate set

doi:10.3778/j.issn.1673-9418.1507073

文献标志码：A

中图分类号：TP311