基于并行图计算框架的大规模图最大流加速算法研究

发布时间：2024-05-12 03:49

　　最大流问题是图论中一个重要的基础性问题,其求解算法在科学和工程领域以及现实生活中都有广泛的应用,城市交通相关的车流量控制、城市排水管道的最大排水量计算、网络规划、路径规划等重要问题都可以抽象为最大流问题;最大流问题也是计算机视觉、大数据以及图像处理等技术的理论基础。上述技术目前仍在快速发展和更新,因此对最大流问题的深入研究有助于促进相关领域的发展,具有重要的理论意义和实际意义。学术界已提出多种用来解决最大流问题的新算法和新思路,逐步建立了单机求解最大流问题的较为完善的理论体系。虽然现有算法从多个角度求解最大流问题,但在应用到海量图数据处理时仍存在计算结果不准确和求解效率较低等问题。针对这些问题,本文主要研究基于GraphChi框架的大规模图最大流加速,并在该并行图计算框架中尝试解决图分割计算复杂度较高,多次计算存在大量冗余工作等关键问题。本文主要内容如下:(1)研究面向最大流计算的图数据划分和覆盖图构建方法,利用割点构建覆盖图并把原图拆分成多个子图,将割点映射到覆盖图并把其余顶点放入不同的子图。在美国路网等经典数据集上的测试结果表明,该算法将顶点数量缩减到了原图的0.97%^6...

【文章页数】：62 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第一章 绪论
    1.1 研究背景及意义
    1.2 研究现状
    1.3 主要创新点
    1.4 章节安排
第二章 最大流问题的相关理论和算法
    2.1 最大流问题模型
        2.1.1 图的定义及相关概念
        2.1.2 最大流理论模型
        2.1.3 BDT理论模型
        2.1.4 基于BDT的查询优化
    2.2 增广路径算法
    2.3 预流推进算法
    2.4 本章小结
第三章 覆盖图构建算法
    3.1 图数据划分方法
    3.2 覆盖图构建算法
        3.2.1 算法思想
        3.2.2 算法步骤
    3.3 实例分析
    3.4 实验结果与分析
    3.5 本章小结
第四章 最大流并行加速算法
    4.1 最大流问题回顾及限制条件
    4.2 查找路径算法
    4.3 并行计算最大流
    4.4 实验结果与分析
    4.5 本章小结
第五章 基于Graph Chi框架加速计算
    5.1 Graph Chi框架简介
    5.2 并行滑动窗口机制
        5.2.1 磁盘加载机制
        5.2.2 并行更新机制
        5.2.3 数据持久化机制
    5.3 基于框架的多子图计算
    5.4 实验结果与分析
        5.4.1 基于框架加速构建覆盖图实验
        5.4.2 基于框架并行计算多子图最大流实验
        5.4.3 本文算法与经典算法的对比实验
    5.5 本章小结
第六章 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢
个人简历、攻读硕士学位期间取得的学术成果



本文编号：3970816