大数据图数据库之MapReduce用于图计算，数据库mapreduce

大数据图数据库之MapReduce用于图计算，数据库mapreduce

/* 版权声明：可以任意转载，转载时请务必标明文章原始出处和作者信息 .*/
                 CopyMiddle: 张俊林                    

节选自《大数据日知录：架构与算法》十四章，书籍目录在此

1.使用Mapreduce进行图计算

          使用MapReduce框架来针对大规模图数据进行计算的研究工作相对较少，这主要归结于两方面原因：一方面，将传统的图计算映射为MapReduce任务相对其他类型的很多任务而言不太直观；另一方面，从某种角度讲，使用该分布计算框架解决图计算任务也并非最适宜的解决方案。

     尽管有上述缺点，但很多图算法还是可以转换为Mapreduce框架下的计算任务。下面以PageRank计算为例讲述如何在该框架下进行图计算。PageRank的计算原理在前面已有介绍，本节重点分析如何在Mapreduce框架下对算法进行改造，使得可以用多机分布方式对大规模图进行运算。

      Mapreduce框架下的输入往往是key-value数据对，其中，value可以是简单类型，比如数值或字符串，也可以是复杂的数据结构，比如数组或者记录等。对于图数据来说，其内部表示方式以邻接表为宜，这样，输入数据的key为图节点ID，对应的value为复杂记录，其中记载了邻接表数据、key节点的PageRank值等。

      对很多图算法来说，Mapreduce内部计算过程中的Shuffle和Sort操作起到类似于通过图中节点出边进行消息传播的效果。从图14-7的PageRank伪码中可见此技巧的运用。

       在该例的Map操作中，输入数据的key是图节点ID，value是图节点数据结构N，其中包括邻接表AdjacencyList信息以及节点对应的当前PageRank值。第3行代码计算当前节点传播到邻接节点的PageRank分值，第5、6行代码将这些分值转换为新的key1-value1，以邻接节点ID作为新的key，而从当前节点传播给邻接节点的分值作为新的value1。除此之外，还需要将当前节点的节点信息继续保留，以便进行后续的迭代过程，所以第4行代码将输入记录本身再次原封不动地传播出去。

       Mapreduce计算框架在Map操作后会通过网络通信将具有相同key值的中间结果记录映射到同一台机器上，以满足后续Reduce阶段操作的要求。一般情况下，这种网络传输数据量非常大，往往会严重影响计算效率，而Combine操作即为减少网络传输以优化效率而提出。Combine操作在本地机器Map操作后，首先将具有相同key值的Map结果数据value部分进行本地聚合，这样本来应该分别传输的项目即被合并，大大减少了网络传输量，加快了计算速度。对于图计算，同样可以采用这种优化手段改善效率，图14-8展示了相应的Combine操作，其运行流程与Reduce操作大体相似，第4行到第8行代码累加相同key的本地value数据，第9行代码将这种累加数据传播出去，key保持不变，value成为聚合数据s，这样就大量减少了网络传输量。

       上面介绍了如何在Mapreduce框架下进行PageRank计算，很多其他图算法也可用近似的思路处理，其关键点仍然是通过上述的Shuffle和Sort操作，将同一节点的入边聚合到一起，而Reduce操作可以类似例中的部分数值求和，也可能是取边中的Max/Min等其他类型的操作，这依据应用各异，但基本思想无较大的区别。

2．MapReduce在图计算中存在的问题

        MapReduce尽管已经成为主流的分布式计算模型，但有其适用范围，对于大量的机器学习数据挖掘类科学计算和图挖掘算法来说，使用Mapreduce模型尽管经过变换也可以得到解决，但往往并非解决此类问题的最佳技术方案。根本原因在于：很多科学计算或者图算法内在机制上需要进行多轮反复迭代，而如果采用Mapreduce模型，每一次迭代过程中产生的中间结果都需要反复在Map阶段写入本地磁盘，在Reduce阶段写入GFS/HDFS文件系统中，下一轮迭代一般是在上一轮迭代的计算结果的基础上继续进行，这样需要再次将其加载入内存，计算得出新的中间结果后仍然写入本地文件系统以及GFS/HDFS文件系统中。如此反复，且不必要的磁盘输入/输出严重影响计算效率。除此之外，每次迭代都需要对任务重新进行初始化等任务管理开销也非常影响效率。

      对Mapreduce模型来说，计算分为两个阶段，即Map阶段和Reduce阶段。针对上述问题，Map阶段的最初输入即为稍加改造的图G的邻接表，除了节点的邻接表信息外，还需要额外记载节点当前获得的最小距离数值。以常见的key-value方式表示为：key=节点ID，value=<节点到源节点A的当前最小距离Dist，邻接表>。以源节点A为例，其Map阶段的输入为：<A, <0, <(B, 10),(D, 5)>>>，其他节点输入数据形式与此类似。

      Map阶段对输入数据的转换逻辑为：计算key节点的邻接表中节点到源节点A的当前最短距离。即将key-value转换为key1-value1序列，这里key1是key节点的邻接表中节点ID，value1为key1节点到源节点A的当前最短距离。以源节点A为例，其输入为<A, <0, <(B, 10), (D, 5)>>>，经过Map转换后，得到输出<B,10>和<D,5>，<B,10>的含义是：B节点到A节点的当前最短距离是10（由A节点到源节点A距离0加上B节点到A节点距离10获得），<D,5>的含义与之类似。通过此步可以完成Map阶段计算，图14-10展示了原始输入转换为Map阶段输出结果对应的KV数值。

       在Map阶段产生结果后，系统会将临时结果写入本地磁盘文件中，以作为Reduce阶段的输入数据。Reduce阶段的逻辑为：对某个节点来说，从众多本节点到源节点A的距离中选择最短的距离作为当前值。以节点B为例，从图14-10中Map阶段的输出可以看出，以B为key有两项：<B,10>和<B,inf>，取其最小值得到新的最短距离为10，则可输出结果<B,<10,<(C,1),(D,2)>>>。图14-11展示了Reduce阶段的输出。

      在Reduce阶段结束后，系统将结果写入GFS/HDFS文件系统中，这样完成了单源最短路径的一轮计算。使得图节点B和图节点D的当前最短路径获得了更新。而为了能够获得最终的结果，还需要按照上述方式反复迭代，以本轮Reduce输出作为下一轮Map阶段的输入。由此可见，如果完成计算，则需要多次将中间结果往文件系统输出，这会严重影响系统效率。这是为何Mapreduce框架不适宜做图应用的主要原因。

