首页> 正文

分布式图计算中的图划分问题研究

2020-12-02阅读(999)

分布式图计算中的图划分问题研究

论文摘要

自20世纪90年代开始,以因特网为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代,使得人类在任何地点任何时间都能够互联互通。从城市网络到全球航空网络,从大脑神经网络到各种新陈代谢网络,各种复杂网络已经充斥着人们生活的方方面面,包括经济,政治,科学等。复杂网络的研究能够广泛地应用到生物、计算机等各个学科领域,使人们更好的了解现实世界中的复杂系统。而如今,网络规模十分巨大,如果把大脑中的神经元看作顶点,神经元之间互连的树突看作边,那么整个网络将包含890亿个顶点及100万亿条边。如何对这些大规模图数据进行有效率的挖掘计算,是研究复杂网络的首要任务。并行计算技术是现在最成熟、应用最广、最可行的计算加速技术之一。因此研究复杂网络计算的并行加速技术具有十分重要的意义。而如何在各计算单元间分配任务是并行计算性能好坏的关键。图划分技术就是解决这一问题的有效手段。图划分问题的研究是随着实际应用的需求不断驱动。随着云计算技术的快速发展,不管是公有云还是私有云,不可避免会出现集群的异构性;数据量的快速增长对图划分算法的划分质量,划分效率及可扩展性提出新的要求;以寻找最短路径等为代表的局部挖掘的图计算应用的广泛性,对之前图划分算法都将成为新的挑战,使得之前划分技术难以适用当今复杂多变的集群环境和应用需求。针对以上三个挑战,分别提出了不同的解决方法。本文的主要贡献如下:1、针对异构计算环境下的分布式集群,本文提出了一种异构感知的流式图划分算法（HaSGP）。该方法根据并行异构环境中硬件性能的不同特点,合理的分配任务,使之提升分布式图计算的效率。同时针对流式图划分,设计了一种基于邻边结构的动态缓存数据管理机制,该机制有效的管理划分过程中的缓存数据。相对于现有的基于邻点结构的流算法,划分效率明显提升。2、针对大规模图划分的问题,本文设计了一种基于层次亲和聚类的分布式大图划分算法（DisHAP）。具体创新点为:设计了基于Boruvka算法的层次亲和聚类,将其作为初始划分。以顶点相似度为距离度量,迭代合并距离较近的两顶点,并移去子图中邻点相似度和值最小的顶点以约束规模过大的子图。在没有后续优化的情况下,划分质量也接近于现有的某些大图划分方法;针对大规模子图之间的割边率优化问题,DisHAP使用降维的操作,将初始划分结果线性嵌入为一维顶点序列。通过分片优化割边的方式对顶点序列重排列,将原问题转化为多个复杂度较小的子问题以利于并行计算。3、设计了一种面向多子图查询感知的图划分算法（Muti-QS）。该算法根据查询的历史记录对图数据进行动态的划分,实验表明,Muti-QS能够达到最高76%的查询在本地化执行。而且查询感知划分速度很快,因为它只对少量查询区域进行操作而不是优化大量的顶点。同时也提出了一种具有局部和全局屏障的混合模型—子查询屏障。由于子查询屏障中的局部屏障产生的最小化开销,使局部屏障能够最大化的减少本地化查询的延迟。而子查询屏障中的全局屏障能够很好的执行动态的优化分割。为了进一步降低分区之间的通信量,Muti-QS使用一种分离器和组合器,通过非集合通信进行同步,降低并发网络通信开销的影响。

