余海洋廈門(mén)大學(xué)2013年8月.ppt

,余海洋 廈門(mén)大學(xué) 2013年8月,Pass-Join-K:多分段匹配的字符串相似性連接算法,2,Outline,1、問(wèn)題定義 2、相關(guān)背景 3、算法介紹 4、實(shí)驗(yàn)結(jié)論,3,1.問(wèn)題定義,給定一組字符串，要判斷出哪些字符串是相似的？ 應(yīng)用： Web搜索引擎爬取網(wǎng)頁(yè)時(shí)的重復(fù)網(wǎng)頁(yè)檢測(cè) 去除重復(fù)數(shù)據(jù)后的文檔聚類(lèi) 文檔抄襲、剽竊檢測(cè) 基于查詢(xún)相似性的用戶(hù)推薦 DNA序列分析 ,4,1.問(wèn)題定義,字符串相似性：衡量?jī)蓚€(gè)字符串的相似程度 相似性度量： Jaccard 距離： 編輯距離：字符串A通過(guò)增，刪，替換操作變?yōu)樽址瓸的最小操作數(shù),Baby,Body,Substitution,Bod,Body,Insertion,5,1.問(wèn)題定義,字符串相似性Join： 給定一組基于字符串為特征的數(shù)據(jù)集，找出其中相似的字符串配對(duì)。 類(lèi)型： 按操作不同：Self-Join、R-S Join 按應(yīng)用不同：Jaccard 距離、編輯距離（本文所用度量方法）,6,2.相關(guān)背景,候選對(duì)-驗(yàn)證 總時(shí)間=選擇候選對(duì)時(shí)間+驗(yàn)證時(shí)間 相關(guān)算法： All-Pairs PPJoin、PPJoin+、Ed-Join Pass-Join,2.相關(guān)背景,候選對(duì)： 字符串集合：S = vldb,sigmod,. ，R=pvldb,icde, 總集合對(duì)數(shù), 候選對(duì)： ,.,7,3.算法介紹,Pass-Join: Partition-based method： Threshold = 2,8,3.算法介紹,Pass-Join: Partition-based method： Threshold = 1,9,K=1,K=2,3.算法介紹,10,Pass-Join: Partition-based method： r = “abcdefghijk” s = “abdefghk” 候選對(duì)：,L11,1,2,3,4,r,r,r,r,def,3.算法介紹,劃分方式： 越長(zhǎng)越難匹配，所以每段都盡量一樣長(zhǎng),11,3.算法介紹,子串選擇： 我們已經(jīng)劃分好了一個(gè)串，那么另一個(gè)串應(yīng)該怎么劃分呢？ 我們?nèi)绾螠p少需要匹配的字串？,12,3.算法介紹,子串選擇： Position-aware Multi-match-aware,13,3.算法介紹,Position-aware：Threshold = 2,14,Length=6,Length=7,3.算法介紹,Position-aware：,15,3.算法介紹,Multi-match-aware：Threshold = 3,16,Length=7,Length=8,3.算法介紹,Multi-match-aware：,17,4.實(shí)驗(yàn)結(jié)論,18,s,Pass-Join-K與Pass-Join算法的時(shí)間對(duì)比,4.實(shí)驗(yàn)結(jié)論,19,不同的K值對(duì)算法時(shí)間的影響,20,4.實(shí)驗(yàn)結(jié)論,1、本文不局限于原算法的劃分，而是通過(guò)增加劃分段數(shù)，來(lái)達(dá)到更加嚴(yán)格的限制候選對(duì)的生成 2、該方法隨著K的增加，雖然使得候選對(duì)數(shù)量得到減少，但是需要更多的空間與查詢(xún)時(shí)間，從而