基于GPU异构体系结构的大规模图数据挖掘关键技术研究
| 摘要 | 第10-12页 |
| Abstract | 第12-13页 |
| 第一章 绪论 | 第14-36页 |
| 1.1 研究背景 | 第14-24页 |
| 1.1.1 图数据挖掘的广泛应用 | 第14-16页 |
| 1.1.2 图数据挖掘领域的关键问题 | 第16-19页 |
| 1.1.3 大规模图挖掘面临的挑战 | 第19-20页 |
| 1.1.4 GPU异构计算平台带来的机遇和挑战 | 第20-24页 |
| 1.2 研究现状 | 第24-31页 |
| 1.2.1 广度优先搜索算法研究的相关工作 | 第24-26页 |
| 1.2.2 中介中心度计算算法研究的相关工作 | 第26-28页 |
| 1.2.3 子图同构算法研究的相关工作 | 第28-29页 |
| 1.2.4 频繁子图挖掘算法研究的相关工作 | 第29-31页 |
| 1.3 研究内容 | 第31-32页 |
| 1.4 主要工作及贡献 | 第32-34页 |
| 1.5 文章结构 | 第34-36页 |
| 第二章 基于GPU的并行广度优先搜索算法研究 | 第36-54页 |
| 2.1 广度优先搜索 | 第36-40页 |
| 2.1.1 广度优先搜索简介 | 第36-37页 |
| 2.1.2 并行广度优先搜索 | 第37页 |
| 2.1.3 典型基于GPU广度优先搜索算法 | 第37-40页 |
| 2.2 基于GPU的广度优先遍历算法 | 第40-49页 |
| 2.2.1 邻居收集 | 第41-44页 |
| 2.2.2 全局去重 | 第44-45页 |
| 2.2.3 自底向上遍历 | 第45-48页 |
| 2.2.4 多GPU算法 | 第48-49页 |
| 2.3 实验结果及讨论 | 第49-53页 |
| 2.3.1 实验设置 | 第49-50页 |
| 2.3.2 GPU自顶向下BFS算法性能评测 | 第50-52页 |
| 2.3.3 GPU混合BFS算法性能评测 | 第52-53页 |
| 2.4 本章小结 | 第53-54页 |
| 第三章 基于GPU的中介中心度计算算法研究 | 第54-74页 |
| 3.1 中介中心度计算问题 | 第54-58页 |
| 3.1.1 中介中心度计算定义 | 第54-55页 |
| 3.1.2 经典中介中心度计算算法 | 第55-56页 |
| 3.1.3 典型基于GPU的并行中介度计算算法 | 第56-58页 |
| 3.2 基于GPU的中介中心度计算算法 | 第58-67页 |
| 3.2.1 算法框架 | 第58-59页 |
| 3.2.2 基于前沿队列的方法 | 第59-62页 |
| 3.2.3 基于顶点并行的方法 | 第62-66页 |
| 3.2.4 混合方法 | 第66-67页 |
| 3.3 性能评测 | 第67-72页 |
| 3.3.1 实验设置 | 第67-68页 |
| 3.3.2 单GPU平台混合方法性能测试 | 第68-71页 |
| 3.3.3 多GPU平台混合方法性能测试 | 第71-72页 |
| 3.4 本章小结 | 第72-74页 |
| 第四章 基于GPU的大规模子图同构算法研究 | 第74-92页 |
| 4.1 子图同构问题 | 第74-77页 |
| 4.1.1 子图同构问题简介 | 第74-75页 |
| 4.1.2 部分子图映射 | 第75页 |
| 4.1.3 基于区域扩展的匹配顺序选择 | 第75-77页 |
| 4.2 基于区域遍历的GPU子图同构算法 | 第77-87页 |
| 4.2.1 算法框架 | 第77-78页 |
| 4.2.2 GPU区域遍历 | 第78-84页 |
| 4.2.3 GPU子图匹配 | 第84-86页 |
| 4.2.4 负载均衡 | 第86-87页 |
| 4.3 实验结果及讨论 | 第87-91页 |
| 4.3.1 实验设置 | 第87-88页 |
| 4.3.2 性能评测 | 第88-91页 |
| 4.3.3 扩展性测试 | 第91页 |
| 4.4 本章小节 | 第91-92页 |
| 第五章 基于GPU的频繁子图挖掘算法研究 | 第92-112页 |
| 5.1 频繁子图挖掘简介 | 第92-95页 |
| 5.1.1 频繁子图挖掘定义 | 第92-93页 |
| 5.1.2 gSpan算法 | 第93-94页 |
| 5.1.3 典型的基于GPU的g Span算法 | 第94-95页 |
| 5.2 基于GPU的频繁子图挖掘算法 | 第95-105页 |
| 5.2.1 算法框架 | 第95-97页 |
| 5.2.2 基于GPU的模式图扩展 | 第97-100页 |
| 5.2.3 基于GPU的支持度计算 | 第100-103页 |
| 5.2.4 最小DFS编码检测 | 第103-105页 |
| 5.2.5 基于GPU的子图映射生长 | 第105页 |
| 5.3 实验结果及讨论 | 第105-109页 |
| 5.3.1 实验设置 | 第105-106页 |
| 5.3.2 性能评测 | 第106-109页 |
| 5.4 本章小结 | 第109-112页 |
| 第六章 结论与展望 | 第112-116页 |
| 6.1 工作总结 | 第112-113页 |
| 6.2 研究展望 | 第113-116页 |
| 致谢 | 第116-118页 |
| 参考文献 | 第118-130页 |
| 作者在学期间取得的学术成果 | 第130页 |
