一种基于Q-sample的局部相似连接并行算法

局部相似连接能快速找出数据集间的局部相似记录对,是基因序列比对、剽窃检测和数据清洗等研究领域的基本操作。文中主要研究基于MapReduce框架的并行相似连接技术,提出了一种基于Q-sample的局部相似连接算法,解决了局部相似连接的定位问题。该算法采用了过滤验证二阶段模式:在过滤阶段,所提算法使用Q-sample分割方案拆分字符串集,在不丢失任何匹配的基础上生成了高质量的子串,抛弃了大量的无关字符串对;在验证阶段,所提算法优化了LS-Join算法的双向扩展验证方法,通过去除冗余匹配、合并连续匹配和合并非连续匹配等技术提高了算法的验证效率。通过实验对比了不同数据集和编辑距离参数下算法的性能表现,结果显示所提算法在大数据集上的局部相似连接速度快于当前的优秀算法LS-Join。理论分析和实验结果证明,所提算法的相关技术提高了局部相似的连接性能。

大数据处理中MapReduce框架的Q-sample算法设计

为了解决大量重复数据导致MapReduce的混淆消耗过大及网络传输拥堵的问题,设计了一种基于MapReduce框架的相似连接算法Q-sample。该算法首先将Q-sample的子串进行分割以减少过滤阶段的子串数量,从而减少网络传输数量,进而减少相似连接所耗费的时间,然后通过设计三个匹配过滤器和一个统计特征过滤器的方法来提高过滤效率,最后进行相关实验。实验结果表明,算法有效地提高了MapReduce众局部相似自连接速度和字符匹配的过滤效率。