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

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

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

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