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

作者：刘显敏; 李建中

来源：计算机研究与发展, 2013, S1: 239-247.

• 实体匹配
• 实体同一性
• 消解
• 近似算法
• 启发式算法 entity matching
• entity consistency
• resolution
• approximation algorithms
• heuristic algorithms

实体同一性检测问题,即实体识别问题,是数据质量领域一个比较热门的研究问题.利用运行在两个实体上的实体匹配算法求解实体识别问题是目前研究工作中最主要的一个思路.然而,实体匹配算法的输出结果中可能有"歧义",使得算法的输出很难直接转化为实体识别问题的结果.考虑如何利用额外的知识来消去这种"歧义",形式化定义了实体匹配结果消解问题.该问题被证明是NP-完全问题.一个基于线性规划的近似算法Round被给出,它的近似比是O(log n),针对特殊情况,一个随机近似算法KwikResolution被给出.考虑到两个算法各自的不足,4个直观的启发式算法被给出.实验结果验证了理论分析的结果,并且证明了给出的启发式算法是有效的.

• 单位
  哈尔滨工业大学