余海洋厦门大学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-PairsPPJoin、PPJoin+、Ed-JoinPass-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-awareMulti-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的增加，虽然使得候选对数量得到减少，但是需要更多的空间与查询时间，从而K值并不是越大越好。3、本文提供了一个思路，即通过匹配次数的增加，使得候选对减少，相信会有较多的算法能够用到此思想。,21,谢谢！,