学位论文 > 优秀研究生学位论文题录展示

大规模图增量迭代处理技术的研究与实现

作　者: 王志刚
导　师: 于戈
学　校: 东北大学
专　业: 计算机软件与理论
关键词: 大规模图 增量迭代处理 数据划分 磁盘索引 网络通信
分类号: TP301.6
类　型: 硕士论文
年　份: 2013年
下　载: 8次
引　用: 0次
阅　读: 论文下载
 

内容摘要


社交网络、生物信息网络和信息技术的快速发展,使图论及其相关算法的应用日益广泛。其中,利用云计算环境开发大规模图的增量迭代处理平台,已经成为当前学术界和工业界研究的热点。但是针对数据划分、磁盘管理和网络通信等方面的优化工作,相对较少,而这三个方面正是影响大图处理平台运行效率的至关重要的因素。由于大图的增量迭代处理,具有数据耦合性强、迭代频率高、数据访问局部性差等特点,因此对于上述三个方面的优化处理是一个十分具有挑战性的课题,这也是本文的主要工作内容。在数据划分方面,本文首先分析了DFS生成图和BFS生成图的局部性,然后提出了连续划分策略。相比于现有的随机Hash划分,连续划分策略能够保留输入图的原始局部性,避免数据划分阶段的全局洗牌操作,均衡计算负载。同时,为提供迭代过程的消息路由寻址服务,本文提出了基于Hadoop的图顶点连续编码方案和基于DHT的Hybrid-MT连续编码方案,可以将图顶点字符串转换为数字连续编号。在磁盘管理方面,通过分析增量迭代过程,本文提出了图状态转换模型,并据此设计了基于列存储模型的静态Hash索引和基于Markov模型的动态可调Hash索引。前者可以提高消息数据与本地图数据之间连接操作的局部性,避免随机磁盘存取。后者在前者基础上,根据迭代状态的转换和Markov代价收益评估模型,可以动态调整Hash桶的分割粒度,最小化磁盘存取开销。在网络通信方面,通过扩展BSP模型(Bulk Synchronous Parallel),本文提出了基于EBSP模型的Hybrid迭代机制,即图数据同步处理,而消息数据跨步处理。特别的,消息跨步剪枝(ASMP)和跨步合并(ASMC)是两种跨步处理方法,可以分别剪枝消息规模和加速消息传播速度。此外,在连续划分基础上,本文提出了VCCP(Vertex-Cut based on the Continuous Partitioning)方法,利用BFS生成图的原始局部性,VCCP通过较低的预处理开销,能够显著改善总体运行效率。最后,本文设计了DiterGraph原型系统,通过大量实验验证了数据划分、磁盘管理和消息通信的性能。与现有系统对比,对于单源最短路径算法,DiterGraph的运行效率是Giraph的2倍,与Hadoop和Hama相比,最高可达21倍和43倍；对于PageRank算法,采用VCCP方法后,DiterGraph的运行效率最高可达Hadoop的20倍。

全文目录


摘要  5-6
Abstract  6-11
第1章 引言  11-17
  1.1 研究背景  11-13
    1.1.1 云计算与大数据  11
    1.1.2 大规模图的增量迭代计算  11-13
  1.2 研究意义  13-15
    1.2.1 大图增量迭代计算的特点与挑战  13-14
    1.2.2 国内外研究现状  14-15
  1.3 本文主要贡献及组织结构  15-17
    1.3.1 本文主要贡献  15-16
    1.3.2 本文组织结构  16-17
第2章 大图迭代计算的相关工作  17-23
  2.1 大图迭代计算的分布式框架  17-19
    2.1.1 基于MapReduce模型的计算框架  17-18
    2.1.2 基于BSP模型的计算框架  18-19
    2.1.3 其它分布式计算框架  19
  2.2 大图的分布式划分  19-20
    2.2.1 随机Hash划分算法  19-20
    2.2.2 启发式划分算法  20
  2.3 大图的磁盘存储与索引技术  20-21
  2.4 大图处理的消息优化方法  21-22
    2.4.1 同步迭代处理  21
    2.4.2 异步迭代处理  21
    2.4.3 基于Combine的消息优化方法  21-22
    2.4.4 基于切分的消息优化方法  22
  2.5 本章小结  22-23
