article20201115

Posted on Edited on

大数据 | 大数据基础--算法之并行计算算法：计算最小支撑树（生成树）

亲爱的读者朋友大家晚上好，上次我们简单介绍了并行算法以及有关矩阵乘法的几个基本问题，这次我们来分析基于MapReduce的计算最小生成树算法。

MR简介

还是先把MapReduce每个操作的定义放在下面。

MapReduce

使用MR模型进行计算有几个要点：

  • 计算分轮次进行，每一轮的输入和输出的数据都是形如\(<key,value>\)的
  • 每一轮分为：Map、Shuffle、Reduce
  • Map：每个数据被map函数处理，输出一个新的数据集合，也就是改变了\(<key,value>\)
  • Shuffle：对编程人员透明，所有在Map中输出的数据，被按照key分组，具备相同key 的数据被分配到相同的reducer
  • Reduce：输入\(<k,v_1,v_2,...>\)，输出新的数据集合
  • 针对这样的计算框架，我们的设计目标为：更少的轮数、更少的内存、更大的并行度

问题简介

相信有很多读者知道最小生成树的概念和定义，但是为了完整性（凑字数），还是把形式化的定义再写一遍。

已知图\(G = (V,E)\)，其中\(V,E\)分别是图的点集合和边集合。图\(G\)的一个子图\(T^*=(V,E')\)被称为最小生成树当且仅当\(T^*\)是连通的并且\(\sum_{(u,v)\in T^*}{w(u,v)} = \min_{T}\{\sum_{(u,v)\in T}{w(u,v)}\}\)。

在小数据范围内，通常使用\(Kruskal\)或\(Prim\)算法求解，当图的规模变得较大时，由于这两个算法的复杂度的限制，在有限时间内将无法求解。这时可以借助MapReduce来加速计算。

算法主要思想

利用图划分算法，将图\(G\)划分成\(k\)个子图，在每个子图中计算最小生成树，具体如下。

  1. 将节点分成\(k\)部分，对每一个\((i,j)\in [k]^2\)，令\(G_{ij} = (V_i\cup V_j,E_{ij})\)为节点\(V_i\cup V_j\)上的导出子图
  2. 在每个\(G_{ij}\)上分别求解\(M_{ij}=MSF(G_{ij})\)
  3. 令\(H = \cup_{i,j}M_{ij}\)，计算\(M = MST(H)\)

注：\(MSF\)指的是最小生成森林，举个例子来说明这个概念，在一个最小生成树中有\(n-1\)条边，可以理解为是一个只有一棵树的最小生成森林。同理，在同一个图中也存在有两棵树、三棵树的最小生成森林，只要这个森林是\(\min\{\sum_{(u,v)\in Forest}w(u,v)\}\)就可以。

本质上讲，算法的本质就是先在局部算好生成树，然后用剩余的连接这些生成树的边组成一个新的图，并求出这个新的图的最小生成树作为最总的结果。

MR算法

  • Map：input: \(<(u,v),NULL>\)
    • 转化\(<(h(u),h(v));(u,v)>\)
    • 针对上述转化数据，如果\(h(u) = h(v)\)，则对所有\(j \in [1,k]\)，输出\(<(h(u),j);(u,v)>\)
  • Reduce：input:\(<(i,j);E_{ij}>\)
    • 令\(M_{ij} = MSF(G_{ij})\)
    • 对\(M_{ij}\)中的每条边\(e=(u,v)\)输出\(<NULL;(u,v)>\)
  • Map：nothing（identity）
  • Reduce：\(M = MST(H)\)

其中\(h\)是哈希函数，可以用一个取值均匀的随机算法实现（ps：用随机算法生成哈希表，而不是每次运行都随机取值）。

当然在划分时还要考虑各个计算节点的负载均衡问题。

总结

以上就是利用并行计算解决最小生成树问题的一个简要算法，关于并行计算的算法到这里就介绍结束了。从下一次开始，我们将会介绍一些外存算法，外存算法主要考虑由磁盘和内存之间的IO产生的时间开销以及大量数据无法直接载入内存的问题，届时我们会着重的分析两个排序算法：一个是外存排序算法，另一个是链表排序算法。