一种分布式环境中的二分式多层网格skyline算法

丁日强

渤海大学 信息科学与技术学院，辽宁 锦州 121000

一种分布式环境中的二分式多层网格skyline算法

丁日强

渤海大学 信息科学与技术学院，辽宁 锦州 121000

1 引言

近年来，由于skyline在多维数据集中的诸多应用，人们对skyline查询处理的兴趣已经越来越大。给定一个数据集P包含对象P={P1，P2，…，Pn}，skyline查询处理可以返回所有Pi值，其中对象Pi不受另一个对象Pj控制（所谓控制关系是指：如果对象p至少在某一维上优于另一对象q，而在其他维上都不比对象q差，则说p能够控制q）。之前的研究主要侧重于如何获得高效的集中式skyline查询算法，像文献[1-4]所提到的算法均是这样的。然而，在实际中，大量的独立数据往往是存储在不同的分布式服务器上的。图1显示了在分布式环境下的skyline查询：skyline查询是由用户通过查询服务器（Query Server，QS）发起的，skyline查询的分析结果是通过收集所有连接服务器的数据得到的。比如现在要买一辆车，就是一种类似于分布式环境下的skyline查询，需要根据各辆车的价格，质量，安全性等多个标准，从各个不同的售车网站获得各种信息，最终买到满意的车辆。这种多重标准信息的综合捕捉就需要利用一种分布式体系结构来解决，从而避免产生太大的数据访问。

图1 分布式环境下的skyline查询示意图

处理分布式skyline查询最简单的办法就是发送查询要求给所有连接的本地服务器，然后各个本地服务器自行处理查询要求，并将处理结果反馈给查询服务器（QS），查询服务器（QS）综合收到的查询结果得出一个最终的全局skyline查询结果。这种方法需要传输和处理大量不必要的重叠数据，这些数据是本地skyline查询要利用的数据，而不是全局skyline查询要利用的数据。Joao B等人在文献[5]中提出了一种基于网格的分布式skyline查询处理策略（AGiDS），使用基于网格的数据结构，获得每个服务器中的数据。该方法的思想是发送包含本地skyline数据的信息元组给查询服务器（QS），而不是发送本地skyline数据给查询服务器（QS），在查询服务器（QS）中被控制的局部信息元组首先被淘汰，然后只有未受控制的信息元组中的局部skyline查询数据传送到查询服务器（QS）中。但是，如果发送到查询服务器（QS）的本地服务器信息元组有重叠，很多不必要的数据就需要被处理。

在本文中，提出了一种在分布式环境中的二分式多层网格skyline查询算法（DMLG）。该方法假定每个服务器共享一个共同的网格结构，查询服务器（QS）首先收集包含本地skyline数据的信息元组，如果有的信息元组是重叠的，采用的方法是建立一个基于重叠信息元组的多层网格，利用这种多层网格机制，很多不必要的本地数据在转移到查询服务器进行处理之前就会被过滤掉，所以会大大提高查询的效率。

2 相关工作

对于skyline查询计算，一般分为集中式skyline查询计算和分布式skyline查询计算。集中式skyline查询计算提出较早，也已经有了较深入的研究，已经有了许多有效的skyline查询计算的算法，例如块嵌套环算法（BNL）、排序过滤算法（SFS）、最近邻算法（NN）等等。文献[1]中提出了块嵌套环算法（BNL），BNL算法在内存中用一个窗口保存那些暂时不被任何其他点所控制的点，BNL会把窗口组织为一个自组织列表，这种方法是对数据库中所有点两两比较的一种最简单的优化方法；文献[1]中同时提出了分治法（D&C），D&C的思想是每次将数据集沿某一维分成D1和D2两个部分，分别计算D1与D2上的skyline查询结果，采取的方法是在D1和D2上分别递归调用D&C算法，直到每一个子部分都划分到足够小，小到能快速计算出skyline查询结果为止，再将D1和D2上的skyline结果归并在一起，除去不符合条件的点，最终得到整个数据集的skyline查询结果。文献[2]中提出了排序过滤算法（SFS），其思想是将全部数据点按单调函数排序，任何一个排在前面的点都不会被排在后面的点所控制。经过排序之后再使用 BNL算法；文献[3]中提出了最近邻算法（NN），NN算法是第一个用户友好的 skyline查询算法，其基本思想是利用搜索到的最近邻居来递归地划分数据空间，同时需要对全部待测数据集建立一个R-tree索引，NN算法能够顺序返回用户规定的skyline点，具有较好的用户友好性。文献[4]中提出了另一种集中式skyline查询算法：分枝界限算法（BBS），BBS算法与NN算法相似之处是该算法也是基于最近邻搜索的，而且同样采用了R树对数据进行索引，而且可以通过改变最小距离公式很好地适应用户的不同需求。因此，从性能的各个方面来讲，BBS被认为是当前最优的集中式skyline查询计算算法。

