余海洋厦门大学2013年8月.ppt

,余海洋 厦门大学 2013年8月,Pass-Join-K:多分段匹配的字符串相似性连接算法,2,Outline,1、问题定义 2、相关背景 3、算法介绍 4、实验结论,3,1.问题定义,给定一组字符串，要判断出哪些字符串是相似的？ 应用： Web搜索引擎爬取网页时的重复网页检测 去除重复数据后的文档聚类 文档抄袭、剽窃检测 基于查询相似性的用户推荐 DNA序列分析 ,4,1.问题定义,字符串相似性：衡量两个字符串的相似程度 相似性度量： Jaccard 距离： 编辑距离：字符串A通过增，删，替换操作变为字符串B的最小操作数,Baby,Body,Substitution,Bod,Body,Insertion,5,1.问题定义,字符串相似性Join： 给定一组基于字符串为特征的数据集，找出其中相似的字符串配对。 类型： 按操作不同：Self-Join、R-S Join 按应用不同：Jaccard 距离、编辑距离（本文所用度量方法）,6,2.相关背景,候选对-验证 总时间=选择候选对时间+验证时间 相关算法： All-Pairs PPJoin、PPJoin+、Ed-Join Pass-Join,2.相关背景,候选对： 字符串集合：S = vldb,sigmod,. ，R=pvldb,icde, 总集合对数, 候选对： ,.,7,3.算法介绍,Pass-Join: Partition-based method： Threshold = 2,8,3.算法介绍,Pass-Join: Partition-based method： Threshold = 1,9,K=1,K=2,3.算法介绍,10,Pass-Join: Partition-based method： r = “abcdefghijk” s = “abdefghk” 候选对：,L11,1,2,3,4,r,r,r,r,def,3.算法介绍,划分方式： 越长越难匹配，所以每段都尽量一样长,11,3.算法介绍,子串选择： 我们已经划分好了一个串，那么另一个串应该怎么划分呢？ 我们如何减少需要匹配的字串？,12,3.算法介绍,子串选择： Position-aware Multi-match-aware,13,3.算法介绍,Position-aware：Threshold = 2,14,Length=6,Length=7,3.算法介绍,Position-aware：,15,3.算法介绍,Multi-match-aware：Threshold = 3,16,Length=7,Length=8,3.算法介绍,Multi-match-aware：,17,4.实验结论,18,s,Pass-Join-K与Pass-Join算法的时间对比,4.实验结论,19,不同的K值对算法时间的影响,20,4.实验结论,1、本文不局限于原算法的划分，而是通过增加划分段数，来达到更加严格的限制候选对的生成 2、该方法随着K的增加，虽然使得候选对数量得到减少，但是需要更多的空间与查询时间，从而