分布式環(huán)境下Skyline計(jì)算算法研究.pdf

1、一個(gè)多維數(shù)據(jù)庫(kù)上的skyline,是此數(shù)據(jù)庫(kù)上不被其它任何數(shù)據(jù)點(diǎn)支配的點(diǎn)所組成的集合。skyline計(jì)算以其在多目標(biāo)決策、數(shù)據(jù)挖掘、數(shù)據(jù)庫(kù)可視化等方面的廣闊應(yīng)用獲得了越來(lái)越多研究者的關(guān)注。本文以普通分布式數(shù)據(jù)庫(kù)和結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)為目標(biāo),對(duì)分布式環(huán)境下的skyline計(jì)算算法展開(kāi)了深入的研究。當(dāng)前,分布式數(shù)據(jù)庫(kù)上的skyline計(jì)算研究已經(jīng)取得了初步進(jìn)展,但已有的算法還遠(yuǎn)不能滿足分布式環(huán)境下skyline計(jì)算的要求,因?yàn)樗鼈冎辽偈芟抻谝韵氯?/p>

2、種情況中的一種:(1)假設(shè)數(shù)據(jù)是被垂直劃分的;(2)僅支持滿足某種特殊網(wǎng)絡(luò)要求的水平劃分的數(shù)據(jù)庫(kù);(3)專為具有較低計(jì)算能力的輕量移動(dòng)設(shè)備設(shè)計(jì)。因此,本文提出了一種全新的基于反饋的分布式skyline計(jì)算算法,它以一種嶄新的反饋機(jī)制為核心,采多輪計(jì)算模式,支持任意水平劃分的數(shù)據(jù)庫(kù)上的skyline計(jì)算。算法中傳遞的反饋信息能大量剪除非skyline的本地?cái)?shù)據(jù)點(diǎn),避免無(wú)用信息在網(wǎng)絡(luò)中的傳輸,因而很大程度減少了網(wǎng)絡(luò)帶寬的消耗量。算法能快速地

3、響應(yīng)用戶,并按用戶規(guī)定的順序逐漸返回計(jì)算結(jié)果,具有很好的用戶可適應(yīng)性和漸進(jìn)性。本文以在真實(shí)數(shù)據(jù)庫(kù)和合成數(shù)據(jù)庫(kù)上的大量實(shí)驗(yàn)衡量了算法的性能,證實(shí)了它是一個(gè)高效的分布式skyline計(jì)算算法。在此基礎(chǔ)上,本文還對(duì)對(duì)等網(wǎng)絡(luò)(P2P)上的skyline計(jì)算進(jìn)行了研究。對(duì)等網(wǎng)絡(luò)是分布式信息共享與搜索的一種重要平臺(tái),Chord作為對(duì)等網(wǎng)絡(luò)的代表性協(xié)議以其簡(jiǎn)單靈巧的設(shè)計(jì)和良好的性能備受關(guān)注。已有的對(duì)等網(wǎng)絡(luò)上的skyline計(jì)算算法或是專為子空間的sk