然而，实际中的数据量很大，数据源很多且在距离上一般会相距较远，这时把所有数据放在一个单独的服务器上存储和处理就不是一个理想的方法了。文献[6]提出了解决在多个分布式来源下的skyline查询算法，算法的基本关系是垂直分区的，即每个服务器只保留关系中的一个属性。在本文中，侧重于横向分区，即每个服务器包含所有的属性，但仅存储所有属性中的一个子集。文献[7]提出了分布式环境中skyline查询计算的最小边界区域法（MBRs），分别计算每个服务器上存储的数据，根据所有服务器的计算结果最终得到最后的理想结果。文献[8]中提出了反馈式skyline查询算法（FDS），FDS算法有效降低了传输大量的非skyline点数据，节省了带宽成本。但是有些skyline点数据总是需要重复去计算，因此会产生较长的响应时间。文献[5]中提出了一种基于网格的分布式skyline查询处理算法（AgiDS），该方法在分布式服务器中采用并行计算的方法，响应时间较快。但是，如果本地服务器发送到查询服务器（QS）的数据重叠，这种方法就不能有效地减少这些重叠数据的传输了，这些数据只需在本地服务器进行skyline查询计算处理，而不需要传输到查询服务器（QS）进行全局的skyline查询计算处理。文献[9]提出的算法同样是基于网格的算法（MGDS），是在文献[5]的基础上提出的关于处理数据重叠的一种改进算法，但文章中关于重叠数据的处理算法随意性太大，不同的人对重叠数据进行处理的结果不同，而且结果可能相差很远。

3 二分式多层网格skyline查询算法

3.1 基本思想

如前所述，如果发送到查询服务器（QS）的本地服务器信息元组有重叠，方法AgiDS及MGDS都不能有效地减少重叠数据的传输，因此，提出了一种在分布式环境中的二分式多层网格skyline查询算法（DMLG），假设每个服务器共享一个包含全部数据集的网格，给定一组分布式服务器S={S1，S2，…，Si}。每个服务器存储全部数据集中的一部分数据元组，并且每个服务器有能力针对自己存储的数据元组进行本地的skyline查询计算，用户发起skyline查询的服务器称做查询服务器（Query Server，QS）。为了有效地对skyline查询结果进行评估，本文所述方法定义了在二维空间中，各单元格由每个单元格的左下角坐标唯一确定，即单元格Di坐标=（左下角横坐标，左下角纵坐标），在网格中各单元格之间有以下三种控制关系：

（1）单元格A控制单元格B：如果单元格A的坐标小于单元格B的坐标。

（2）单元格B控制单元格A：如果单元格B的坐标小于单元格A的坐标。

（3）单元格A与单元格B重叠：如果单元格A的坐标等于单元格B的坐标。

注：所谓单元格A的坐标小于单元格B的坐标，指单元格A的左下角横坐标或左下角纵坐标小于B的左下角横坐标或左下角纵坐标，即包含以下三种情况：

（1）单元格A与单元格B横坐标相等，单元格A的纵坐标小于单元格B纵坐标。

（2）单元格A与单元格B纵坐标相等，单元格A的横坐标小于单元格B横坐标。

（3）单元格A的横坐标和纵坐标都小于单元格B的横坐标和纵坐标。

如果单元格B被单元格A控制，就意味着单元格B中的所有数据元组都被单元格A中的任意一个数据元组所控制。定义包含skyline数据点的数据元组为本地skyline，如图2深色区域所示。如果本地局部skyline在不同的服务器上发生重叠，定义这些重叠的数据元组为本地重叠skyline，如图2中的单元格A和单元格B。在所述的二分式多层网格skyline查询算法中，将本地重叠skyline包含的数据按重叠程度降序排列，将重叠程度在序列前半部分的重叠本地skyline定义为高度重叠本地skyline，如图2中的单元格A和单元格B等。

图2 DMLG算法的处理过程

3.2 DMLG算法的处理过程

