论文阅读报告-厦门大学数据库室

厦门大学数据库实验室论文阅读报告三报告人：罗道文导师：林子雨时间：2015年08月07日过渡页1目录EfficientSimilarityJoinsforNearDuplicateDetectionMassJoin:AMapReduce-basedMethodforScalableStringSimilarityJoins12基础知识2XiaoC,WangW,LinX,etal.Efficientsimilarityjoinsfornear-duplicatedetection[J].ACMTransactionsonDatabaseSystems(TODS),2011,36(3):15-24.GuoliangLi;ShuangHao;JiannanWang;JianhuaFeng，MassJoin:AMapReduce-basedMethodforScalableStringSimilarityJoins，DataEngineering(ICDE),2014IEEE30thInternationalConferenceon论文详情：论文一：论文二：基础知识3ppjoin基础知识4字符串格式：基础知识5四种相似度度量函数：Overlapsimilarityis4基础知识6Hammingsimilarityis2。基础知识7公式转换：基础知识8•前缀过滤算法，那前缀到底多长合适了？•根据抽屉原理，如果O(x,y)=α，那么长度为(|x|-α+1)的x前缀必须和长度为(|y|-α+1)的y前缀至少一个匹配。如果α=4，那么前缀长度为2。基础知识9Prefix-length=(|x|-α+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最大匹配数是多少了？最大匹配数=前缀匹配数+min(x后缀长度，y后最长度)。基础知识12算法执行流程：一个倒排索引和一个字符串迭代字符串前缀每一个元素w[i]，查找倒排索引|x|*t=|y|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，50.8*5=4，符合第一个条件。因为1+ubound=4，所以不符合第二个条件，即不作为侯选集。再取出C，倒排索引中找到w，但30.8*5=4，所以直接淘汰。基础知识14验证执行流程：x和A，以及α利用ubound=A[y]+|x|-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，则淘汰，不作为侯选集。举个例子：谢谢