论文部分内容阅读
互联网和信息技术的快速发展推动了大众对数据的生产和消费,信息为数据披上了外衣,人们进入了一个网络密布、数据激增的时代。在这个信息化时代,Web网页呈现出几何数量级增长趋势。用户可以很便捷的发布和获取各种信息,但是也面临着如何从数以TB甚至PB量级的网页数据中快速精准地定位有用信息的问题。人们获取信息的途径,除了网页文本信息,还有网页间链接结构,从Web网络结构中我们可以挖掘出隐藏的潜在信息。传统单机模式下的Web网络结构挖掘PageRank算法,无论从空间存储还是计算效率上都已远不能满足我们的需求。云计算的出现很好地解决了这个问题。利用云计算技术,人们可以很方便的通过互通的网络环境搭建云平台,利用低配置的计算机集群获取强大的存储和计算能力。在详细研究Web结构挖掘的经典算法——Google的PageRank算法,云计算的关键技术MapReduce编程模型及其开源实现——Hadoop框架的基础上,针对PageRank算法数据处理过程中,网页结构关系规模过大造成的数据存储、网络传输和输入输出资源消耗过大的问题,在PageRank计算开始之前,本文通过网页链接结构本身的特性(一个网站内的网络节点分布比较集中,而不同网站之间的链接不是特别紧密)进行网站分割。实现Key压缩,从而降低Map函数加载驱动、初始化常量造成的资源消耗。对切割后的数据,采用Hash映射和LZO双重压缩技术减低传输过程中的时间开销。通过K步长算法,在并行迭代过程中尽量减少节点之间的通信,加快迭代收敛速度。搭建Hadoop平台,利用不同规模的数据集,对传统并行PageRank算法和改进的并行算法进行时间和空间开销上的评估。实验结果表明改进的并行算法在确保空间占用的基础上明显加快了 PageRank算法的执行速度。实现PageRank算法在微博平台中权威值计算中的应用,通过实验结果验证算法的有效性。