摘 要 本文以VB6与Access97作为开发工具，介绍了图像在数据库中的存储与显示技术。

关键词 数据库，数据控件，二进制，图像存储，图像显示，ADODB，Recordset

数据库是数据管理的最新技术，是计算机科学的重要分支，是现代计算机信息系统和计算机应用的基础和核心。在科学技术高速发展的今天，在信息资源无处不在、无处不用，已成为各部门的重要财富的时候，对于从事程序开发的人员来说显得尤为重要。

如今，对数据库的操作不仅仅满足于对字符和数字的单一操作，图像的存储与显示已显得尤为重要。下面作者将以VB6.0与Access97作为开发工具，分别介绍两种图像显示与存储的方法。

利用数据控件和数据绑定控件

利用这种方法，不写或写少量代码就可以构造简单的数据库应用程序，这种方法易于被初学者接受。在举例之前，先把数据绑定功能简要的说明一下，凡是具有DataSource属性的控件都是对数据敏感的，它们都能通过数据控件直接使用数据库里的数据。比如CheckBox Control , ComboBox Comtrol , TextBox Comtrol , PictureBox Control ,Image Comtrol … 因为这种方式涉及到的知识点比较少，也比较容易理解，不多作说明，现直接介绍编程步骤。

1、从数据库中显示所需要的图片

首先，添加一个Data数据控件,设置它的DatabaseName和RecordSource属性，

strPath = App.Path
If Right(strPath, 1) <> "\" Then
strPath = strPath & "\"
MyData.DatabaseName = strPath & "ExampleDB.mdb" '数据库存地址
MyData.RecordSource = "Info" '表名

第二步，添加Image控件用来显示图片，设置它的DataSource和DataField属性。例如本例中: Image1.DataSource="MyData"和Image1.DataField=" MyPhoto" 。然后设置其它具有数据绑定功能的控件用来显示所要的其它内容，经过这两步的操作，运行程序就可以显示你要的数据了。

2、向数据库中添加需要存储的图片

首先，利用数据控件所具有的AddNew属性，添加一个按钮，双击后添加如下代码MyData.Recordset.AddNew

第二步，为Image控件图片指定图片路径Image1.Picture = LoadPicture("图片路径")，经过这两步的操作，就可以向数据库中添加图片了。

这种方法最简单快捷，要写的代码量很少。但是这种方法在运行速度和灵活性方面有一定的限制，适合于初学者和一些简单的应用，要想灵活多变的显示图像，下面介绍的方法或许更适应您的要求。

利用编写代码实现图片的存储与显示

这种方法相对于方法一来说，代码量大，但是它操作灵活，能够满足多样形式下的操作，受到更多编程者的青睐。但是涉及到的知识面相对要多一些，不仅要掌握数据库的操作方法，还要二进制文件的读写作进一步的了解。关于数据库及二进制文件的基本操作很多参考书上都介绍的比较详细，需要时请查阅即可。在编程之前把......余下全文>>
 

大数据[2]技术的战略意义不在于掌握庞大的数据信息，而在于对这些含有意义的数据进行专业化处理。换言之，如果把大数据比作一种产业，那么这种产业实现盈利的关键，在于提高对数据的“加工能力”，通过“加工”实现数据的“增值”。
从技术上看，

大数据与云计算的关系[3]
大数据与云计算的关系就像一枚硬币的正反面一样密不可分。大数据必然无法用单台的计算机进行处理，必须采用分布式计算架构。它的特色在于对海量数据的挖掘，但它必须依托云计算的分布式处理、分布式数据库、云存储和虚拟化技术。[3]
随着云时代的来临，大数据（Big data）也吸引了越来越多的关注。《著云台》的分析师团队认为，大数据（Big data）通常用来形容一个公司创造的大量非结构化和半结构化数据，这些数据在下载到关系型数据库用于分析时会花费过多时间和金钱。大数据分析常和云计算联系到一起，因为实时的大型数据集分析需要像MapReduce一样的框架来向数十、数百或甚至数千的电脑分配工作。
大数据需要特殊的技术，以有效地处理大量的容忍经过时间内的数据。适用于大数据的技术，包括大规模并行处理（MPP）数据库、数据挖掘电网、分布式文件系统、分布式数据库、云计算平台、互联网和可扩展的存储系统。