基于MapReduce的分布式极图构造算法研究

基于MapReduce的分布式极图构造算法研究

北京交通大学 赵男

随着云计算技术的快速发展,很多与大规模数据处理相关的研究与应用都逐渐迁移到云计算环境中,如数据挖掘、网络搜索、图像处理以及生物信息分析等。对大规模的图数据处理技术也是当前高性能计算领域的研究热点。而在图论研究中,极图构造算法作为极图理论的一个重要研究内容,越来越受到人们的关注。 极图是指满足一定约定条件且边数最多的图,其构造算法产生大规模的临界图集合作为中间数据。传统的串行极图构造算法会因为需要处理的临界图数量的大幅增加而变得效率低下。MapReduce模型是目前在研究云计算相关问题时常被使用的编程模型,Hadoop项目是对该模型的开源实现,利用这个平台可以大大简化分布式编程的难度。 本文提出了一种基于MapReduce的分布式极图构造算法。在对串行极图构造算法深入分析的基础上提出了并行的实施方案,然后在Hadoop分布式基础平台上实现了极图构造的分布式并行算法。其中,各个map任务处理那些已被划分成数据块的临界图输入数据,reduce任务负责归并所有map任务产生的中间临界图数据并得到最终的图集合。 本文还进行了一系列对比试验,以验证所设计的分布式极图构造算法的有效性和执行效率。实验结果表明,该算法能够构造出不超过28个顶点且不含六边形的极图集合。与串行算法相比,该算法的整体加速比和执行效率分别为2.2645和75.48%。特别是,在构造具有19个顶点的不含六边形且边数不少于35的临界图集合时,其加速比和执行效率分别达到了2.7423和91.41%。

基于MapReduce的分布式极图构造算法研究