论文部分内容阅读
随着大数据时代的到来,数据规模和种类急剧增大,如何在海量数据中找出对用户有用的信息至关重要。Skyline查询作为经典的查询算法,能够有效返回原始数据集上的一组较优子集,将Skyline算法应用到MapReduce并行计算框架,成为处理大数据环境下Skyline查询的有效方法。高维度、大数据集上Skyline查询算法的时空开销大,因此如何提高大数据下的Skyline算法效率成为一个研究热点。由于Skyline结果集规模随维度呈指数级增长,大数据环境下Skyline结果集规模巨大从而无法为用户返回精准的信息,如何选取规模更小、更具有代表性的查询结果值得进一步研究。 针对大数据环境下Skyline查询效率低问题,提出了一种基于MapReduce框架的广义支配优化Skyline查询算法。该算法定义了全空间广义支配的概念,验证了广义支配的快速性和高效性,利用广义支配过滤原始数据集中的非Skyline点从而为Skyline查询提供削减的数据集。通过优化数据点支配能力的计算方法,利用MapReduce复合键值对削减后的数据集按照支配能力大小排序,以加快非Skyline点的过滤。实验结果表明,该算法可以有效加快非Skyline点的过滤,提高Skyline查询算法的时间性能。 针对大数据环境下Skyline结果集规模巨大问题,为了对Skyline结果集进行优选、得到更具有代表性的Skyline结果,提出了MapReduce框架下基于支配个数的Skyline结果集优化算法。该算法提出了数据点支配个数的计算方法,即在进行数据点支配比较的同时,动态地计算数据点的支配个数,从而为用户返回k个支配个数最高的Skyline点代表Skyline结果集。实验结果表明,该算法可以有效地控制Skyline结果集规模,具有良好的时间和空间性能。