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

• 作者: 孙德才 王晓霞
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 相似连接 Q-sample MapReduce 数据清洗 大数据
• 年，卷（期）: 2019,（12）
• 所属期刊栏目: 大数据与数据科学
• 页码范围: 38-44
• 页数: 7页
• 分类号: TP391
• 字数: 8968字
• 语种: 中文
• DOI: 10.11896/jsjkx.190100240

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙德才	渤海大学信息科学与技术学院	9	9	2.0	2.0
2	王晓霞	渤海大学信息科学与技术学院	7	6	1.0	1.0