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

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