基于实体的相似性连接算法

来源：软件学报杂志2015年第6期北京时间：

作者：刘雪莉,王宏志,李建中,高宏

单位：刘雪莉，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000111,王宏志，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000102,李建中，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000103,高宏，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000104

摘要：按照元组描述的实体对其进行组织和查询处理,是一种管理劣质数据的有效方法.考虑到同一个实体的同一属性存在多个描述的值,因此,基于实体的数据库上的连接是支持多个值的相似性连接.与字符串的相似性连接相比较,实体的相似性连接在数据清洗、信息集成、模糊关键字查询、诈骗检测和文本聚集等领域有着更好的应用效果.通过建立双层索引结构,提出了实体数据库上相似性连接算法ES-JOIN.同时,该方法适用于解决集合中字符串模糊匹配的相似性连接问题,而传统的集合相似性连接只针对集合中元素精确匹配的情况.为了加速连接,还提出了过滤措施对算法进行优化,进一步给出了优化算法OPT_ES-JOIN.实验验证了ES-JOIN算法和OPT_ES-JOIN算法具有很好的效率和可扩展性.实验结果表明,过滤措施具有很好的过滤效果.

关键词：实体;相似性连接;劣质数据

基金资助：国家自然科学基金(61003046, 6111113089, 61033015, 60831160525, 61173022); 国家重点基础研究发展计划(973) (2012CB316200, 2012CB316202); 国家高技术研究发展计划(863)(2012AA011004); 海量图数据上实体识别(KF2011003)