欢迎来到天天文库
浏览记录
ID:1140081
大小:943.50 KB
页数:18页
时间:2017-11-08
《厦门大学数据库实验室》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、厦门大学数据库实验室论文阅读报告三报告人:罗道文导师:林子雨时间:2015年08月07日过渡页1目录EfficientSimilarityJoinsforNearDuplicateDetectionMassJoin:AMapReduce-basedMethodforScalableStringSimilarityJoins12基础知识2XiaoC,WangW,LinX,etal.Efficientsimilarityjoinsfornear-duplicatedetection[J].ACMTransactionsonDatabaseSystems(TODS),2011,36
2、(3):15-24.GuoliangLi ; ShuangHao ; JiannanWang ; JianhuaFeng,MassJoin:AMapReduce-basedMethodforScalableStringSimilarityJoins,DataEngineering(ICDE),2014IEEE30thInternationalConferenceon论文详情:论文一:论文二:基础知识3ppjoin基础知识4字符串格式:基础知识5四种相似度度量函数:Overlapsimilarityis4基础知识6Hammingsimilarityis2。基础知识7公式转换:基
3、础知识8•前缀过滤算法,那前缀到底多长合适了?•根据抽屉原理,如果O(x,y)>=α,那么长度为(
4、x
5、-α+1)的x前缀必须和长度为(
6、y
7、-α+1)的y前缀至少一个匹配。如果α=4,那么前缀长度为2。基础知识9Prefix-length=(
8、x
9、-α+1)}前缀长度=基础知识10举个例子:假设t=2,根据公式假设由y,z,w建倒排索引C={w},G={z},A={y,z},B={y},此时来了一个字符串x,则我们需要到倒排索引中查找B和C的列表,可得(x,y)和(x,w)为候选相似对。基础知识11基于位置过滤:X和y前缀匹配,而且匹配个数为1,那么x和y最大匹配数是多少了
10、?最大匹配数=前缀匹配数+min(x后缀长度,y后最长度)。基础知识12算法执行流程:一个倒排索引和一个字符串迭代字符串前缀每一个元素w[i],查找倒排索引
11、x
12、*t<=
13、y
14、1+ubund>=αA[y]+=1A是一个map,从记录的id到int的映射验证x和y基础知识13C={w}G={z}A={z,y}B={y}假设t=0.8,可得α>=5,x的前缀为B和C,先取出B,然后倒排索引中查找得到y,5>0.8*5=4,符合第一个条件。因为1+ubound=4,所以不符合第二个条件,即不作为侯选集。再取出C,倒排索引中找到w,但3<0.8*5=4,所以直接淘汰。基础知识14验证
15、执行流程:x和A,以及α利用ubound=A[y]+
16、x
17、-px过滤O=O+x和y后缀匹配数如果O>α,则x和y匹配。基础知识15后缀过滤:在字符串x后缀随机选择一个元素w,在y中也找到w(简单考虑,不考虑找不到w的情形)则x和y中,w左右两边的长度差即为海明距离最小值。基础知识16假设海明距离为2,随机选择的元素为F,则H(x,y)最小值为1+1=2,不大于2,所以可作为侯选集。但是如果迭代调用,在F左边随机选择D,则可得H(x,y)最小值为1+2+1=4,大于2,则淘汰,不作为侯选集。举个例子:谢谢
此文档下载收益归作者所有