余海洋厦门大学2013年8月.ppt
《余海洋厦门大学2013年8月.ppt》由会员分享,可在线阅读,更多相关《余海洋厦门大学2013年8月.ppt(21页珍藏版)》请在三一文库上搜索。
1、,余海洋 厦门大学 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,In
2、sertion,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-b
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 海洋 厦门大学 2013
链接地址:https://www.31doc.com/p-3254258.html