一种基于MapReduce的局部相似自连接算法

王晓霞，孙德才

(渤海大学 信息科学与技术学院，辽宁 锦州 121013)

0 引 言

随着各行各业数据量的飞速增长，大数据的存储、处理、管理和分析等领域已成为当前研究的热点。在大数据处理中，数据清洗的目的是删除冗余信息、纠正存在的错误等。相似连接(similarity join)[1-4]能在给定的数据集中快速找出所有满足相似要求的记录对，是数据清洗中去除相似信息的常用方法。相似连接在基因序列比对、剽窃检测和信息检索等领域也有广泛的应用。

相似连接分为全局连接和局部连接。全局连接要求记录对的整体相似，而局部连接则要求记录对满足局部相似要求即可。相似连接又根据参与连接的数据源数分为自连接和多源连接。当数据源为单个时称为自连接，自连接找出的相似记录对都来源于同一个数据集。而当数据源为两个及以上时称为多源连接，多源连接的相似记录对分别来源于不同的数据集。在相似连接中，衡量一个记录对的相似程度的方法主要包括编辑距离[5-6]、海明距离、Jaccard、Cosine和Dice等。编辑距离是指把一个字符串经过插入、修改或删除三种编辑操作转变成另一个字符串所要进行的最小操作次数。文中用编辑距离衡量字符串对的相似度，因为编辑距离不仅对噪声鲁棒性强，还能体现出两个字符串间字符顺序的差别[6]。

研究相似连接算法的主要目的是加快相似连接的速度，尤其是基于大数据集的相似连接。当前的相似连接算法主要有内存算法和并行算法。内存算法由于运行过程中允许共享大量信息(如索引等)，所以只能运行在单台机器上，如PassJoin[7]、K-Join[8]和LS-Join[9]等。并行算法的设计目的是实现集群多任务并行计算，但并行算法也有共享信息困难的问题。MapReduce框架是Google提出的一种高效的分布式编程框架，在大数据处理中应用广泛。近年来，基于MapReduce框架的相似连接并行算法[6,10-15]的研究也得到了众多学者的关注，如V-SMART-Join[10]、PassJoinKMR[6]、MassJoin[11]、SAX[14]、FS-Join[15]等。

文中研究的主要内容是基于单个字符串集的局部相似自连接并行算法。目前，LS-Join算法是首个基于两个数据集的局部相似连接内存算法，虽然文中也提出了改进的多线程算法，但仍无法实现集群多节点的并行计算。另外，在当前的相关文献中也尚未发现局部相似自连接算法的相关研究。对此，文中提出一种新的基于MapReduce框架的并行连接算法，并拟解决局部相似自连接的定位问题。

1 局部相似自连接及新过滤方案

1.1 局部相似自连接的问题定义

给定一个数据集，局部相似自连接将找出集合中所有存在局部相似的记录对。这里先给出相关问题的定义：

定义2(局部相似自连接的定位问题)：给定一个窗口长度l、一个编辑距离参数τ和一个字符串集S。局部相似自连接的定位问题是从字符串集S中找出所有存在l-τ局部相似的串对,si∈S,sj∈S,i≠j，并同时找出该串对中最长的局部相似子串位置。

表1 例子字符串集

如给定一个字符串集S，如表1所示。数据集中每行是一个字符串的信息，其中‘#’号前面的是字符串编号，而后面的是字符串内容。如l=7,τ=1，则是一个l-τ局部相似对，它们间如最长子串对为ed(s1[4,12],s3[1,9])=1。

1.2 局部相似自连接过滤方案

局部相似自连接的输入包括一个给定的数据集、一个窗口长度和一个编辑距离参数。LS-Join算法[9]是一种基于两个数据集的多源局部相似连接算法。LS-Join算法先读取第一个字符串集并建立一个倒排索引。然后把第二个字符串集中的字符串拆分子串，并在倒排索引中检索子串并生成候选串对。最后，提出了一种基于双向扩展的局部验证方法来验证候选对。该算法也能进行自连接运算，只需输入的两数据集相同即可。但如此连接后，结果集中存在两种冗余记录对，即自身冗余对和正反冗余对。自身冗余对为字符串和本身组成的串对，该串对中因两字符串完全一样，所以一定存在于结果集中，即,si∈S,sj∈S,i=j。正反冗余串对是两个不同编号的字符串组成的串对，但因分先后顺序而形成的冗余，如,si∈S,sj∈S,i≠j和,si∈S,sj∈S,i≠j。这些冗余串对不仅增加了连接算法计算的时间，还增加了结果集的数量。

