大規(guī)模字符串連接的并行化研究與應(yīng)用.pdf

1、隨著互聯(lián)網(wǎng)的快速發(fā)展，信息的傳遞日益頻繁，海量的信息使得個(gè)人的接受能力嚴(yán)重超載。如何能夠從這些海量信息中準(zhǔn)確、快速獲取所需內(nèi)容成為一個(gè)急需解決的問(wèn)題。字符串相似性連接技術(shù)是最為有效的解決辦法。字符串相似性連接在現(xiàn)實(shí)應(yīng)用中具有深遠(yuǎn)的意義。它在文本檢索、生物信息學(xué)、信號(hào)處理、入侵檢測(cè)等領(lǐng)域有著廣泛的應(yīng)用。
　　本文重點(diǎn)研究如何高效地處理大規(guī)模字符串相似性連接的問(wèn)題，并針對(duì)該問(wèn)題提出了兩種并行化的解決方案。本文首先深入研究了字符串相似度

2、連接技術(shù)，將衡量字符串相似度多種方法，根據(jù)處理對(duì)象的不同分成了兩類，并結(jié)合實(shí)際的例子展示了算法的計(jì)算的過(guò)程、結(jié)果，以及相似度的計(jì)算公式及應(yīng)用領(lǐng)域。介紹了已有的相似度連接方法，根據(jù)算法的處理策略將它們分為兩類，接著探討了這些算法在處理大規(guī)模字符串相似性連接問(wèn)題時(shí)的優(yōu)缺點(diǎn)，進(jìn)而提出了更加高效的字符串的并行化連接方法。本文的主要貢獻(xiàn)有：
　　(1)深入研究了字符串相似性連接過(guò)程中所涉及的相關(guān)概念及技術(shù)，分析發(fā)現(xiàn)，現(xiàn)有方法在處理大規(guī)模字符

3、串相似性連接問(wèn)題時(shí)效率較低，且容易出現(xiàn)內(nèi)存不足等問(wèn)題。
　　(2)提出了一種新的基于內(nèi)存的并行化連接算法——Para-Join。首先根據(jù)每個(gè)字符串的區(qū)間向量將數(shù)據(jù)集劃分成若干個(gè)不相交的子集。為了實(shí)現(xiàn)單個(gè)子集的連接和兩個(gè)不同子集間的連接，本文還提出了兩種基于劃分框架的算法Para-RR和Para-RS。Para-Join算法不僅能保證結(jié)果的完整性而且也不會(huì)帶來(lái)冗余計(jì)算。它通過(guò)多線程編程來(lái)實(shí)現(xiàn)并行化的字符串連接，提高了字符串相似性連接

4、的效率。
　　(3)針對(duì)Para-Join算法無(wú)法解決內(nèi)存不足的問(wèn)題。本文在Para-Join的基礎(chǔ)上提出了一種基于Spark框架的并行化連接算法——Spss-Join，該算法彌補(bǔ)的Para-Join的不足：Spss-Join算法能夠自動(dòng)獲取token集而且不需要明確指出線程數(shù)量，交由Spark框架自行處理，使得Spss-Join算法更加靈活，能夠適應(yīng)更多的應(yīng)用和環(huán)境；Spss-Join算法解決了內(nèi)存容量對(duì)數(shù)據(jù)集大小的限制，能有效