大數(shù)據(jù)集全比較問題的數(shù)據(jù)分配策略研究.pdf

1、大數(shù)據(jù)集全比較是一種特殊的計算問題，對數(shù)據(jù)集中的任意兩個數(shù)據(jù)進行比較計算，廣泛存在于生物信息學，生物計量學，數(shù)據(jù)挖掘等領(lǐng)域?；诜植际酱鎯軜?gòu)的分布式計算由于具有高效益，高可靠性和高可擴展性等優(yōu)點，而被廣泛地用于解決大規(guī)模的計算問題，包括全比較計算。它把一個大問題分解為多個小問題，然后把每個小問題交給分布式系統(tǒng)中的各個節(jié)點來處理。然而，它的性能依賴于數(shù)據(jù)分配，任務分解和任務調(diào)度策略。對于比較任務來說，不合理的數(shù)據(jù)分配和低的數(shù)據(jù)本地性會極

2、大地降低整體的計算性能，此外，分布式系統(tǒng)中不均衡的計算負載也會影響計算性能。
　　本文首先介紹了問題產(chǎn)生的背景，以及對該問題傳統(tǒng)的解決方法的不足。其次，對全比較問題進行了深入的理論研究，模型構(gòu)建，并提出了相應的算法，獲得了好的計算性能。本文的貢獻主要為以下幾點：
　　(1)對全比較問題進行深入的理論剖析，對全比較計算的數(shù)據(jù)分配問題進行了模型構(gòu)建。
　　(2)提出了基于貪心思想的啟發(fā)式的數(shù)據(jù)分配算法。根據(jù)數(shù)據(jù)分配問題的理

3、論模型，提出了啟發(fā)式規(guī)則，并根據(jù)這些規(guī)則提出了數(shù)據(jù)分配算法。保證了所有比較任務的數(shù)據(jù)本地性為100％，與在每個節(jié)點上存儲所有的數(shù)據(jù)文件的策略相比，提高了存儲效率，與Hadoop默認的數(shù)據(jù)分配策略相比，提高了整體的計算性能和良好的可擴展性。
　　(3)提出了基于圖覆蓋的數(shù)據(jù)分配算法。該方法為本文首次提出，用于解決全比較問題。首先，介紹了用圖覆蓋來解決全比較計算的數(shù)據(jù)分配問題的理論基礎(chǔ)。其次，證明了在某種條件下可以構(gòu)造出圖覆蓋的最優(yōu)解