MapReduce下相似性連接算法改進的研究.pdf

1、在大數據的時代背景下，拼寫檢查、數據清洗、協(xié)同過濾等應用成為研究熱點，而相似性連接作為這些眾多數據分析的基本操作有著廣泛的應用價值，同時Google提出的MapReduce編程模型是處理海量數據最流行的并行計算模型之一，但因其不能較好的支持相似性連接算法，使得在MapReduce上進行相似性連接成為大數據的一個重要可擴展的研究領域。相似性連接中，以n-gram算法為基礎的傳統(tǒng)算法應用領域非常廣泛，增加了錯誤拼寫對相似性度量的影響，但由于

2、該算法生成的標記存在大量冗余，無形中增加了內存空間的消耗以及運行時間。隨后針對n-gram算法提出了改進的ED-Join算法，在前綴篩選階段減少了前綴標記的數量，但卻給每個標記分配了位置因素，雖然運行時間顯著減少，空間消耗減少卻不多。并且以n-gram算法為基礎的ED-Join算法并沒有在并行架構下實現，無法適應海量數據處理的要求，因此在海量的數據中改進n-gram算法，減少冗余，減少空間消耗以及運行時間成為亟待解決的問題。
　　

3、針對以上問題，本文改進了傳統(tǒng)的n-gram算法以及ED-Join算法，提出一種支持MapReduce的新型算法-n-gram-imp算法。首先，該算法在劃分字符串時，用無冗余滑動窗口代替冗余滑動窗口，僅需選取少量的前綴標記參加過濾即可，使空間利用效率以及運行時間都得到了提升。其次，n-gram-imp算法生成的標記無冗余，需要對篩選出的標記進行針對性的過濾操作，所以提出了Pre-imp前綴過濾算法。最后，在MapReduce計算模型上實