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

来源：计算机技术与发展杂志2020年第02期北京时间：

作者：王晓霞;孙德才

摘要：局部相似自连接能在给定的单个数据集中快速找到所有满足相似要求的记录对,它在数据清洗、基因序列比对和 剽窃检测等领域都有广泛的应用。 为研究基于单个字符串集的并行自连接算法,提出了一种基于MapReduce框架的自连 接算法,解决了局部相似自连接的定位问题。 该算法采用了过滤验证二阶段模式;在过滤阶段,采用无关对过滤和冗余对 过滤抛弃了大量的无效字符串对;在验证阶段,通过生成小编号串内容保留项解决了字符串编号和内容的快速配对问题。 实验结果显示,该算法在大数据集上的自连接速度一直快于当前的优秀算法LS-Join,同时非常适合动态编辑距离参数环 境下的局部相似自连接操作。 实验结果也证明,该算法中提出的相关技术有效地提高了局部相似自连接的速度。

关键词：相似连接;自连接;MapReduce;数据清洗;大数据