厦门大学数据库实验室论文阅读报告二

2015 暑假拼血 在战7 夏门大学林 DAYS 厦门大学数据库实验室 论文阅读报告二 报告人:罗道文 导师:林子雨 时间:2015年07月27日

厦门大学数据库实验室 论文阅读报告二 报告人：罗道文 导师：林子雨 时间：2015年07月27日

过渡页 目录 Pass-Join: A Partition-based Method for Similarity Joins 2 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints

过渡页 1 目 录 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 1 Pass-Join: A Partition-based Method for Similarity Joins 2

基础知识 基础知

基础知识 2 基础知识

基础知识 知识科普 1、所谓相似性连接( similarity join)是指在给定的数据集(同一个数据集,或者两个数 据集,甚至多个数据集之间)上并设定相应的阈值,通过某一种相似性度量函数找出所 有相似度不小于阈值的数据对的操作。 2、四种数据集:字符串相似性连接、集合或多重集合相似性连接、冋量相似性连接 和图的相似性连接 3、相似性度量:汉明距离〔 hammingdistance)、 Levenshtein距离、编辑距离相 似性、标准化编辑距离( normalized editdistance)

基础知识 3 知识科普： 1、所谓相似性连接(similarity join)是指在给定的数据集（同一个数据集，或者两个数 据集，甚至多个数据集之间）上并设定相应的阈值，通过某一种相似性度量函数找出所 有相似度不小于阈值的数据对的操作。 2、四种数据集：字符串相似性连接、集合或多重集合相似性连接、向量相似性连接 和图的相似性连接 3、相似性度量：汉明距离（hammingdistance）、Levenshtein 距离、编辑距离相 似性、标准化编辑距离（normalized editdistance）

基础知识 举个例子: 编辑距离( Edit Distance),又称 editdistance距离,是指两个字串之间,由一个 转成另一个所需的最少编辑操作次数。编辑操作包括将—个字符替换成另一个字符 ,插入一个字符,删除一个字符。 例如,有两个字符串t1: string和t2: thing,如果要从t1->t2,编辑距离为2 如果阈值设为3,则t和t2位相似字符串

基础知识 4 举个例子： 编辑距离（Edit Distance），又称editdistance距离，是指两个字串之间，由一个 转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符 ，插入一个字符，删除一个字符。 例如，有两个字符串t1：string和t2：thing，如果要从t1->t2，编辑距离为2 如果阈值设为3，则t1和t2位相似字符串

论文 论文

论文一 5 论文一

论文 论文信息 LI Guo-liang deng dong Wang Jian- nan, et al. Pass -Join a partition-based method for similarity joins [J]. Proceedings of the vldb endowment, 2011, 5 (3): 253-264

论文一 6 论文信息： LI Guo-liang，DENG Dong，WANG Jian-nan，et al． Pass-Join: a partition-based method for similarity joins［J］． Proceedings of the VLDB Endowment，2011，5( 3) : 253-264．

论文 辅助定理: Given a string r with T 1 segments and a string s, if s is similar to r within threshold T s must contain a substring which matches a segment of r. 字符串s: ab ds fd ds(sa字符串r: cy/kg fd gf

论文一 7 Given a string r with τ + 1 segments and a string s, if s is similar to r within threshold τ , s must contain a substring which matches a segment of r. 辅助定理： 字符串s：ab ds fd ds sa 字符串r： cy kg fd gf

论文 主要思想 先过滤,后验证 假设有两个字符串集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的编辑距离,减少验证时间

论文一 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的编辑距离，减少验证时间。 主要思想： 先过滤，后验证

论文 实例分析 SIvankateshI s2-avatareshalsy=kaushic chadurils=kaushik chakrablss=kayshuk chadhuiIs6caushik chakrabar 10 L 15 15 23 hieshik: cha: duri krab ka ik shuk cha: duri krab hui candidate Candidate Candidates Candidates Answer:中 Answer:φ1 Answer:φ I Answer: Figure 1: An example of our partition-based framework

论文一 9 实例分析：