高效大规模静态图划分算法的研究与应用
发布时间：2021-07-06 13:27
社交网络、网页链接、城市道路交通网和大规模集成电路等均可抽象为顶点和边的数量在千万级以上的大规模图（数据）,对这类大规模图的高效分析与计算需要在分布式平台上进行。然而,大规模图均衡划分是分布式处理图数据的核心问题,优良的大规模图划分结果可以充分利用集群资源、提升数据处理效率。已有许多研究者以线性规划、多级划分、启发式等方法对大规模图划分问题进行了研究,并提出了许多求解算法。但已有算法存在划分效率低、未充分考虑图结构、划分结果质量差等问题。因此,对大规模图划分算法进行研究与创新,使其能够提升大规模图数据处理任务的计算效率,在大数据分析领域具有极大的理论意义和应用价值。论文选题来源于国家自然科学基金项目,作者针对已有算法缺陷,结合标签传播机制、多目标优化和对大规模图内部结构的研究创新提出了两种新的大规模图划分算法,同时,用所提出的算法优化了Giraph图处理框架中的图划分处理组件,使其图处理框架的性能得到了较大的提升。本文主要工作内容及创新如下:（1）针对传统大规模图划分算法划分效率低、划分质量差且未充分利用分布式平台的问题,本文基于轻量级的标签传播机制,创新提出了一种新的高效平衡大规模图...
【文章来源】：西安电子科技大学陕西省 211工程院校 教育部直属院校
【文章页数】：84 页
【学位级别】：硕士
【部分图文】：
常见大规模图数据
析及数据挖掘任务已经不可能，需要利用分布式平台进行处理。文献模图处理框架进行了对比分析研究。下面本文对流行的、具有代表性的处理框架进行总结与分析。2.1 PowerGraph图数据处理框架werGraph[29]是嵌入在 GraphLab[30,31]中的底层图处理框架。目前专门针据处理的框架 Pregel[32]不适合处理自然图数据，问题在于高度顶点和分很差。设计 PowerGraph 时就是为了应对上述两个问题，其中 Power 是布[22]的图数据。PowerGraph主要贡献有两点：第一，提出了GAS(Gather)计算模型[33]，将高维度点并行化；第二，采用顶点切分，均衡集群负载 还有一些其它特性，包括 3 种执行模式（全局同步，全局异步，可串行化量 Cache 特性，具体特点可以参看论文[29]。个 PowerGraph 架构如图 2.1 所示。最上层是 PowerGraph 系统，它和 G一起，采用 C++实现，利用 HDFS 进行数据输入和输出，利用检查点实现
图2.2 GraphX 整体结构图raphX 的图数据存储模式与划分策略。GraphX 中图数据的分布式存储模，边会被分配到每个 EdgePartition，顶点 Master会被分配到每个VertexPartition 会拥有本地边关联的顶点的 Ghost 副本。Ghost 副本数量和边分都会受到划分方法的影响，因此划分策略的选取是非常的关键，最好是结构来进行选取。GraphX已有RandomVertexCut、Canonical- RandomVeartition1d、EdgePartition2d 四种划分策略。于 GraphX 是基于 Spark 平台并对其进行扩展，所以 GraphX 天然具有可扩展性和执行效率，并且 GraphX 的 Graph 和 Table 两种视图共享底可以降低计算和存储的开销。但是 GraphX 上的消息计算会同时访问源点，所以其上的消息计算开销较大，从而会影响图数据计算效率。2.3 Giraph图数据处理框架iraph[37]是一个迭代式的图计算系统。雅虎开发了 Giraph，在开发时采取的 Pregel 模型[32]，Pregel 模型超步迭代的示例如图 2.3 (a)所示。后来，
【参考文献】：
期刊论文
[1]改进的点到三角网距离快捷算法[J]. 吴耕宇,潘懋,郭艳军,李兆亮. 计算机辅助设计与图形学学报. 2014(03)
[2]BHP:面向BSP模型的负载均衡Hash图数据划分[J]. 周爽,鲍玉斌,王志刚,冷芳玲,于戈,邓超,郭磊涛. 计算机科学与探索. 2014(01)
本文编号：3268329
【文章来源】：西安电子科技大学陕西省 211工程院校 教育部直属院校
【文章页数】：84 页
【学位级别】：硕士
【部分图文】：
常见大规模图数据
析及数据挖掘任务已经不可能，需要利用分布式平台进行处理。文献模图处理框架进行了对比分析研究。下面本文对流行的、具有代表性的处理框架进行总结与分析。2.1 PowerGraph图数据处理框架werGraph[29]是嵌入在 GraphLab[30,31]中的底层图处理框架。目前专门针据处理的框架 Pregel[32]不适合处理自然图数据，问题在于高度顶点和分很差。设计 PowerGraph 时就是为了应对上述两个问题，其中 Power 是布[22]的图数据。PowerGraph主要贡献有两点：第一，提出了GAS(Gather)计算模型[33]，将高维度点并行化；第二，采用顶点切分，均衡集群负载 还有一些其它特性，包括 3 种执行模式（全局同步，全局异步，可串行化量 Cache 特性，具体特点可以参看论文[29]。个 PowerGraph 架构如图 2.1 所示。最上层是 PowerGraph 系统，它和 G一起，采用 C++实现，利用 HDFS 进行数据输入和输出，利用检查点实现
图2.2 GraphX 整体结构图raphX 的图数据存储模式与划分策略。GraphX 中图数据的分布式存储模，边会被分配到每个 EdgePartition，顶点 Master会被分配到每个VertexPartition 会拥有本地边关联的顶点的 Ghost 副本。Ghost 副本数量和边分都会受到划分方法的影响，因此划分策略的选取是非常的关键，最好是结构来进行选取。GraphX已有RandomVertexCut、Canonical- RandomVeartition1d、EdgePartition2d 四种划分策略。于 GraphX 是基于 Spark 平台并对其进行扩展，所以 GraphX 天然具有可扩展性和执行效率，并且 GraphX 的 Graph 和 Table 两种视图共享底可以降低计算和存储的开销。但是 GraphX 上的消息计算会同时访问源点，所以其上的消息计算开销较大，从而会影响图数据计算效率。2.3 Giraph图数据处理框架iraph[37]是一个迭代式的图计算系统。雅虎开发了 Giraph，在开发时采取的 Pregel 模型[32]，Pregel 模型超步迭代的示例如图 2.3 (a)所示。后来，
【参考文献】：
期刊论文
[1]改进的点到三角网距离快捷算法[J]. 吴耕宇,潘懋,郭艳军,李兆亮. 计算机辅助设计与图形学学报. 2014(03)
[2]BHP:面向BSP模型的负载均衡Hash图数据划分[J]. 周爽,鲍玉斌,王志刚,冷芳玲,于戈,邓超,郭磊涛. 计算机科学与探索. 2014(01)
本文编号：3268329
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3268329.html
