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

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

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

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