基于生成子图的超图划分算法研究

论文摘要

最大限度地降低多主机间的查询成本对于大数据应用的数据处理具有重要意义。超图通过将多路径关系或交互表示为网络,擅长对复杂网络(典型的大数据应用)的数据和数据关系进行建模。超图分区有助于划分多个主机上的查询负载,从而实现大规模网络的水平扩展。在可用的处理单元之间找到一个良好的通信任务划分,对于缩短执行时间、减少能耗、更好地利用计算和通信资源至关重要。因此本文基于生成子图理论改进了现有的切割网络的超图划分算法,能够更高效并行处理拥有庞大数量用户的在线信息通信任务。现有的启发式超图划分算法一般分为两种——顶点划分和超边(网络)划分,其目的是在满足分区权重对顶点的平衡要求的同时,最小化切割网络的数目。但是,由于工作负载主要是由组操作(网络)产生的,那么在水平扩展中,要降低整个通信网络中查询总成本并平衡工作负载,考虑网络划分的方式更为合理。因此,我们提出了一个启发式的网络的超图划分算法。具体地说:首先,确定每个分区包含的平均超边数量;然后,根据逆向思维将超边看成节点,运用最小生成子图的搜索算法,寻找最少的节点能够包含平均数量的超边;接着,将原超图划分为每个分区都包含平均数量的超边;再基于经典的超边划分算法HEPart中的超边移动增益定义对当前分区进行优化;最后,得到满足网络权重平衡约束的超图划分。在两个由无向超图建模的复杂网络数据集中,对所提出算法在不同的割集尺度下的性能进行了评估。并与现有的超边划分算法HEPart的划分质量与性能进行比较。实验结果证明了本文算法的计算成本更小和划分质量更优。

论文目录

摘要

Abstract

1 绪论

1.1 本课题研究背景和意义

1.2 国内外研究现状

1.3 本文研究内容

2 相关知识介绍

2.1 引言

2.2 超图的定义

2.3 超图的相关参数

2.3.1 顶点的度

2.3.2 顶点的超度

2.3.3 集聚系数

2.4 超图划分的定义

2.4.1 超图划分的两种度量标准

2.4.2 超图划分的优化问题描述

2.5 超图的最小生成子图定义

2.6 HEPart超图划分算法

2.6.1 HEPart算法定义

2.6.2 HEPart算法步骤

2.6.3 HEPart算法优劣点与可改进方向

2.7 本章小结

3 最小生成子图搜索算法

3.1 引言

3.2 优化问题描述

3.3 逐步增加网络

3.4 逐步删除网络

3.5 算法3.2与算法3.3性能对比

3.5.1 两种超图结构的区别

3.5.2 超图结构对两种算法的影响

3.5.3 迭代次数对算法的影响

3.5.4 网络数量对算法的影响

3.6 本章小结

4 基于生成子图的超图划分算法

4.1 引言

4.2 HEPart算法的细节

4.2.1 算法中出现的符号含义

4.2.2 初始增益计算

4.3 最小生成子图划分算法

4.4 基于生成子图的超图划分算法

4.5 本章小结

5 算法实验结果分析与对比

5.1 引言

5.2 实验环境

5.3 算法评估指标

5.4 算法4.3的性能

5.4.1 两种度量对切割顶点数量的影响

5.4.2 两种度量对复制顶点数量的影响

5.4.3 两种度量对分区标准差NSTDEV的影响

5.5 算法4.3与HEPart算法的比较

5.6 算法4.3的性能

5.7 本章小结

结论

参考文献

致谢

文章来源

类型: 硕士论文

作者: 王译晗

导师: 刘洪波,汲业

关键词: 超图划分,网络划分,生成子图,大数据,无标度网络

来源: 大连海事大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 大连海事大学

分类号: O157.5

DOI: 10.26989/d.cnki.gdlhu.2019.001813

总页数: 53

文件大小: 4206K

下载量: 28

基于生成子图的超图划分算法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