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

Similarity Join Algorithm Based on Entity

作　　者：刘雪莉[1] 王宏志[1] 李建中[1] 高宏[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《软件学报》2015年第6期1421-1437,共17页Journal of Software

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

摘　　要：按照元组描述的实体对其进行组织和查询处理,是一种管理劣质数据的有效方法.考虑到同一个实体的同一属性存在多个描述的值,因此,基于实体的数据库上的连接是支持多个值的相似性连接.与字符串的相似性连接相比较,实体的相似性连接在数据清洗、信息集成、模糊关键字查询、诈骗检测和文本聚集等领域有着更好的应用效果.通过建立双层索引结构,提出了实体数据库上相似性连接算法ES-JOIN.同时,该方法适用于解决集合中字符串模糊匹配的相似性连接问题,而传统的集合相似性连接只针对集合中元素精确匹配的情况.为了加速连接,还提出了过滤措施对算法进行优化,进一步给出了优化算法OPT_ES-JOIN.实验验证了ES-JOIN算法和OPT_ES-JOIN算法具有很好的效率和可扩展性.实验结果表明,过滤措施具有很好的过滤效果.Taking entity as the basic unit to organize the tuples in query processing is an effective way of managing low-quality data. As many descriptions of attribute value in an entity, join operator must support similarity join over multiple values. Entity similarity join is more effective than traditional similarity join in data cleaning, information integration, fuzzy keyword search, fraud detection, and text aggregation. In this paper, an entity similarity join algorithm, ES-JOIN, is designed by adopting the structure of the double layer prefix index. The presented method is suitable for solving set similarity join problem based on fuzzy elements matching, and thus is a better choice than the traditional set similarity join which only considers exact element match. In order to accelerate the join process, a new filtering measures is proposed to optimize the algorithm, and an optimization algorithm, OPT ES-join, is also obtained. Experiments demonstrate that the ES-JOIN algorithm has good efficiency and scalability, and the filter measures is very effective.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]