基于划分的增量式字符串相似性连接方法

• 作者: 朱斌 燕彩蓉 王健 黄永锋
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 字符串相似性连接 增量处理 划分 字符串匹配 反向索引
• 年，卷（期）: 2016,（1）
• 所属期刊栏目: 第32届中国数据库学术会议(NDBC 2015)
• 页码范围: 27-32
• 页数: 6页
• 分类号: TP311
• 字数: 7252字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2016.01.0027

摘要

字符串相似性连接是数据质量管理的基本操作,也是数据价值发现的关键步骤.针对目前已有的方法不能满足面向大数据的增量式处理需求的问题,提出一种面向流式数据的增量式字符串相似性连接方法——IncJoin,并对方法的索引技术进行了优化.该方法以Pass-Join字符串连接算法为基础,首先,采用字符串划分技术将字符串划分成多个互不相交的子串;然后,建立字符串的反向索引列表并将其作为状态;最后,新增数据只需根据状态进行相似性计算,每次连接操作结束后都对状态进行更新.实验结果表明,Inc-Join方法在不影响连接准确率的同时,有效将长、短字符串重复匹配次数减少为√n(n是批处理方式的匹配次数).实验对3种数据集进行处理,发现使用批处理方式进行相似性连接的响应时间是Inc-Join的1至4.7倍,并呈现急剧递增的趋势;而且优化后Inc-Join方法的响应时间最小只占优化前的3/4,并随处理数据的增多所占比例越来越小.同时优化后的Inc-Join不需要保存状态,再一次减小了算法执行的时间和空间开销.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	燕彩蓉	东华大学计算机科学与技术学院	21	155	8.0	12.0
2	黄永锋	东华大学计算机科学与技术学院	23	118	6.0	10.0
3	王健	东华大学计算机科学与技术学院	6	2	1.0	1.0
4	朱斌	东华大学计算机科学与技术学院	3	3	1.0	1.0