一种分布式环境下的skyline查询算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种分布式环境下的skyline查询算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要: skyline 计算在多标准决策、数据挖掘和数据库可视化等领域具有非常重要的作用.研究了分布式环境下的skyline查询问题.提出通过合并局部skyline集合得到全局skyline集合的思想，在计算全局skyline集合时，先对局部skyline集合进行区域划分和动态编码，然后根据各个区域之间的制约关系进行数据合并.通过实验分析可知，当全局skyline集合的规模较大时，经过区域划分的算法比起直接合并的算法执行效率更好.

关键词: skyline计算；区域划分；动态编码

中图分类号:TP311.13

文献标识码:A文章编号:1672-8513(2010)05-0325-04

An Algorithm for Distributed Skyline Queries

YAN Weiyu1,2,ZHOU Lihua1，ZHAO Jiasong2

(1. School of Information Science and Engineering, Yunnan University, Kunming 650091, China; 2. School of Science and Information Engineering, Yunnan Agricultural University, Kunming 650201, China）

Abstract: The skyline computation has played a significant role in the fields of multi-criteria decision making, data mining and database visualization. This paper focuses on studying distributed skyline queries and provides a new algorithm, that is, while calculating global skyline sets, region division and dynamic coding are used first in part skyline sets; then, data are combined according to the limiting relation in each region. Through analyzing experimental results, it reaches the conclusion that the algorithm making use of region division is more efficient than the direct merge algorithm when the global skyline sets scale is large.

Key words: skyline computation；region division；dynamic coding

Skyline计算就是从一个数据集中找到不被其他数据点支配的所有点的集合.如果一个数据a支配另一个数据b，那么a的每一维属性值都不比b对应属性值“差”，而且必须至少有一个属性值比b的“好”.“差”和“好”无统一定义，[PS严伟榆1；S*2；Z1，Y，PZ]可以根据用户的选择和喜好定义.例如，一个游客到了某个海滨城市，当他在选择旅馆时，希望找一家的价格相对便宜而其距离海边的距离相对近一点的旅馆.如图1每个点代表一个旅馆，横坐标和纵坐标分别表示该旅馆的价格及其到海边的距离.显然如果旅馆a与b相比其价格便宜且距离海边更近，则a比b好（a支配b），但通常情况下距离海边越近的旅馆其房价也越高.skyline操作返回的旅馆集合在图中用黑点标识，非skyline集合中没有一个旅馆在价格和距离上比这些skyline集合中的更优，故游客只需考虑skyline集合中的旅馆.

近年来，skyline 查询逐渐成为数据库领域的一个研究热点，它在多标准决策、数据挖掘、数据库可视化和偏好查询等领域具有潜在的应用前景.最近10 年, 国内外对skyline 计算及其相关问题的研究主要包括3个方面:①集中式数据库上的skyline 计算，已有的算法包括文献［1］中的块嵌套环算法(BNL)和分治算法(D&C)、文献［2］中的位图算法(Bitmap)和索引算法(Index)、最近邻算法［3］ (NN)、分枝界限算法［4］ (BBS)等;②分布式数据库上的skyline 计算,已有的算法包括普通分布式环境下的skyline 计算［5］、移动自组织网络［6］下的skyline 计算和文献［7］中的关于对等网络(P2P) 上的skyline计算等;③其它skyline 计算:任意子空间上的skyline 计算［8］、在所有子空间上的skyline 计算［9-10］ (skycube)、在数据流上的skyline计算［11］等.

本文主要讨论的是普通分布式环境下的的skyline 计算，与文献［5］中的数据呈垂直分布所不同的是本文中的数据是水平分布的.针对如何将局部skyline子集合并成全局skyline集合这个问题，提出了一种“区域划分”的合并思想，并通过实验证明了算法的有效性.

1 问题描述

文献［5］提出了第1个分布式数据库上的skyline算法，此算法适用于数据垂直分布的情况，即数据对象的各个维度值分别存放在不同的服务器上.算法思想是：首先将各维上的数据排序，然后用轮循的方式依次访问各维，直到某一个数据点p通过此按序访问在各个维度上都被访问到为止.此时可以将所有还未在任何维度被访问过的数据点除去，因为它们都被点p所支配，skyline集合一定包含在已经被访问到的对象集合中.

与文献［5］不同，本文考虑的是数据水平分布的情况，即数据集合随机的分布在不同的服务器中.因为当一个数据点p是一个全局skyline点时，它一定也属于某个局部skyline集合，所以当用户需要进行全局的skyline查询时，可以先访问各个局部服务器计算出局部skyline集合，再把局部结果上传到核心服务器上进行下一步全局结果的查询，系统结构如图2所示.

2.1 skyline的定义

定义1 支配关系,设在数据集A的维度为d.A中存在2个对象q1,q2，各维度上的值分别为( x1, x2, …, xd)和(y1, y2, …, yd），若i,xi≤yi都成立，且j满足xj＜yj(1≤i,j≤d)，则称q1支配q2，表示为Dominate(q1,q2).各个维度上的支配关系应由具体的需求而定，为了描述方便，本文假定各个维度上的支配关系统一为“

定义2 skyline集合,所有不被任何其它点所支配的点的集合称为skyline集合，简称SP.在此定义局部的 skyline集合为SPi.

2.2 BNL算法

文献［12］对已有集中式的skyline查询算法做了详细的说明和比较，集中式skyline查询可分为不带索引和带索引两大类，BNL属不带索引算法.此算法的优点是实现简单，适用于任何维的数据，无须对数据进行任何索引或预处理.它满足skyline计算算法对正确性、公平性的要求.

BNL算法的基本思想是：在内存中设置一个窗口保存当前不被其它点所支配的点.读取数据p与窗口内的点一一比较.此时，比较的结果有3种可能：

1）p点被窗口中的1个点支配.此时p点一定是非SP点，直接丢弃;

2）p点支配窗口中的1个或多个点.将被支配点从窗口中删除，同时将p点插入窗口;

3）p点与窗口中的所有点都不存在支配关系.此时，如果窗口中有足够的空间，就将p点插入窗口队列中，若空间不够，则将p点写入一个临时队列中.

假设第1个插入到临时队列的是m点，当所有的数据都被访问了一遍时，可以确定窗口中所有在m点之前被访问到的点一定是skyline点，可以直接输出.然后将临时队列中的数据点与窗口中的剩余数据点进行下一轮比较，直到临时队列为空.

3 区域划分与多窗口收集算法

3.1 区域划分思想

首先需要确定一个划分点，可以先对各个局部skyline集合的每一维度求出1个平均值，由所有维度的平均值构成1个局部的中值.然后把所有的局部中值再进行1次平均得到1个全局中值作为划分点.为了便于描述，这里用av(x1,x2,…,xn)表示全局中值，用SP表示skyline集合，第i个局部skyline集合就是SPi ，同时以三维数据空间作为操作对象.

用全局中值av(x1,x2,…,xn)对SPi中的数据点进行二叉区域划分，在划分的过程中同时对区域进行动态编号.划分的原则是：从第1维开始逐层划分，如果p(x1)

3.2 划分区域之间的制约关系描述

以三维数据为例，在任意2个局部服务器上的对应8个区域： S110,S101,S100,S011,S010,S001,S000,S111 中：

1） 除编号为000和111的区域之外，在任何2台局部服务器上的区域如果其编号互逆的区域一定不存在制约关系.如在局部服务器Qi 上的划分区域S110和服务器Qj 上的划分区域S001中的数据没有制约关系;

2） 在任何2台局部服务器上的区域如果其编号不同但是1的个数相同的区域不存在制约关系.如在局部服务器Qi 上的划分区域S110和Qj 上的划分区域S011中的数据一定不存在制约关系;

3） 特殊区域S111和S000:在每个局部服务器上的SPi进行区域划分时，区域S111和S000至多只有1个区域不空;

4） 在任何2台局部服务器上，相同编号的划分区域之间的支配关系是双向的.例如，Qi 上的划分区域S110 可能存在数据对象制约Qj 上的划分区域S110中的数据对象，反之亦然;

5）在任何2台局部服务器上，编号中1的个数多的划分区域单向支配编号中1的个数少的划分区域.例如，Qi 上的划分区域S110 可能存在数据对象制约Qj 上的划分区域S100中的数据对象；但是Qj 上的划分区域S100中一定不存在数据对象制约Qi 上的划分区域S110中的数据对象.

在合并局部skyline集合计算全局skyline集合时，可以根据以上5个规则按区域进行合并，对于没有制约关系的区域可以不再进行制约判断，直接合并；对相同编号的区域采取双向制约判断，删除非全局skyline点；用编号中1的个数多的区域对编号中1的个数少的区域进行单向支配判断，删除非全局skyline点.

[PS严伟榆3；S*2；X*2，BP]

4 实验分析

实验环境：CPU主频为3.0GHz，内存为2GB，硬盘是WD7200转／500GB的PC机；操作系统是Microsoft Windows XP Professional SP2，编程语言选用的是Microsoft Visual C# 2005.

实验平台的部署：在1台PC机上模拟生成了1个核心服务器端和3个局部服务器端.

测试数据集：实验对独立数据、正关联数据和反关联数据3类数据进行测试，数据随机生成.

实验在三维数据空间下对以下2个算法进行比较分析.

1）计算出各个服务器上的局部skyline集，然后汇总到核心服务器上，再用一次BNL算法计算全局skyline;

2）计算出各个服务器上的局部skyline集，然后汇总到核心服务器上，采用“区域划分和多窗口收集”算法计算全局skyline.

为了便于描述，以下称算法1）为DC算法，算法2）为PC算法.图4反映了3类数据集上当数据集合增大时，PC算法和DC算法的时间效率.[JP2]图4中，横坐标表示数据集合的大小/个，纵坐标表示时间/s.[FL）]

[PS严伟榆4；S*2；X1，BP，DY#]

[FL（K2] 实验结果分析：从图4中可以看出，在正关联数据集和独立数据集上，2个算法执行效率相当.在反关联数据集上，当待测数据集较大时，PC算法的执行效率较DC算法有一定改善.说明待测数据集的类型对算法有一定的影响，当全局skyline集合的规模增大时，PC算法的执行效率较高.

5 结语

本文提出的分布式数据库下当数据水平分布时，通过对局部skyline集合进行区域划分编码后再进行全局skyline查询的算法，可以在合并环节减少数据的匹配次数.实验结果表明当全局skyline集合的规模较大时，算法执行效率有所提高.下一步的研究工作将就高维数据集下的查询和skyline的并行计算展开.

参考文献:

［1］BORZSONYI S, KOSSMANN D, STOCKER K. The skyline operator ［C］//Proc of ICDE. 2001: 421- 430.

［2］TAN K L, ENG P K, OOI B C. Efficient progressive skyline computation［C］//Proc of VLDB. 2001: 301- 310.

［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］BALKE W T, GUNTZER U, ZHENG J X. Efficient distributed skylining for web information systems［C］//Proc of EDBT. 2004: 256- 273.

［6］HUANG Z Y, JENSEN C S, LU H, et al. Skyline queries against mobile lightweight devices in manets［C］//Proc of ICDE. 2006:66.

［7］WANG S, OOI B C, TUNG A K H, et al. Efficient skyline query processing on peer-to-peer networks［C］//Proc of ICDE. 2007: 1126-1135.

［8］TAO Y F, XIAO X, PEI J. Subsky: efficient computation of skylines in subspaces［C］//Proc of ICDE. 2006:65.

［9］YUAN Y, LIN X, LIU Q, et al. Efficient computation of the skyline cube［C］//Proc of VLDB. 2005: 241- 252.[ZK）]

［10］[ZK（#]PEI J, JIN W, ESTER M, et al. Catching the best views of skyline: a semantic approach based on decisive subspaces［C］//Proc of VLDB.2005: 253- 564.

［11］TAO Y, PAPADIAS D. Maintaining sliding window skylines streams［J］.IEEE Trans on KDE, 2006, 18( 2) : 377- 391.

［12］朱琳,关佶红,周水庚.Skyline计算研究综述 ［J］.计算机工程与应用, 2008,44(6):160-165.

［13］邓波,贾焰,杨树强 .一种高效的分布式Skyline查询算法［J］. 计算机工程与科学, 2007,29(9):97-100.