MapReduce框架下Skyline查询算法研究与改进

来源 :合肥工业大学 | 被引量 : 0次 | 上传用户:xiaofch22
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着大数据时代的到来,数据规模和种类急剧增大,如何在海量数据中找出对用户有用的信息至关重要。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结果集规模,具有良好的时间和空间性能。
其他文献
作为一种关注域间流量级别上的网络性能优化技术,域间流量工程越来越受到ISP的重视。BGP协议是目前唯一广泛使用的域间路由协议,用来引导域间流量穿越自治域。因此BGP路由的
人脸识别是一种重要的生物特征识别技术,在公共安全、信息安全、金融等领域具有广阔的应用前景。近二十年来,人脸识别取得了很大进展,也涌现出了一些有效的人脸识别算法。其中,基
随着计算机技术的发展,互联网越来越深入人们的日常生活。但是在它给人们带来便利的同时,网络安全问题也随之而来。木马便是其中一种威胁越来越大的基于互联网的恶意软件。为
显著性检测是图像处理与计算机视觉领域的重要研究内容之一。本文将人眼对RGB三原色的敏感度差异引入显著性检测方法中,探讨改进的基于RGB视觉敏感度的显著性检测方法。本文
社区问答系统目前已成为一项新兴的Web 2.0服务。不同于传统的自动问答系统,人们在这类系统中提出自己的问题后,其他的用户可以根据自身经验来回答相应的问题。在经过一段时
随着互联网和数字多媒体技术的发展,数字作品的制作、传输、存储越来越方便。然而,技术的发展在给人们带来便利的同时也带来了许多安全问题,包括音像制品的非法传播、拷贝、
本文的研究背景是某飞机显控系统对嵌入式数据库的应用需求预研项目。为提高事务管理器事务调度的成功率及软件的构架性能,对事务管理器的混合事务调度、并发控制及软件构架
虚拟漫游技术是虚拟现实技术的重要分支,在建筑、医学、航天等领域应用广泛。本文以地产开发项目为背景,提出了一个桌面级漫游应用的设计思路和解决方案,重点对虚拟场景建模和漫
学位
脉冲现象是自然科学乃至社会科学领域中一种普遍而重要的现象,并通常用脉冲微分方程进行刻画。对实际问题,我们还希望用相对快速的外加手段或脉冲扰动来修正系统以达到预期目的
网络计费系统对于运营商与用户来说都是一个极其重要的系统,不仅可以统计网络用户的费用,而且可以监控网络数据流量,优化网络资源分配。先进的计费系统是提供优质网络服务的