分布并行字符串相似性連接方法研究與應(yīng)用.pdf

1、相似性連接是數(shù)據(jù)挖掘分析領(lǐng)域的基礎(chǔ)操作，在數(shù)據(jù)清洗、生物信息學(xué)和信息集成等眾多領(lǐng)域有著廣泛的應(yīng)用意義。相似性連接處理的數(shù)據(jù)類型一般包括字符串、集合、向量和圖等類型，對(duì)于不同數(shù)據(jù)類型對(duì)象之間的相似程度的衡量也有多種度量標(biāo)準(zhǔn)，如杰卡德距離、余弦距離、編輯距離。本文主要研究基于編輯距離度量的字符串相似性連接，即在被查詢字符串?dāng)?shù)據(jù)集中找出所有與給定的查詢字符串集合中元素滿足編輯距離不小于給定閾值的字符串。目前處理字符串的相似性連接算法大多為基于

2、單機(jī)的內(nèi)存算法,他們在處理海量字符串?dāng)?shù)據(jù)時(shí)需要耗費(fèi)大量時(shí)間，而分布式計(jì)算平臺(tái)的興起與廣泛應(yīng)用為高效解決海量字符串連接提供了條件。本文基于Spark并行計(jì)算框架良好的擴(kuò)展性、容錯(cuò)性，將單機(jī)計(jì)算轉(zhuǎn)至集群模式，研究并行字符串相似性連接問題。
　　首先，在對(duì)傳統(tǒng)字符串相似性連接相關(guān)技術(shù)的研究基礎(chǔ)上，設(shè)計(jì)了字符串相似連接的并行化處理框架，在分布式計(jì)算框架Spark中進(jìn)行實(shí)現(xiàn)，給出并分析了并行化的具體實(shí)現(xiàn)過程。通過字符串的頻率向量信息，在數(shù)據(jù)

3、劃分的基礎(chǔ)上，有效地過濾掉不符合相似條件的字符串，避免了大量的無效計(jì)算，通過實(shí)驗(yàn)證明了數(shù)據(jù)并行化與計(jì)算并行化能夠有效的提高海量字符串相串相似連接的處理效率。
　　其次，對(duì)字符串的相似連接進(jìn)行優(yōu)化，主要包括并行化算法的優(yōu)化及平臺(tái)的優(yōu)化。在并行化算法方面，對(duì)字符串聯(lián)合頻率向量進(jìn)行廣播，減少連接過程中數(shù)據(jù)傳輸量。由于Spark基于內(nèi)存計(jì)算的特性，集群環(huán)境中數(shù)據(jù)傳輸成為Spark計(jì)算平臺(tái)的瓶頸，對(duì)此，在計(jì)算平臺(tái)方面，針對(duì)任務(wù)調(diào)度策略中數(shù)據(jù)