基于划分的增量式字符串相似性连接方法  

Partition-based incremental processing method for string similarity join

作　　者：燕彩蓉[1] 朱斌[1] 王健[1] 黄永锋[1] 

机构地区：[1]东华大学计算机科学与技术学院,上海201620

出　　处：《计算机应用》2016年第1期27-32,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61402100);中央高校基本科研业务费专项(2232013D3-15)~~

摘　　要：字符串相似性连接是数据质量管理的基本操作,也是数据价值发现的关键步骤。针对目前已有的方法不能满足面向大数据的增量式处理需求的问题,提出一种面向流式数据的增量式字符串相似性连接方法——IncJoin,并对方法的索引技术进行了优化。该方法以Pass-Join字符串连接算法为基础,首先,采用字符串划分技术将字符串划分成多个互不相交的子串;然后,建立字符串的反向索引列表并将其作为状态;最后,新增数据只需根据状态进行相似性计算,每次连接操作结束后都对状态进行更新。实验结果表明,Inc-Join方法在不影响连接准确率的同时,有效将长、短字符串重复匹配次数减少为n^(1/2)(n是批处理方式的匹配次数)。实验对3种数据集进行处理,发现使用批处理方式进行相似性连接的响应时间是Inc-Join的1至4.7倍,并呈现急剧递增的趋势;而且优化后Inc-Join方法的响应时间最小只占优化前的3/4,并随处理数据的增多所占比例越来越小。同时优化后的Inc-Join不需要保存状态,再一次减小了算法执行的时间和空间开销。String similarity join is an essential operation of data quality management and a key step to find the value of data. Now in the era of big data, since the existing methods can not meet the demands of incremental processing, an incremental string similarity join method oriented streaming data, called Inc-Join, was proposed. And the string index technique was optimized. Firstly, based on the Pass-Join string join algorithm, strings were divided into some disjoint substrings by utilizing partition technique; secondly, the inverted index of strings was created and acted as a state; finally, the similarity calculation was done according to the state when new data came, and the state would be updated after each operation of string similarity join. The experimental results show that Inc-Join method can reduce the number of reduplicate matching between short or long strings to n√n（ n is the number of matching with batching processing model） without affecting the join accuracy. The elapsed time of string similarity join with batching processing model was 1 to 4. 7 times the time Inc-Join needs when three different datasets were processed, and it tended to increase sharply. And the minimum elapsed time of optimized Inc-Join only accounted for 3 /4 of original elapsed time of Inc-Join. With the increasing number of strings, the elapsed time of optimized Inc-Join would account for less and less of proportion in original elapsed time. The state need not to be saved, so the optimized Inc-Join further reduces time and space cost of Inc-Join.

关 键 词：字符串相似性连接 增量处理 划分 字符串匹配 反向索引 

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