因给定的数据集中含有大量的字符串，因此也存在着海量的字符串对。为避免枚举所有串对，文中算法采用了过滤验证二阶段模式。为进行快速过滤和去除冗余对，该算法采用了基于分割子串的过滤方案。

定理1(无关对过滤定理)：给定两个字符串si,sj，一个编辑距离参数τ和一个窗口长度l。把串si分割成⎣|si|/q」个连续但不重叠的长度为q的子串(称为Q-sample)，其中q=⎣(l+1)/(τ+2)」,q≥1。此时如字符串对为l-τ局部相似对，则串sj中包含至少一个串si的Q-sample。

定理2(冗余对过滤定理)：给定一个字符串集S，一个编辑距离参数τ和一个窗口长度l。字符串集S中有两个字符串si,sj，其中i为字符串si在集合S中的编号和j为sj的编号，则字符串对集G={,i

证明：在局部相似自连接中，有两种冗余串对，即自身串对和正反串对。条件i

2 基于MapReduce框架的局部相似自连接算法

局部相似自连接的输入包括：一个字符串集S，一个编辑距离参数τ和一个窗口长度l。为实现并行计算，文中的MLSSJ算法采用了分布式编程框架MapReduce，共设计了三个阶段，即过滤阶段、验证阶段1和验证阶段2。

2.1 过滤阶段

为避免枚举所有可能的字符串对，该算法设计了一个MapReduce任务实现无关对和冗余对的快速过滤方案。定理1是一个无关对过滤条件，使用定理1能抛弃那些不共享Q-sample的字符串对。定理2是一个冗余对过滤条件，使用定理2能抛弃影响连接性能的冗余对。为使用定理1和定理2进行快速过滤，MLSSJ算法在过滤阶段先对输入的字符串集S中所有字符串进行子串分割，然后再进行过滤。过滤阶段的MapReduce任务包括三个过程，即Map、Shuffle和Reduce。

(1)Map过程：基于MapReduce框架设计的程序执行中并行交替运行着众多的map任务，每次map任务的输入是一个key-value对，其中sn是分片的编号，而split是输入字符串集S的一行内容。例如表1中的例子集合，一次map的split就是一行内容，即一个字符串的编号和内容。为进行局部相似自连接的前期处理，该算法先提取字符串的编号(记为sid)和字符串内容(记为s)，然后针对字符串s分别生成索引子串和匹配子串，具体过程如下：

(2)Shuffle过程：在MapReduce框架中，shuffle过程将map过程产生的所有key-value对按key值(索引子串和匹配子串)进行混淆、排序，并把具有相同key的key-value对送到同一reduce节点上。

2.2 验证阶段1

过滤阶段输出结果由大量的key-value对构成，其中每个key-value对都是一个候选对集，即一个key-value对包含了某个字符串与集S中所有编号小于该串的候选对。而验证阶段的任务是从这些候选对集中找出真正含有局部相似的串对，并定位最长相似子串的位置。但现在因候选对集只有串编号而没有串内容，所以算法无法验证。为实现候选对集字符串内容的快速读取配对和验证候选对，该算法把验证阶段设计成了两个阶段，即验证阶段1和验证阶段2。

验证阶段1的主要目的是读取集S的字符串内容，并初步进行字符串编号和串内容的配对。它的输入包括集S和过滤阶段的输出结果。验证阶段1的MapReduce任务也包含Map、Shuffle和Reduce三个过程。

2.3 验证阶段2

验证阶段1结束后实现了大编号串编号和串内容的匹配，也给出了每个大编号串对应的候选对集，还输出了需要保留的小编号串内容。但此时仍无法进行候选对的验证工作，因为还缺少小编号串的串内容。验证阶段2的任务是实现小编号串编号和串内容的配对，同时进行最终的验证定位工作。验证阶段2的输入是验证阶段1输出结果。验证阶段2依然包含Map、Shuffle和Reduce三个过程。

3 实 验

3.1 实验环境

为验证文中算法和相关技术的有效性，实验中基于MapReduce框架用Java实现了文中的MLSSJ算法。算法运行环境为Hadoop集群，集群中主节点1个，从节点4个；硬件配置均为CPU i5 4590 四核心、16 G内存和1 TB硬盘。实验中还实现了文献[9]中的LS-Join算法，这里记LSJ-S为单线程算法，记LSJ-M为多线程算法(线程数为4)。实验的数据主要来源于两个数据集，见表2。DBLP集是一个计算机类英文文献的集成数据库，实验中只保留了记录中作者和标题两个字段。GBEST集为NCBI GenBank的表达序列标签(Expressed Sequence Tags, ftp://ftp.ncbi.nlm.nih.gov/)，实验中只保留了序列本身。

表2 实验数据集信息

3.2 算法性能对比及结果分析

评价相似连接算法时，时间性能最为重要。LS-Join算法实验中的最优配置参数DBLP集为l=50,τ=5,q=7，GBEST集为l=100,τ=7,q=9。MLSSJ算法的配置参数除不需要q值外其他与LS-Join算法相同。首先在实验中对比不同大小数据集对各算法性能的影响。实验中分别采用LSJ-S、LSJ-M和MLSSJ算法在不同大小的字符串集分别进行局部相似自连接运算，并统计了各个算法自连接的时间消耗。随着字符串集字符串数量的逐渐增大，各算法的总连接时间变化如图1和图2所示。

图1 DBLP集大小与连接时间

由图1和图2可知，随着数据集中字符串数量的不断增大，LSJ-M算法的连接速度一直快于LSJ-S算法，由此可见多线程并发技术加快了LS-Join算法的连接速度。MLSSJ算法的连接速度要明显快于LS-Join的LSJ-S算法和LSJ-M算法，尤其在小字母表且长字符串的数据集(如GBEST)上新算法性能表现更优。这主要是因为LS-Join算法是一个内存算法，虽然采用了多线程技术但也只能运行在一台机器上。而MLSSJ算法是一个运行在多节点集群上的并行算法，基于MapReduce框架的设计使得它更适合大数据集的局部相似自连接。从图中还可以看出，随着数据集的增大，MLSSJ算法的连接时间基本呈线性增加。

图2 GBEST集大小与连接时间

在相似连接中，编辑距离参数是一个非常重要的参数。为对比各个算法对编辑距离参数的敏感度，实验中还分别采用不同的编辑距离参数对LSJ-M算法和MLSSJ算法在各数据集上进行了局部相似自连接操作。在DBLP集上配置参数为l=50,τ=0,1,3,5(LSJ-M中q=7)， GBEST集上为l=100,τ=0,1,3,5,7(LSJ-M中q=9)。随着编辑距离参数的逐渐增大，各算法的性能表现对比如图3和图4所示。

图3 DBLP集编辑距离与连接时间

图4 GBEST集编辑距离与连接时间

由图3和图4可知，在不同编辑距离参数下MLSSJ算法的速度一直快于LSJ-M算法。该实验主要分析各个算法对编辑距离参数的敏感度。由图3和图4可知，LSJ-M算法随着编辑距离参数不断增大而连接时间变化较小，因此该算法对编辑距离参数的敏感度较小。这主要是因为实验中LSJ-M算法的索引子串长度q值对不同编辑距离参数影响较大，而这里q值固定。实际使用中需要对不同数据集进行q值实验测优，因此该算法也不够灵活。而MLSSJ算法随着编辑距离参数的不断增大，其连接时间也不断增加，因此该算法对编辑距离参数的敏感度较大。这主要是因为MLSSJ算法中切分子串长度是根据编辑距离参数动态计算的，即τ值越小，q值越大，分割得到的子串数目越少，处理所需的时间就越短。因此，MLSSJ算法在编辑距离参数动态变化的局部相似自连接中比LSJ-M算法更具优势。

4 结束语

文中主要研究了基于单个字符串集的局部相似自连接算法。先给出了局部相似自连接定位问题的定义，然后通过分析相似自连接中的无关串对和冗余串对问题，总结出了无关串对过滤定理和冗余串对过滤定理。最后提出了一种基于MapReduce框架的局部相似自连接并行算法。实验结果表明，该算法有效地提高了局部相似自连接的速度。该算法虽然通过MapReduce框架的并行技术加快了局部相似自连接的速度，但仍存在并行节点间数据传输量大和过滤阶段生成的候选对多等问题。下一步将研究更加苛刻的过滤条件，拟通过降低过滤阶段生成的候选对数量来减少验证时间。