Part-Join:基于划分的字符串相似性连接  

Part-Join: partition based string similarity join

作　　者：陈懿诚[1] 骆吉洲[1] 李建中[1] 

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

出　　处：《计算机应用研究》2014年第10期3002-3006,共5页Application Research of Computers

基　　金：国家重点基础研究发展计划资助项目(2012CB316202)

摘　　要：目前，已有许多高效的字符串相似性连接算法被提出，但是这些算法在过滤的过程中利用的往往是字符串本身的局部信息，而忽略了字符串集合的整体信息，故性能没有得到充分的提高。为此，提出了一种基于划分的算法Part—Join，它从频率向量、字母袁、频率分布三方面对数据集进行子集划分，并给出子集间的过滤策略用于排除不相似的字符串对。扩展实验表明，Part—Join比已有算法Pass—Join效率提高了10％～15％。Recently many effieent 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 partitioned the data set into subsets with the help of frequency vector, alphabet and frequency distribution, meanwhile, it deviced some prunning strategies to filter out dissimilar string pairs. Experimental results show that the algorithm presented is more efficient than Pass-Join with the efficiency incresed by 10% to 15%.

关 键 词：相似性连接 划分 频率 编辑距离 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]