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

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

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

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

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