數(shù)據(jù)流的分布并行n-of-N Skyline查詢處理技術(shù)研究.pdf

1、數(shù)據(jù)流作為一種新的數(shù)據(jù)存在形式，廣泛應(yīng)用于諸如金融數(shù)據(jù)分析、傳感器網(wǎng)絡(luò)、記憶位置的服務(wù)等現(xiàn)實應(yīng)用中。數(shù)據(jù)流查詢處理已經(jīng)成為當前大數(shù)據(jù)環(huán)境下數(shù)據(jù)庫研究領(lǐng)域的一個熱點問題。伴隨著分布式計算環(huán)境的興起，分布并行化已經(jīng)成為當前數(shù)據(jù)流研究領(lǐng)域的一個重要的發(fā)展趨勢，實現(xiàn)流處理的分布并行化不僅能夠滿足用戶日益增長的查詢實時性需求，還能夠克服單機集中式查詢處理方法所遇到的計算能力不足等問題。
　　數(shù)據(jù)流n-of-N Skyline查詢是一種新型的

2、數(shù)據(jù)流Skyline查詢。其查詢形式相對于一般數(shù)據(jù)流 Skyline查詢更加復(fù)雜，對計算節(jié)點性能要求更高。而且當數(shù)據(jù)流工作負載變化過大時，現(xiàn)有的單機集中式查詢方法因計算能力限制難以提供更高的查詢效率與靈活性。因此，針對數(shù)據(jù)流n-of-N Skyline查詢，對其進行并行化處理研究具有很重要現(xiàn)實意義。
　　針對已有的單機集中式n-of-N Skyline查詢算法無法滿足更高的查詢實時性的問題，提出了一種適用于n-of-N Skyli

3、ne查詢的并行查詢模型 nNPM，并基于此模型提出了一種分布并行n-of-N Skyline查詢算法PnNS。在PnNS算法中，每個并行計算節(jié)點只需維護局部滑動子窗口數(shù)據(jù)信息，而且并行計算節(jié)點之間不需要進行交互通信就可完成計算任務(wù)，結(jié)果輸出在下一級節(jié)點實現(xiàn)。實驗結(jié)果表明，當數(shù)據(jù)流工作負載較大時，相比于傳統(tǒng)單機集中式查詢算法，PnNS算法的查詢效率隨著并行度的增加接近于線性增長；當滑動窗口規(guī)模、數(shù)據(jù)維度等發(fā)生改變時， PnNS算法依然能夠

4、保持較好的并行查詢處理性能。
　　針對并行n-of-N Skyline查詢過程中由于并行計算節(jié)點性能的差異而引起的負載不均衡問題，提出了一種基于滑動窗口調(diào)整的動態(tài)負載均衡算法 LBA。該算法采用一種基于簇的子窗口劃分策略，并且通過劃分反饋模塊實時調(diào)整并行計算節(jié)點維護的子窗口大小，進而達到在并行計算節(jié)點之間調(diào)整負載的目的。實驗結(jié)果表明，LBA算法能夠有效改善并行計算節(jié)點之間的負載均衡性，使節(jié)點處理延遲標準偏差下降36％；當滑動窗口大

5、小、并行計算節(jié)點個數(shù)、數(shù)據(jù)維度發(fā)生改變時，LBA算法依然能夠使分布并行n-of-N Skyline查詢的并行計算節(jié)點間保持較好的負載均衡性。
　　針對并行n-of-N Skyline查詢過程中系統(tǒng)整體負載過大或過小所造成的查詢計算節(jié)點資源供應(yīng)不足或過剩問題，提出了一種彈性可擴展的并行查詢模型EPM，并基于該模型提出了一種彈性節(jié)點資源配置算法 ENPA。在 ENPA算法所采用的彈性協(xié)議中，將數(shù)據(jù)流工作負載抖動性以及計算節(jié)點自身處理延