基于实体的相似性连接算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

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


Similarity Join Algorithm Based on Entity
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

刘雪莉,王宏志,李建中,高宏.基于实体的相似性连接算法.软件学报,2015,26(6):1421-1437

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2012-11-25
  • 最后修改日期:2014-03-28
  • 录用日期:
  • 在线发布日期: 2015-06-04
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号