云计算环境下的并行Skyline算法及其应用研究

发布时间：2019-09-26 11:52

【摘要】：随着互联网飞速发展,数据呈爆炸式增长,海量数据的处理需求越来越大。然而,由于数据量过大,使得海量数据处理对软硬件要求高、系统资源占用多,因此海量数据的处理技术面临着巨大挑战。目前,以MapReduce为代表的云计算技术越来越受到学术界和商业界的关注,并且在海量数据处理上得到了普遍的应用和推广。Skylin e算法作为一种有效的海量数据处理算法,可以帮助人们从数据中提取最感兴趣或最关心的信息,有效地剪枝掉无用数据,避免数据分析时的干扰。本文以云计算技术为依托,研究海量数据的Skyline算法,重点研究海量数据的静态Skyline算法、动态Skyline算法和图像数据的度量空间Skyline算法,以及这些算法在MapReduce架构下的优化和应用问题。论文完成的主要研究工作如下：针对海量数据静态Skyline查询时通信开销大及其计算量大的问题,本文提出了高效的基于用户喜好的子空间Skyline算法。针对海量数据计算量和通信开销问题,该算法利用了基于网格的剪枝策略来减少参与运算的数据点。针对海量数据Skyline计算返回用户终端的结果集庞大、不利于用户决策,并且用户终端的存储及网络通信资源有限的问题,该算法采用基于用户需求的SQM-filtering和ε-filtering过滤方法来返回Skyline结果的子集。最后利用MapReduce实现了基于用户喜好的子空间Skyline算法,并在不同分布的数据集上进行实验分析,实验结果表明这些方法有效提高了子空间Skyline算法在处理海量数据时的效率。针对海量数据动态Skyline查询时,一方面被查询对象的属性值随着查询对象的变化而变化,另一方面云计算环境的分布式存储、并行处理情况复杂,因此动态Skyline算法处理海量数据时存在计算开销大、实时性差等问题。针对这些问题,本文提出了一种基于MapReduce的动态Skyline算法,它利用基于网格的粗粒度全局Skyline格来实现快速查询,通过全局Skyline格计算获得候选结果集。这样有效地剪枝掉一些非结果点,节省了大量的计算开销,提高了动态Skyline算法处理海量数据的运行效率。最后为了验证该算法的效率和实用性,我们将该方法应用到网络监控流数据的异常情况检测中。在图像大数据的度量空间Skyline查询中,针对基于语义度量空间选择带来的计算复杂度高等问题,本文提出了一种基于图像多特征融合的度量空间Skyline算法,其核心是采用多特征融合图像检索方法(SKFF)。它在度量空间上采用图像的底层特征来描述图像,基于词袋模型生成相似度向量,并将Skyline操作应用到新的度量空间中进行图像检索。其特点是不需要针对不同图像库为每个特征设置权值,采用这种方法得到的结果不仅与查询图像在多个特征上都比较相似,而且还可以返回在某一特征上与查询图像相似的候选图像。该算法克服了传统多特征融合方法参数多、自适应性差的问题。同时,利用MapReduce能提高算法的效率和可扩展性。最后通过一系列实验验证了该算法的有效性和可扩展性。
【图文】：

ＭａｐＲｅｄｕｃｅ［７ｌ它大量普通机器代替了集群中的高性能服务器，已被证明具有易逡逑部署、高容错性及可扩展性等特点近些年来Ｈａｄｏｏｐ得到了广泛应用，成为海逡逑量数据并行处理的代表技术之一。逡逑正如思科公司所预测，２０１６年全球将有７９％的数据中屯、托管着云计算平台。逡逑海量数据存储在这些云计算平台中，由于数据量过大，使得这些海量数据处理技逡逑术对软硬件要求非常高、系统资源占用非常多，带来了算法效率低下的问题。海逡逑量数据处理是一个热点的研究方向，众多学者们依托云计算平台提出很多新的高逡逑效的海量数据处理算法，Ｓｋｙｌｉｎｅ算法是其中的一种高效的数据查询和提取方法，逡逑可レッ快速地从海量数据中抽取出关键的信息，大大减少数据量，降低海量数据处逡逑理中对软硬件的要求，提高数据处理的效率。逡逑Ｓｋｙｌｉｎｅ算法Ｍ是从一个给定数据集中返回不被其他任何数据对象支配的数据逡逑对象集合的过程，查询的结果是数据集中一部分特殊的数据对象，即数据集的边逡逑界点，其主要目标是提取数据集的边界点作为候选集提供给用户进行决策。逡逑遗逡逑

体系结构图,体系结构,主服务器,节点

图２．２邋ＨＤＦＳ体系结构逡逑Ｆｉｇ．邋２．２邋ＨＤＦＳ邋ａｒｃｈｉｔｅｃｔｕｒｅ逡逑如图２．２所示，ＨＤＦＳ是一个主从式体系结j9ｗ，它是邸Ｓ的开源实现。ＨＤＦＳ逡逑集群系统由Ｈ部分组成，，分别是一个主服务器节点（命名节点）、多个从节点（数据逡逑节点）和客户端姐成。主服务器节点管理文件系统的命名空间和控制客户端对文件逡逑－１５－逡逑
【学位授予单位】：大连海事大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP311.13;TP391.41

【参考文献】