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

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

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

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

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

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