Top-k字符串相似連接算法性能優(yōu)化研究.pdf

1、相似連接算法在數(shù)據(jù)清理、數(shù)據(jù)集成和重復(fù)網(wǎng)頁檢測等領(lǐng)域有著廣泛的應(yīng)用。相似度的度量方法有多種，包括Jaccard相似度，Cosine相似度，Dice相似度和Hamming距離等。本文中主要集中于字符串Jaccard相似度和Cosine相似度連接算法的研究。
　　目前的相似連接算法有兩種類型：基于相似度閾值的相似連接和Top-k相似連接?；陂撝档南嗨七B接就是給定閾值θ，求出字符串集合中不小于θ的字符串對；Top-k相似連接就是閾值未

2、知，需要求出字符串集合中最相似的前k個字符串對。
　　Top-k連接算法非常適合于相似度閾值未知的應(yīng)用場景，目前最為有效的Top-k相似連接算法是Xiao等人提出的Topk-join。但該算法存在問題主要包括：為了減少重復(fù)計算，算法執(zhí)行過程中生成的每一個候選記錄對都需要查找哈希表，從而導(dǎo)致哈希查找代價過大；每次前綴事件只處理記錄的一個Token，使得臨時結(jié)果集逼近真實結(jié)果的速度較慢，同時造成前綴事件和臨時結(jié)果堆的維護代價過大。

3、r>　　針對上述問題，本文提出了一種基于Token批處理的Top-k相似連接算法Opt-join。新算法將Token批處理技術(shù)集成在現(xiàn)有的事件驅(qū)動框架中，以降低前綴事件的處理代價；通過提高后綴過濾的maxdepth深度優(yōu)化算法性能，并對maxdepth的選取給出了定性的分析；通過置換哈希查找與過濾操作的執(zhí)行位置來降低哈希查找代價，并理論證明了該置換的正確性；
　　實驗結(jié)果表明，與Topk-join算法相比Opt-join取得了1.