厦门大学数据库实验室

厦门大学数据库实验室论文阅读报告二报告人：罗道文导师：林子雨时间：2015年07月27日过渡页1目录Trie-Join:EfficientTrie-basedStringSimilarityJoinswithEdit-DistanceConstraints

Pass-Join:APartition-basedMethodforSimilarityJoins

12基础知识2基础知识基础知识3知识科普：1、所谓相似性连接(similarityjoin)是指在给定的数据集（同一个数据集，或者两个数据集，甚至多个数据集之间）上并设定相应的阈值，通过某一种相似性度量函数找出所有相似度不小于阈值的数据对的操作。2、四种数据集：字符串相似性连接、集合或多重集合相似性连接、向量相似性连接和图的相似性连接3、相似性度量：汉明距离（hammingdistance）、Levenshtein距离、编辑距离相似性、标准化编辑距离（normalizededitdistance）基础知识4举个例子：编辑距离（EditDistance），又称editdistance距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。例如，有两个字符串t1：string和t2：thing，如果要从t1->t2，编辑距离为2

如果阈值设为3，则t1和t2位相似字符串。论文一5论文一论文一6论文信息：LIGuo-liang，DENGDong，WANGJian-nan，etal．Pass-Join:apartition-basedmethodforsimilarityjoins［J］．ProceedingsoftheVLDBEndowment，2011，5(3):253-264．

论文一7Givenastringrwithτ+1segmentsandastrings,ifsissimilartorwithinthresholdτ,smustcontainasubstringwhichmatchesasegmentofr.辅助定理：字符串s：abdsfddssa字符串r：cykgfdgf论文一8假设有两个字符串集R和S，通过分别迭代R和S中的字符串R1和S1，1、如果R1和S1中有匹配的子字符串，则R1和S1作为候选相似字符串，最后在计算R1和S1的编辑距离ed(R1,S1)，如果ed(R1,S1)<阈值τ，则字符串为相似字符串。2、如果R1和S1没有匹配子字符串，则R1和S1肯定不是相似字符串，即不用计算机R1和S1的编辑距离，减少验证时间。主要思想：先过滤，后验证论文一9实例分析：论文一10问题分析：对于一个字符串S，如果子串长度为i，则有|S|-i+1个子串。字符串S总的子串数：论文一11由于L15中的每一项的长度都相等，所以可以将字符串S按长度来切分，如果长度为i，则S中长度为i的子串有|S|-i+1，所以总的字符串个数为Length-basedMethod:字符串s：abdsfddssa论文一12Shift-basedMethod:avatareshap1子串起点选择：长度为i子串个数为：总的子串个数为：论文一13Position-awareSubstringSelection：总的子串条数为：论文一14Multi-match-awareSubstringSelection

子串总数为：论文一15验证阶段：转换思路：由于计算编辑距离的代价高，所以论文中并未计算候选字符串的编辑距离，而是检验候选字符串的相似距离小于阈值论文一161、M(0,j)=jfor0≤j≤|s|2、for1≤i≤|r|and0≤j≤|s|,

M(i,j)=min(M(i−1,j)+1,M(i,j−1)+1,M(i−1,j−1)+δ)

whereδ=0ifthei-thcharacterofristhesameasthej-thcharacterofs;otherwiseδ=1.

Length-awareVerification论文一17经过一些条件限制，最后只需计算一下公式所包括的元素：r=“kaushukchadhui”s=“caushikchakrabar”用以下公式预估两个字符串的编辑距离：论文二18论文二论文二19论文信息：WANGJian-nan，FENGJian-hua，LIGuo-liang．Trie-join:efficient

trie-basedstringsimilarityjoinswithedit-distanceconstraints［J］．

ProceedingsoftheVLDBEndowment，2010，3(1-2):1219-

1230．

论文二20对论文一的改进：论文一通过过滤之后，剩下即为侯选集，很大程度上提高了性能。然而需要迭代所有侯选集，当字符串集非常大的时候，开销还是很高。论文二通过前缀过滤，可以对侯选集进行剪枝，降低侯选集数量，提高性能。论文二21Givenatrieandastrings,nodeninthetrieiscalledanactivenodeofstringsifed(s,n)≤τ.

假设阈值为1，有一个字符串s：ebay，那么节点4，11和12都为字符串s的activenode。论文二22假设有一个字符串s：ebay，由于13节点不是s的activenode，所以14,15,16,17都将不会和s相似。论