Part_Join_基于划分的字符串相似性连接.pdf

第 31 卷第 10 期 计 算 机 应 用 研 究 Vol. 31 No. 10 2014 年 10 月 Application Ｒesearch of Computers Oct． 2014 * Part-Join : 基于划分的字符串相似性连接 ， ， 陈懿诚 骆吉洲 李建中 ( ， 150001) 哈尔 滨工业大学 计算机科学与技术 学院 哈尔 滨 : ， ， 摘 要 目前 已有许 多高效的字符串相似性连接算法被提出 但是这些 算法在过 滤的过程 中利用 的往往是 字 ， ， 。 ， 符串本 身的局部信息 而忽略 了字符串集合 的整体信息 故性能没有得到充分的提高 为此 提出了一种基于 划 Part-Join ， 、 、 ， 分的算法 它从频率向量 字母表 频 率分布三方面对数据集进行子 集划分 并给 出子 集 间的过 滤策略 用于排除不相似 的字符串对。扩展 实验表明，Part-Join 比 已有算法 Pass-Join 效率提 高了 10% ～ 15% 。 : ; ; ; 关键词 相似性连接 划分 频率 编辑距离 中图分类号:TP391 文献标志码:A 文章编号:1001-3695 ( 2014) 10-3002-05 doi :10 ． 3969 /j ． issn． 1001-3695． 2014 ． 10 ． 028 Part-Join :partition based string similarity join CHEN Yi-cheng ，LUO Ji-zhou ，LI Jian-zhong (School of Comp uter Science ＆ Techonlogy ，Harbin Institute of Technology ，Harbin 15000 1，China) Abstract :Ｒecently many efficent similarity join algorithms have been proposed ，however ，these algorithms use only the local information of the strings and negelect the global information of the data set ，so the performance has not been sufficiently im- proved． This paper proposed Part-Join ，which