论文目录

  • 中文摘要
  • 英文摘要
  • 1 绪论
  •   1.1 研究背景
  •   1.2 研究现状
  •     1.2.1 复杂网络
  •     1.2.2 图划分技术
  •   1.3 存在的问题
  •   1.4 本文的主要工作
  •     1.4.1 研究思路
  •     1.4.2 研究内容
  •     1.4.3 主要贡献
  • 2 图划分相关理论与技术
  •   2.1 图划分基础理论
  •   2.2 经典图划分算法
  •     2.2.1 离线划分
  •     2.2.2 流式划分
  •     2.2.3 动态重划分
  •   2.3 分布式图计算平台
  •     2.3.1 Pregel
  •     2.3.2 Giraph
  •     2.3.3 GraphLab
  • 2'>    2.3.4 TUX2
  •   2.4 本章小结
  • 3 异构计算环境中图划分算法的研究
  •   3.1 引言
  •     3.1.1 研究背景
  •     3.1.2 研究意义
  •     3.1.3 挑战与贡献
  •   3.2 问题定义
  •   3.3 异构因素下的形式化建模
  •     3.3.1 流式图划分
  •     3.3.2 计算能力
  •     3.3.3 通信带宽
  •     3.3.4 共享资源竞争
  •   3.4 异构环境下的图划分算法
  •     3.4.1 异构感知的流式划分
  •     3.4.2 邻边结构
  •   3.5 实验评估
  •     3.5.1 评估指标
  •     3.5.2 计算能力异构
  •     3.5.3 网络通信异构
  •     3.5.4 共享资源竞争
  •     3.5.5 图计算性能
  •   3.6 本章小结
  • 4 基于层次亲和聚类的分布式大图划分算法
  •   4.1 引言
  •   4.2 相关工作
  •   4.3 问题定义
  •   4.4 算法整体研究框架
  •   4.5 基于层次亲和聚类的分布式大图划分过程
  •     4.5.1 初始划分
  •     4.5.2 互交换平衡优化
  •     4.5.3 单点不平衡迁移
  •     4.5.4 复杂度分析
  •   4.6 实验评价
  •     4.6.1 实验环境
  •     4.6.2 数据集
  •     4.6.3 初始划分
  •     4.6.4 收敛分析
  •     4.6.5 划分时间
  •   4.7 本章小结
  • 5 面向多子图查询系统的图划分算法
  •   5.1 引言
  •     5.1.1 研究背景
  •     5.1.2 研究挑战
  •     5.1.3 本章贡献
  •   5.2 研究动机
  •   5.3 问题描述
  •     5.3.1 符号及定义
  •     5.3.2 查询感知图划分问题
  •   5.4 Muti-QS概述
  •   5.5 查询感知图划分
  •     5.5.1 监控
  •     5.5.2 分析优化
  •     5.5.3 执行
  •   5.6 子查询屏障
  •   5.7 分离组合器
  •   5.8 实验评估
  •     5.8.1 参数设置
  •     5.8.2 自适应图划分
  •     5.8.3 子查询屏障
  •     5.8.4 可扩展性
  •   5.9 本章小结
  • 6 结论与展望
  •   6.1 结论
  •   6.2 展望
  • 参考文献
  • 附录
  •   A 作者在攻读学位期间发表的论文目录
  •   B 作者在攻读学位期间参加的科研项目
  •   C 学位论文数据集
  • 致谢

    • 文章来源

    类型: 博士论文

    作者: 李琪

    导师: 钟将

    关键词: 图划分,并行图计算,复杂网络,负载均衡

    来源: 重庆大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 重庆大学

    分类号: O157.5

    总页数: 118

    文件大小: 14905K

    下载量: 81

    相关论文文献

    • [1].基于云聚合理论的城市社区划分算法研究[J]. 计算机应用研究 2017(01)
    • [2].面向分布式图计算的平衡图划分算法[J]. 信息与电脑(理论版) 2019(11)
    • [3].一种松弛的优化均衡流式图划分算法研究[J]. 计算机科学 2016(04)
    • [4].图划分算法综述[J]. 科技信息 2014(04)
    • [5].一种重叠可信社团划分算法的设计与实现[J]. 微计算机信息 2011(09)
    • [6].基于目标预测的扩展目标量测集划分算法[J]. 计算机工程与应用 2020(08)
    • [7].考虑通信成本和硬件碎片利用的簇划分算法[J]. 计算机辅助设计与图形学学报 2015(04)
    • [8].大规模图数据划分算法综述[J]. 电信科学 2014(07)
    • [9].一种基于点割的电路划分算法[J]. 计算机学报 2014(07)
    • [10].有向网络重叠社区的快速划分算法[J]. 计算机科学 2014(S1)
    • [11].三种经典复杂网络社区结构划分算法研究[J]. 电脑与信息技术 2011(04)
    • [12].一种基于聚集系数的局部社团划分算法[J]. 计算机科学 2010(07)
    • [13].基于主题与连接的局部社区划分算法[J]. 数据采集与处理 2016(03)
    • [14].一种考虑执行延迟最小化和资源约束的改进层划分算法[J]. 电子学报 2012(05)
    • [15].基于任务划分算法的基准程序研究[J]. 科技传播 2011(03)
    • [16].VLSI电路划分算法综述[J]. 福州大学学报(自然科学版) 2011(05)
    • [17].一种嵌入式系统软硬件划分算法[J]. 计算机仿真 2011(10)
    • [18].基于逻辑段划分算法统计的文本信息检索[J]. 电脑知识与技术 2009(32)
    • [19].一种动态网络社区划分算法[J]. 北京工业大学学报 2011(02)
    • [20].基于表集合划分算法的数据交换方法研究[J]. 计算机工程与设计 2013(06)
    • [21].基于适应度的簇划分算法研究[J]. 计算机仿真 2008(02)
    • [22].流级别的高速网络流量动态划分算法[J]. 小型微型计算机系统 2013(05)
    • [23].多级划分算法的后处理与评价方法[J]. 小型微型计算机系统 2010(01)
    • [24].基于无偏Q值反馈的社区划分算法[J]. 东南大学学报(自然科学版) 2011(01)
    • [25].自由曲面四边形网格等杆长划分算法[J]. 空间结构 2016(01)
    • [26].改进的基于局部模块度的社团划分算法[J]. 计算机应用 2016(05)
    • [27].基于模糊聚类的社团划分算法[J]. 计算机工程 2016(08)
    • [28].基于子团规模的社团划分算法与地理位置[J]. 东北大学学报(自然科学版) 2012(11)
    • [29].一种基于聚集系数的复杂网络社团划分算法[J]. 网络安全技术与应用 2012(09)
    • [30].一种新的基于晶体管级的电路划分算法[J]. 电子与信息学报 2009(12)

    标签：;  ;  ;  ;  

    分布式图计算中的图划分问题研究
    下载Doc文档

    猜你喜欢

    © 2024 毕论降 版权所有 鄂ICP备12018319号-6