DMLG的处理过程分为三个基本步骤：计划，分析，执行。在计划的开始阶段，skyline查询首先由查询服务器（QS）发起，各个服务器收到skyline查询要求后，就利用当前的网格算法计算它本地的局部skyline。然后查询服务器联络各个连接的服务器，得到每个服务器上的局部skyline结果信息。分析阶段，在查询服务器中分析接收到的单元格内数据，并对全局skyline作出评估，如果在所连接的服务器中出现了高度重叠局部skyline，则处理的方法是把它们放大到一个更高一层的网格。如图2所示，在服务器S1和S2中，单元格A都是高度重叠的局部skyline，则会被转移到更高一层的网格中去处理，而且单元格A中的数据点的管理和计算都是在它所在的高层网格中进行的。然后，查询服务器（QS）收集高层网格的当地局部skyline，并计算到全局skyline。如果在高一层的网格中还是有高度重叠本地skyline发生，则再把它放大到更高一层去处理。注意到图2中，虽然单元格C在服务器S1和单元格D在服务器S2中也是本地skyline重叠的，但它却不转移到更高一层的网格中去处理，这是因为在单元格C和单元格D中只有很少的数据，在低层中处理这些数据比在高层网格中处理更有效率。在执行阶段。存在于每个服务器的全局skyline数据点进行最终的全局skyline计算。至此，由于大多数不必要的本地skyline数据点被过滤掉，该方法大大减少了信息的交换和处理时间。

为了更形象地理解所述方法，举一个DMLG的例子，如图2描述的一样，假设每个服务器都有一个二维的数据集，网格是由3×3的单元格组成的。

在计划阶段，服务器S1中的单元格A，B，C和服务器S2中的单元格A，B，D被作为本地skyline被发送到查询服务器进行计算。分析阶段，在查询服务器中除去那些被控制的本地skyline。因为单元格A是高度重叠的区域skyline，所以它需要被放大到更高一层的网格中处理，单元格A中的数据也是在高一层的网格中处理的，在服务器S1和S2中分别各自计算本地高一层网格A-1，A-2，A-3，A-4，A-5和A-6的skyline。查询服务器（QS）收集高层网格的本地skyline，并计算入全局skyline。由于服务器S1中的单元格A-3和服务器S2中的单元格A-5，A-6被服务器S1中的单元格A-1，A-2和服务器S2中的单元格A-4所控制，所以不属于全局区域skyline。因此，在这个例子中，属于全局区域skyline的单元格有：服务器S1网格中的单元格A，C，A-1，A-2及服务器S2网格中的单元格A，D，A-4。在执行阶段，只有这些单元格中的本地skyline数据被发送到查询服务器进行最后的全局skyline计算。

4 实验结果与分析

4.1 实验描述

在这一节中，将介绍所述方法的性能，实验与文献[4]所述方法MGDS和传统方法作对比。表1显示为实验的参数。

表1 实验的参数

在这个实验中，要用到两种用于skyline算法测试的数据分布类型用来判定skyline计算方法的有效性，分别是反相关数据集和独立数据集。在独立数据集中，各个维度在取值上互不相关。在反相关数据集中，由于各维度的数值之间是反相关的关系，任意一个数据点在某个维度上数值很高，则会在另外一个维度上数值较低。

4.2 实验结果

设定所有分布式服务器都相互连接，并且每个服务器拥有相等数量的数据点，每个服务器中的数据点分散在整个网格的30%范围内。第一个实验，测试的性能是在网络上传输的总数据量。研究的方法是在各个服务器上改变数据元组的数量，大小为从10×103逐渐到200×103，数据的维度设定为2维。图3的结果显示DMLG方法比MGDS和传统方法都要好，这是因为非skyline的数据点被这种二分式多层网格机制过滤掉了，从而减少了总的数据传输量。

图3 不同数据大小的数据总传输量

图4显示的是三种方法根据不同数据大小所产生的响应时间。在这个实验中，数据的维数同样设定为2维，数据的大小范围为10×103～200×103。从图所示结果可以看到，随着数据元组的增加响应时间急剧上升，这是因为随着数据的增加，需要更高的处理成本，从而延长了处理的时间。不管是对反相关数据集还是独立数据集，DMLG方法的响应时间比传统方法和MGDS方法都要少，这是因为这种方法处理的数据比起另两种方法都减少了很多。

图4 不同数据大小的响应时间

图5所示为根据数据不同维数三种方法的响应时间对比。在这个实验中，数据大小设定为10 000，在每个服务器上，逐渐增加数据集的维度并分别测定结果。从图中可以看到，随着维度的增加MGDS方法和传统方法响应的时间比DMLG方法增加得更快。这是因为随着维度的增加前两种方法需要处理数据增加越来越快。

图5 不同维数的响应时间

5 结论与展望

本文研究了水平分区数据集的skyline查询计算，由于相关的数据分散在几个不同的服务器上，因此分布式环境中的skyline查询，需要在各个连接的分布式服务器中收集大量的数据，本文所提方法DMLG利用多层网格的方法，借鉴二分法来处理分布式数据，这样在发送到查询服务器进行最终全局skyline计算之前可以过滤掉许多不必要的本地非skyline数据，从而提高了查询效率。实验结果表明所述方法比现有方法的效果要好。

将来比较重要和感兴趣的后续工作包括：如何进一步在进行最终全局skyline计算之前可以过滤掉更多的本地非skyline数据，以及如何采用更优秀的方法降低查询的时间和提高查询效率。

