论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　广播算法['25'28%]。该算法将两个表中较小的一个以广播的形式传输到另一个表数据所在的节点上，然后在每个节点上直接进行连接.算法由一个只有map函数而reduce函数为空的MapReduce作业完成.作业初始化阶段对小表只进行数据广播，然后在Map阶段直接对数据进行Hash连接.由于广播算法没有reduce操作，因此避免了混洗过程中的数据传输和排序.当进行连接的两个表数据量相差很大时，广播小表的数据传输代价将会大大小于混洗过程中的数据传输代价，从而提高连接效率。
　　半连接算法[29]。半连接算法基于广播算法进行改进，旨在减少广播过程中的数据传输量.广播的表只中并不是所有的数据都会参与连接，因此在传输数据之前通过半连接操作去除部分数据.该算法由3个MapReduce作业构成.第1个作业主要扫描S表并生成其连接键值文件S.M^.第2个作业根据文件S.M中的键值过滤只中每个子表的数据，生成一系列的数据文件第3个作业依据过滤后的只表数据执行广播算法.尽管半连接算法减少了广播过程中的数据传输量，但增加了对表S和只的扫描.因此具体选择哪种算法要根据连接表的大小以及连接键值的分布情况决定。
　　分片半连接算法[29]。该算法将半连接的粒度缩小到S的每个分片子表&'，它同样由3个MapReduce作业构成.第1个作业生成S的链接键值文件，与前一个算法不同的是这个作业只有map操作，针对每个子表没生成连接键值文件Sz.k第2个作业执行半连接，针对每个没，根据只的匹配记录文件和标记生成与子表没相对应的广播数据文件只s,.第3个作业只有map操作，每个mapper读入对应的数据文件并直接进行连接操作.与普通的半连接算法相比，分片半连接算法在广播过程中数据传输量较少，但是需要为每个子表Sz过滤一次只。
　　冗余重分区算法[30]。该算法使用一个二维矩阵表示两表的笛卡尔积，通过将满足连接条件的元素设定为"真"表示各种不同连接类型的结果.所有的连接均由一个MapReduce作业完成，通过均衡每个reducer任务输入和输出的数据量来达到减少查询执行时间的目的.算法根据reducer任务的个数r将二维矩阵分成r个大小均衡的区域，每个reducer负责产生相应区域的连接结果，其输入的数据量则等于区域矩形的周长之半.与以往的连接算法不同，在冗余重分区算法中，一个记录可能被重定向到多个reducer任务的区域中.算法正是通过这种冗余重定向实现了非等值连接，并减轻了数据倾斜的影响，但增加了混洗过程中的数据传输量除了两表等值连接，多表等值连接在数据分析和决策支持中的应用也非常广泛，星形连接和链式连接是主要的两种连接形式.文献[31]提出了一种基于"数据冗余传输"的算法.该算法只包含一个MapReduce作业，数据的冗余传输在map之后的混洗过程中进行，冗余传输的次数和方式则由"mapkey"决定.Map键值是多个连接属性的集合，其中每个连接属性对应着一个共享值（share)，表示该属性Hash后的桶数.Mapper输出的每个键值对可能传输到多个reducer，其个数由Map键值中没有被该表覆盖的连接属性共享值的乘积决定.在reduce阶段，直接对传输到本地的数据进行连接.这种算法比较适合星形连接或者表数不多的链式连接，随着链式连接的表数不断增多，传输代价也成倍增加.文献[32]提出了一种利用二部图进行连接的算法，该算法主要应用在链式连接上设参加链式连接表的个数为w,首先使用w个MapReduce作业为每个表生成一个二部图，然后执行2(1)个作业根据二部图按照和链式连接相反的顺序减少每个表参与连接的记录数，最后利用浓密树提高连接的并行度，这样最少再执行W-1)个作业执行连接.该算法从最大程度上减少了连接过程中的数据传输量，但是需要的MapReduce作业个数较多。
　　与等值连接不同，集合相似性连接要求计算两个表（或者集合）中所有元素的相似度，因此减少数据传输的方法比等值连接复杂.文献[33]提出了一种使用MapReduce实现集合相似性连接的算法，利用"前缀过滤"[36]原则减少参加连接的候选数据对.该算法包括3个步骤：第1步计算用于前缀过滤的全局词项排序，包括两个MapReduce作业，分别用于统计和排序，第2步利用词项排序执行前缀过滤并生成连接结果的行键值对（row-IDpar)，第3步根据行键值对取得实际的连接结果，这两步各使用一个MapReduce作业.该算法通过前缀过滤减少了连接过程中的数据传输代价，但其应用范围比较固定，适用于字符串类型的相似连接。
　　(2)基于调整后MapReduce的连接算法
　　原始的MapReduce框架是一个"过滤-聚集"的过程，这对处理同构的数据源比较有效[37]，然而在处理多表连接时会遇到两方面的问题.一方面，参加连接的数据源往往是异构的，因此在连接处理过程中需要对不同数据源的数据进行同构化处理，例如增加数据源标记等.同构化处理过程不但需要额外的存储开销，而且增加了数据传输量.另一方面，原始的MapReduce框架在处理多表连接时会产生大量中间结果和检查点，这也增加了数据传输量。
　　文献[34]针对异构数据源问题对MapReduce框架进行了扩展，在reduce步骤结束后增加了一个merge的步骤，形成Map-Reduce-Merge框架.Merge的输入数据可以来自不同reducer的输出，这样在一个MapReduce作业里可以处理多个数据源.实现连接的过程类似于传统MapReduce上的重分区连接，不过在map阶段不需要为不同表的数据登记标签，merge阶段可以将两个表对应reduer输出的排序数据进行合并连接.新加坡国立大学的研究人员提出了Map^Join-Reduce框架[35]，并对原始MapReduce的处理过程进行了两方面的扩展.针对第1个问题，文献[35]提出了"过滤-连接^聚集"的编程框架，连接函数可从多个数据源读入数据进行处理，连接函数内容和连接顺序由用户定义.针对第2个问题，Map-Join-Reduce对Map完成后的混洗过程进行了扩展，将原来的"一对一"模式扩展成"一对多"模式，Map函数输出的中间结果一次可以传给多个连接函数.这样通过相应的分区策略可以用一个MapReduce作业完成多表连接，从而减少多个作业处理过程带来的大量中间结果存储和传输问题。