论文部分内容阅读
深受信息时代发展影响的今天,对海量数据的处理已经深入到商业、科技、金融、教育等各行业的发展中。消息预测、电子商务、金融统计等新型信息产业在拥有大量用户数据信息的同时,也同样面临着海量信息的冗杂。从大量混杂的数据当中提取有效的关键信息,变得十分的必要。Skyline查询能够返回用户更感兴趣的信息,是大数据领域信息处理的一种关键技术,被广泛地应用到如好友关系的预测(社交网络大数据),高速公路车辆查询(交通大数据),商品推荐(电商大数据)等诸多领域。随着数据量的剧增,由于skyline查询对信息的选择没有控制性,受数据量和数据分布情况的影响,返回的结果量有可能随之增加。K-支配skyline查询的提出弥补了上述缺陷,它通过控制参数k来控制对属性的选择,从而达到控制结果集大小的目的。然而,由于参数k的可变性,传统的k-支配skyline查询算法一般只能够按照用户在某一方面的要求来进行选择,依赖用户程度较大且可变性不大。同时,在诸多实际应用中经常会出现缺失属性值的现象,当存在获取的信息的属性值缺失时,对不完整信息需要经过特殊的处理方式,才能够使得不完整的信息实现推荐。另外,面对巨增的数据量,与传统的集中式运行环境相比,分布式并行计算框架MapReduce的提出很好地解决了这一问题。通过不断地研究,改进的k-支配skyline查询算法能够适应并行的计算框架,使得处理效率有了明显的提升。针对上述问题,本文研究在MapReduce环境下基于支配层次树的k-支配skyline查询方法,以及在MapReduce环境下不完整数据上的k-支配skyline查询方法。本文的主要内容总结如下:(1)本文提出一种支配层次树DBH-Tree(Dominant based Hierarchical Tree)索引结构,以数据对象占优势的维度的数量为根,构建树形索引结构,将数据划分到不同的叶子节点子空间,在子节点上进行查询,提高查询效率。(2)本文提出MapReduce环境下的k-支配skyline查询算法MR-DBHA(MapReduce-Dominant based Hierarchical Algorithm)。根据所有可能存在的k值,Map函数将数据划分到子空间,在子空间上Reduce函数再进行支配关系的进一步计算,返回k-支配skyline查询结果。(3)本文提出不完整数据上的支配层次树索引结构ID-DBH-Tree(Incomplete data Dominantbased Hierarchical Tree)。应用“桶”策略,将不完整的数据对象按照缺失属性的维度划分到不同的“桶”中,在“桶”内部进行支配关系的计算,得到k-支配skyline结果。(4)本文提出MapReduce环境下不完整数据上的k-支配skyline查询算法MR-ID-DBHA(MapReduce-Incomplete data-Dominant based Hierarchical Algorithm)。首先对不完整数据进行预处理;其次,再通过Map函数将“桶”中的数据按照支配情况分配到子空间上,Reduce函数对数据按照键值key进行支配过程,返回k—支配skyline查询结果。