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

Skyline query based on damping-factor grid in cloud environments

为了解决云环境下对于海量数据的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.