论文 论文
论文一 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: <4, 6> Figure 1: An example of our partition-based framework
论文一 9 实例分析：