[1]Borzonyi S，Kossmann D，Stocker K.The skyline operator[C]// 17th International Conference on Data Engineering.Heidelberg：ICDE Press，2001：421-430.

[2]Chomicki J，Godfrey P，Gryz J.Skyline with presorting[C]// Proc of ICDE，2003：717-816.

[3]Kossmann D，Ramsak F，Rost S.Shooting stars in the sky：an online algorithm for skyline queries[C]//Proc of VLDB，2002：275-286.

[4]Papadias D，Tao Y，Fu G，et al.An optimal and progressive algorithm for skyline queries[C]//Proc of Sigmod，2003：467-478.

[5]Rocha-Junior J B，Vlachou A，Doulkeridis C，et al.AGiDS：a grid-based strategy for distributed skyline query processing[C]// Second International Conference on Data Management in Grid and Peer to Peer Systems，Globe 2009，Linz，2009：12-23.

[6]Balke W T，Güntzer U，Zheng J X.Efficient distributed skylining for web information systems[C]//Hwang J，Christodoulakis S，Plexousakis D，et al.LNCS 2992，EDBT 2004，2004：256-273.

[7]Cui B，Lu H，Xu Q，et al.Parallel distributed processing of constrained skyline queries by filtering[C]//24th International Conference on Data Engineering，ICDE 2008，Cancun，2008：546-555.

[8]Zhu L，Tao Y，Zhou S.Distributed skyline retrieval with low bandwidth consumption[J].TKDE，2009，21：384-400.

[9]Li He，Jang Sumin，Yoo J.An efficient multi-layer grid method for Skyline queries in distributed environments[C]//LNCS 6637：DASFAA Workshops，2011：112-119.

[10]Zhu Lin，Guan Jihong，Zhou Shuigeng.Skyline computation：survey[J].Computer Engineering and Applications，2008，44（6）：160-165.

[11]Chan C Y，Jagadish H V，Tan K L，et al.Finding k-dominant skylines in high dimensional space[C]//Proc of SIGMOD，2006：503-514.

[12]Chan C Y，Eng P K，Tan K L.Stratified computation of skylines with partially ordered domains[C]//Proc of SIGMOD，2005：203-214.

[13]Tao Y，Papadias D.Maintaining sliding window skylines on data streams[J].IEEE Trans on KDE，2006，18（2）：377-391.

DING Riqiang

College of Information Science and Technology,Bohai University,Jinzhou,Liaoning 121000,China

In recent years,the skyline query has

more and more attention.This is because of its importance in many applications involving database visualization multi-criteria decision making,data mining and so on.Most of the previous works have put their attention on processing skyline queries on centralized data sets which is called centralized skyline query,and many research results have got.However,the reality is that the related data practically scatter at several different servers.The skyline query computation needs to gather a lot of data from the connected servers in distributed environment.The existing methods for distributed skyline query computation have two problems:firstly,their processing time for a skyline query is slow;secondly,they transfer many unnecessary data among servers in the network.This paper proposes a Dichotomous Multi-Layer Grid method（DMLG）.The proposed method based on the grid mechanism uses the dichotomy to minimize the unnecessary transferred data.Experiments based on different data sets show that this proposed method is better than the existing methods.

skyline query;distributed skyline query;distributed data;dichotomous multi-layer grid

skyline计算在数据挖掘、多标准决策和数据库可视化等领域有着非常重要的作用，这些年已经得到了广泛的关注，以往对于skyline查询的研究大多集中在处理集中的数据集上，即集中式skyline查询，已经得到了很多的研究成果。然而，实际情况是：相关数据几乎分散在几个不同的服务器上，因此在分布式环境中的skyline查询计算需要从各个服务器收集大量的数据；现有的在分布式环境中的skyline查询方法有两个主要问题：一是skyline查询的处理时间较慢；二是在网络中服务器之间传输了很多不必要的重叠数据。提出了一种二分式多层网格法（DMLG），可以有效地处理在分布式环境中的skyline查询。该方法利用网格的方法，借鉴二分法，最大限度地减少了不必要的重叠数据传输，基于不同的数据集的实验表明，这种方法优于现有的方法。

skyline查询；分布式skyline查询；分布式的数据；二分式网格法

A

TP311

10.3778/j.issn.1002-8331.1203-0083

DING Riqiang.Dichotomous multi-layer grid method for skyline query in distributed computing environments.Computer Engineering and Applications,2013,49（18）：116-119.

辽宁省教育厅项目（No.L2010006）。

丁日强（1987—），男，硕士生，主要研究领域为数据挖掘技术，skyline计算。E-mail：drq211314@163.com

2012-03-05

2012-07-09

1002-8331（2013）18-0116-04