第3章 分布式图划分与顶点连续编码技术  23-41
  3.1 大图的分布式划分  23-26
    3.1.1 大图的局部性分析  23-25
    3.1.2 连续划分方法  25-26
    3.1.3 连续划分方法分析  26
  3.2 图顶点连续编码技术  26-38
    3.2.1 基于Hadoop的连续编码方法  28-29
    3.2.2 基于DHT的Hybrid-MT连续编码技术  29-36
    3.2.3 顶点编号替换的代价分析  36-38
  3.3 实验结果与分析  38-40
    3.3.1 实验设置  38
    3.3.2 图划分性能评估  38-40
  3.4 本章小结  40-41
第4章 基于状态转换与Markov模型的磁盘索引技术  41-59
  4.1 大图的增量迭代特点分析  41-44
    4.1.1 经典算法分析  41-42
    4.1.2 增量迭代特征  42
    4.1.3 增量迭代的状态转换模型  42-44
  4.2 大图的磁盘存储管理技术  44-54
    4.2.1 基于列存储模型的静态Hash索引策略  45-48
    4.2.2 基于状态转换与Markov模型的动态Hash索引策略  48-54
  4.3 实验结果与分析  54-57
    4.3.1 实验设置  54
    4.3.2 索引性能评估  54-56
    4.3.3 数据处理能力与处理效率评估  56-57
  4.4 本章小结  57-59
第5章 增量迭代的消息优化技术  59-75
  5.1 基于EBSP模型的Hybrid迭代机制  59-65
    5.1.1 同步与异步迭代机制分析  59-60
    5.1.2 典型算法分析  60-61
    5.1.3 基于EBSP模型的Hybrid迭代机制  61-62
    5.1.4 消息优化示例分析  62-65
  5.2 基于连续划分的图顶点切分方法(VCCP)  65-69
    5.2.1 基于连续划分的VCCP方法  65-67
    5.2.2 顶点备份比例分析  67-69
  5.3 实验结果与分析  69-74
    5.3.1 实验设置  69
    5.3.2 基于EBSP模型的Hybrid方法性能测试  69-72
    5.3.3 基于连续划分的VCCP方法性能测试  72-74
  5.4 本章小结  74-75
第6章 DiterGraph原型系统  75-83
  6.1 系统简介  75-77
  6.2 系统部署及使用方法  77-81
    6.2.1 系统部署  77-78
    6.2.2 用户编程指导  78
    6.2.3 可视化管理工具  78-81
  6.3 本章小结  81-83
第7章 总结与展望  83-85
  7.1 本文的主要贡献与结论  83
  7.2 未来工作  83-85
参考文献  85-89
致谢  89-91
攻读硕士学位期间的论文项目情况  91

相似论文

  1. 多基地高频雷达固定站中央主机软件研制,TN957.5
  2. 基于自然计算的WSN路由技术研究,TN929.5
  3. 基于辅控多网络的电厂脱硫系统应用及实现,TP311.52
  4. 蚁群算法与A*算法在Ad-Hoc网络中的应用研究,TN929.5
  5. 脉搏信号远程自动监测器系统原型研究,TN911.23
  6. 云闪雷电探测网数据传输与远程监控的技术研究,TN919.3
  7. 基于Mini6410的USB虚拟存储,TP333
  8. 分布式交互仿真模拟技术的研究及其在深水海洋平台锚泊操作模拟中的应用,U674.381
  9. P2P匿名通信网络的安全分析与性能优化,TN915.08
  10. 地区电网故障信息系统的研究应用,TM734
  11. 煤矿井下PLC道岔网络控制系统,TP273
  12. 月球探测空间数据集成与检索技术研究,P184.5
  13. 可介入式励磁控制器的研究与设计,TM762
  14. 分布式网络设备的软件在线升级系统设计,TP311.52
  15. 网络通信中的软交换及软交换实验程序设计,TN915
  16. 铁路机务段综合信息化模型的研究,U269.2
  17. 酒钢生产指挥中心数字监控系统的设计与实现,TP277
  18. 用于路灯控制的无线通信网络平台设计,TP273
  19. 大规模图集的频繁子图挖掘算法研究,TP301.6
  20. 并行计算环境中矢量空间数据的划分策略研究与实现,P208
  21. D-TIN并行构建方法及其在地图综合中的应用研究,P283

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com