基于并行化的网络图压缩表示算法的研究

《基于并行化的网络图压缩表示算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、方臻交硕士学位论文基于并行化的网络图压缩表示算法的研究TheParallel-basedforWebGraphcompressionrepresentationAlgorithm作者：赵建齐导师：杨晓晖北京交通大学2014年3月学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适

2、用本授权说明)学位论文作者签名：撅串前签字日期：矽什年，月渺日导师签名：刀缈吗签字日期：矽哆年：》月谚日中图分类号：TP301．6UDC：004．8学校代码：]0004密级：公开北京交通大学硕士学位论文基于并行化的网络图压缩表示算法的研究TheParallel．basedforWebGraphcompressionrepresentationAlgorithm作者姓名：赵建齐导师姓名：杨晓晖学位类别：工学学科专业：计算机科学与技术学号：11120512职称：副教授学位级别：硕士研究方向：信息检索北京交通大学2014年3月致谢本论文

3、的工作是在我的导师杨晓晖副教授的悉心指导下完成的，杨晓晖副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来杨晓晖老师对我的关心和指导。杨晓晖副教授悉心指导我完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和帮助，在此向杨晓晖老师表示衷心的谢意。同时要感谢瞿有利副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢。在实验室工作及撰写论文期间，刘小华等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激之情。另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我

4、的学业。j匕塞交通太堂亟±堂僮论塞撞要摘要网络图是指由网页及网页之间的链接关系组成的图，通过研究网页间的链接关系，抽取有用的信息，多用于爬虫算法，搜索和社区发现等方面。但在应用网络图时，最主要的问题是网络图的大小，如果网络图记录了整个网络，将包含几百亿的网页，如此巨大的网络图在当前存储现状下，不可能全部放入内存进行处理。本文主要研究大规模网络图的压缩表示方法，在k2-tree算法的基础上应用基于分层的方法，改善了矩阵分割的局限性，同时针对分层算法，实现了基于MapReduce模型的并行化改造。首先，对已有的网络图压缩表示算法及网络

5、图自身的统计特性进行了详细的阐述。针对k2-tree网络图压缩表示算法，分析了矩阵分割对于空间占用和查询时间的影响，同时结合网络图本身的分布规律，验证了基于分层的方法有效性，分层方法改善了上层结构和底层节点分割时过于单一的情况，使算法在压缩率和查询效率方面获得了更好的平衡，在保证空间占用的情况下，获得了更好的查询速度。其次，在应用分层算法的基础上，针对网页数量过于庞大的情况，本文实现了基于MapReduce编程模型对Layer-Based-k2．tree压缩表示算法的并行化改造。面对大规模的网络图数据，并行算法依然可以在可行的时问

6、内进行压缩表示的构造，提高了算法的运行效率。最后，通过在不同公开数据集上的实验对比，验证了基于分层方法的有效性。实验数据表明，在保证一定压缩率的前提下，基于分层的方法获得了更快的查询速度；在不同分层区间下，变化曲线呈现一定规律性，使算法在空间和时间上获得了更好的平衡。于此同时，针对不同数据集，进行了在多核计算机上的并行构造实验，验证了并行算法的可行性，对比串行计算过程，获得了最高9．7的加速比。关键词：网络图：压缩算法：MapReduce；并行计算分类号：TP301．6j匕复童通太堂亟±堂僮途塞△旦墨!B△￡!ABSTRACTWe

7、bgraphrepresentationisakindofgraphwhichconsistsofalltheWebpageswiththehyperlinksbetweenthem．RcallbeusedtoextractrelevantinformationfromthestudyofthoselinksbetweenWebpagesandcommonlyusedasthebasisforcrawlingalgorithm，searchingandcommunitydiscovery．Butthemainproblemofso

8、lvingsomeproblemsusingWebgraphrepresentationisthesizeofthegraphs．AstheyrepresentthewholeWeb，whichcontainsbillionsofWebpages，