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

摘要：

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

关键词：相似连接、Q-sample、MapReduce、数据清洗、大数据

所属期刊栏目：46

分类号：TP391(计算技术、计算机技术)

资助基金：教育部人文社会科学研究青年基金项目15YJC870021;国家自然科学基金青年基金项目61602056;国家社会科学基金项目19BTQ028;辽宁省自然科学基金20170540015;辽宁省社会科学基金L18AXW001;辽宁省教育厅科学研究项目L2015010

在线出版日期：2020-01-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：38-44