云环境下基于衰减因子网格的Skyline查询  

Skyline query based on damping-factor grid in cloud environments

作　　者：姜罕盛 肖迎元[1] 李玉坤[1] 王晓晔[1] 

机构地区：[1]天津理工大学天津市智能计算及软件新技术重点实验室,天津300384

出　　处：《华中科技大学学报（自然科学版）》2013年第S2期176-180,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61170174);天津市自然科学基金资助项目(11JCYBJC26700)

摘　　要：为了解决云环境下对于海量数据的Skyline查询,提出了在Map-Reduce框架下基于衰减因子网格Skyline查询(SQBDFG)算法,该算法通过衰减式的网格进行区域划分,利用网格间的统治关系进行快速过滤,达到减少传输开销的目的,并针对网格的衰减速度会影响实际查询性能进行进一步优化.首先提出网格的最大剪枝空间和最大剪枝效率两个概念,然后从理论上证明了采用衰减式网格在处理海量数据的Skyline查询时在这两方面具有明显的优势.最后通过Hadoop分布式集群上的大量实验,在Skyline查询时间和数据I/O开销两个方面进行对比,证明了提出的SQBDFG算法具有良好的有效性和实用性.To deal with the cloud environment Skyline query for massive data,Skyline query based damping-factor grid(SQBDFG)algorithm in Map-Reduce was proposed,in which the transmission cost can be reduced by the region division based damping-grid to accelerate the filter of domination relationship.Also,the optimization of the SQBDFG was further presented considering the rate of griddamping.In this paper,max pruning space and max pruning efficiency were put forward at first,and then the obvious superiority Skyline query for massive data using damping-grid was proved theoretically.At last,query time of Skyline and I/O cost were compared by a large number of experiments on Hadoop,and the effectiveness and efficiency of the proposed methods was demonstrated.

关 键 词：云环境 SKYLINE查询 MAP-REDUCE 衰减因子网格 HADOOP 分布式计算 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]