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

大图上k边连通子图的并行查询和分析技术的研究

作　者: 王文安
导　师: 谷峪
学　校: 东北大学
专　业: 计算机技术
关键词: BSP 图处理统计三角形最大k边连通子图云计算
分类号: O157.5
类　型: 硕士论文
年　份: 2013年
下　载: 0次
引　用: 0次
阅　读: 论文下载

内容摘要

随着互联网应用的迅猛发展,Web网络、社交网络等应用不断涌现,规模也越来越大,随之而来的大规模网络图数据的分析处理问题也成为了研究热点。同时,计算机以及网络技术的发展使得网络数据规模急速增长,在计算机集群中采用并行的分布式计算方式已经成为发展趋势。云计算(Cloud Computing)的一个最主要的优势就是它的优秀的并行处理能力,而这种优势是得益于它的简单高效的并行编程模型。其中,最典型的就是由Google提出的MapReduce分布式并行编程模型。其次,BSP (Bulk Synchronous Parallel)整体同步并行模型也受到非常多的关注。本文旨在研究大图上k边连通子图的并行查询和分析技术。针对k边连通子图的并行查询和分析技术的两个典型问题：统计三角形和最大k边连通子图查询,本文提出了基于BSP模型的解决方案。在统计三角形的问题中,结合经典的集中式算法的优点,提出了并行环境下的混合算法,并提出了消息剪枝,并行采样,结果去重等多种方案来提高并行算法的执行效率。并提出了存储优化以及算法改进,采样去重等优化方案。所有的方案都给出了可靠的理论证明。在最大k边连通子图查询问题中,本文分析了在集中式环境下解决这个问题的基础算法,然后结合BSP框架和基础算法的特点,提出了并行环境下的改进算法,并针对改进算法的特性,提出了多种剪枝和优化策略来减少需要计算的顶点数量。判断顶点是否需要计算的阈值随着算法的运行在动态变化。同时针对准确性要求不高的应用,提出了采样策略作为改进算法的可选部分。所有的剪枝策略,优化策略和采样策略都给出了可靠的理论证明。将本文提出的方案应用于BSP系统中,并通过实验来分析提出的解决方案。在统计三角形问题中,MapReduce下解决方案的处理速度比BSP慢了13倍。本文设计的消息优化策略大幅度的减少了消息的总量,同时采样策略也表现出了良好的性能,估计值的准确率非常高,并且取样之后的加速很明显。最大k边子图查询问题中,随着图的规模的增加,Hadoop (MapReduce)和集中式算法的执行时间非常长。但是在BSP框架下,改进算法的执行时间最多为数分钟。在分析剪枝策略的实验中,设置不同的阈值时,算法的执行时间有明显的减少,同时针对特殊应用的采样策略也拥有很高的准确率。

全文目录

摘要  5-6
Abstract  6-8
目录  8-10
第1章引言  10-14
  1.1 课题的研究背景  10-12
  1.2 研究内容  12
  1.3 本文工作和组织结构  12-14
第2章相关工作概述  14-24
  2.1 MapReduce模型  14-16
    2.1.1 编程模式  14-15
    2.1.2 处理流程  15-16
  2.2 BSP模型  16-18
    2.2.1 概念  17
    2.2.2 通信  17-18
    2.2.3 路障同步  18
  2.3 图中的三角形  18-20
  2.4 最大k边连通子图查询  20-22
  2.5 本章小结  22-24
第3章图中的三角形  24-42
  3.1 引言  24-25
  3.2 存储和索引  25-26
  3.3 SEN-Iterator  26-34
    3.3.1 EN-Iterator  26-28
    3.3.2 消息优化  28-30
    3.3.3 采样策略  30-32
    3.3.4 SEN-Iterator  32-34
  3.4 实验  34-41
    3.4.1 实验环境  34-35
    3.4.2 实验设置  35
    3.4.3 SEN-Iterator算法的整体性能分析  35-37
    3.4.4 剪枝效果分析  37-38
    3.4.5 采样概率p的实验分析  38-39
    3.4.6 采样算法效果分析  39-40
    3.4.7 拓展性  40-41
  3.5 本章小结  41-42
第4章最大K边连通子图查询  42-64
  4.1 引言  42-44
  4.2 基础算法  44-47
  4.3 SSWP算法  47-57
    4.3.1 采样策略  47-48
    4.3.2 优化策略  48-55
    4.3.3 SSWP算法  55-57
  4.4 实验  57-62
    4.4.1 实验设置  57-58
    4.4.2 SSWP算法的整体性能  58-60
    4.4.3 优化策略分析  60-61
    4.4.4 采样策略分析  61-62
    4.4.5 拓展性分析  62
  4.5 本章小结  62-64
第5章总结与展望  64-68
  5.1 本文工作总结  64-65
  5.2 进一步研究的工作  65-68
参考文献  68-72
致谢  72-74
攻硕期间发表的论文及参加的项目  74

大图上k边连通子图的并行查询和分析技术的研究

内容摘要

全文目录

相似论文