高效的实体匹配结果消解算法  

Efficient Algorithms for Resolving Conflicts in Entity Matching Results

作　　者：刘显敏[1] 李建中[1] 

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

出　　处：《计算机研究与发展》2013年第S1期239-247,共9页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2012CB316200)

摘　　要：实体同一性检测问题,即实体识别问题,是数据质量领域一个比较热门的研究问题.利用运行在两个实体上的实体匹配算法求解实体识别问题是目前研究工作中最主要的一个思路.然而,实体匹配算法的输出结果中可能有"歧义",使得算法的输出很难直接转化为实体识别问题的结果.考虑如何利用额外的知识来消去这种"歧义",形式化定义了实体匹配结果消解问题.该问题被证明是NP-完全问题.一个基于线性规划的近似算法Round被给出,它的近似比是O(log n),针对特殊情况,一个随机近似算法KwikResolution被给出.考虑到两个算法各自的不足,4个直观的启发式算法被给出.实验结果验证了理论分析的结果,并且证明了给出的启发式算法是有效的.Entity identification problem is a popular topic in data quality research area.Utilizing entity matching algorithms to solve entity identification problem is a popular method.However,the result of entity matching algorithms has 'conflicts',such that it is hard to obtain solution for entity identification.Considering how to remove such conflicts using external information,the problem of resolving conflicts in entity matching results is formally defined and is proved to be NP-complete.Two approximation algorithms,Round and KwikResolution,are given,with approximation ratio O(log n) and 3L,respectively.Since those two algorithms have their drawbacks,four heuristic algorithms are given also.Experimental results verify the theoretical analysis of the algorithms,and show that the heuristic algorithms work well.

关 键 词：实体匹配 实体同一性 消解 近似算法 启发式算法 

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