分布式環(huán)境下skyline查詢處理技術(shù)研究.pdf

1、Skyline查詢處理是數(shù)據(jù)庫(kù)技術(shù)領(lǐng)域的一個(gè)研究重點(diǎn)和熱點(diǎn),它在多目標(biāo)決策、數(shù)據(jù)挖掘和可視化、用戶偏好查詢等方面有著廣闊的應(yīng)用。Skyline查詢輸出數(shù)據(jù)集中不被其它任意數(shù)據(jù)點(diǎn)所支配的點(diǎn)所組成的集合,使得用戶可以在小規(guī)模的skyline結(jié)果集上選擇自己感興趣的對(duì)象,而不必關(guān)心那些被過(guò)濾掉的對(duì)象。隨著分布式網(wǎng)絡(luò)系統(tǒng)的深入應(yīng)用和云計(jì)算的發(fā)展,分布式的skyline查詢計(jì)算近年來(lái)受到廣泛關(guān)注。由于全局知識(shí)的缺乏和不同分布式環(huán)境的特殊要求,分布

2、式的skyline查詢面臨著巨大的挑戰(zhàn)。本文針對(duì)分布式環(huán)境下的skyline計(jì)算及其相關(guān)問(wèn)題進(jìn)行了深入的分析研究。本文的主要工作和創(chuàng)新點(diǎn)如下:
　　(1)研究了無(wú)線傳感器網(wǎng)絡(luò)中的連續(xù)skyline查詢問(wèn)題,提出了一種基于預(yù)測(cè)技術(shù)和數(shù)據(jù)映射的skyline查詢算法。Sink收集所有節(jié)點(diǎn)的預(yù)測(cè)誤差,用以預(yù)測(cè)值為中心、兩倍預(yù)測(cè)誤差為邊長(zhǎng)的超正方體來(lái)表示節(jié)點(diǎn)的真實(shí)感應(yīng)數(shù)據(jù)值,然后基于超正方體之間的支配關(guān)系進(jìn)行節(jié)點(diǎn)剪枝。節(jié)點(diǎn)上傳真實(shí)感應(yīng)值,

3、當(dāng)且僅當(dāng)節(jié)點(diǎn)收到sink發(fā)出的“上傳”消息。為了最大化預(yù)測(cè)獲益,提出了一種分段線性預(yù)測(cè)技術(shù),根據(jù)查詢結(jié)果自適應(yīng)地更新預(yù)測(cè)模型參數(shù)值。實(shí)驗(yàn)結(jié)果表明,該算法可以有效地減少傳感器網(wǎng)絡(luò)中執(zhí)行連續(xù)skyline查詢時(shí)的通信代價(jià)。
　　(2)研究了傳感器網(wǎng)絡(luò)中反相關(guān)或簇狀分布數(shù)據(jù)集下的過(guò)濾器設(shè)計(jì)問(wèn)題,提出了基于數(shù)據(jù)簇表示模式的針對(duì)性數(shù)據(jù)過(guò)濾算法?，F(xiàn)有過(guò)濾器算法普遍通過(guò)從數(shù)據(jù)集中選擇支配能力最強(qiáng)的數(shù)據(jù)點(diǎn)(或者相關(guān)數(shù)據(jù)值)作為過(guò)濾器,存在過(guò)濾效果

4、受限于數(shù)據(jù)分布的問(wèn)題。本算法為不同的節(jié)點(diǎn)設(shè)計(jì)不同的過(guò)濾器,來(lái)適應(yīng)不同的數(shù)據(jù)分布。為了降低過(guò)濾器計(jì)算代價(jià)和最大化過(guò)濾獲益,設(shè)計(jì)了一種新穎的數(shù)據(jù)簇表示模式和一種基于歷史查詢結(jié)果的抽樣技術(shù)。實(shí)驗(yàn)結(jié)果表明,該算法在正確返回查詢結(jié)果的同時(shí),減少了無(wú)線傳感器網(wǎng)絡(luò)中的過(guò)濾器計(jì)算代價(jià)和總的查詢通信能耗。
　　(3)研究了無(wú)線傳感器網(wǎng)絡(luò)中的連續(xù)反skyline查詢問(wèn)題,將前面提出的連續(xù)skyline查詢算法思想應(yīng)用到反skyline計(jì)算中。不同于s

5、kyline計(jì)算,反skyline查詢算子是不可分解的,即不能隨意刪除非結(jié)果數(shù)據(jù),否則容易導(dǎo)致誤報(bào)。為此,提出了擴(kuò)展半支配和擴(kuò)展全支配的概念,用來(lái)基于數(shù)據(jù)映射知識(shí)對(duì)產(chǎn)生反skyline數(shù)據(jù)集的節(jié)點(diǎn)、不產(chǎn)生結(jié)果集的節(jié)點(diǎn)和能立即刪除的節(jié)點(diǎn)進(jìn)行識(shí)別。對(duì)這些節(jié)點(diǎn)進(jìn)行分階段探測(cè),以減少需要上傳真實(shí)感應(yīng)數(shù)據(jù)的節(jié)點(diǎn)數(shù)目。實(shí)驗(yàn)結(jié)果表明,算法能輸出正確的結(jié)果集,且具有較好的能量有效性。
　　(4)探討了客戶端/服務(wù)器模型下的skyline查詢問(wèn)題,

6、提出了基于數(shù)據(jù)劃分技術(shù)的分布式skyline算法。該算法將每個(gè)服務(wù)器上的數(shù)據(jù)按照其和其它服務(wù)器數(shù)據(jù)的依賴關(guān)系劃分成若干數(shù)據(jù)區(qū)域,使得不相互依賴的數(shù)據(jù)域能夠并行地執(zhí)行查詢。這些不相互依賴的數(shù)據(jù)區(qū)域可以來(lái)自不同的服務(wù)器,也可以來(lái)自相同的服務(wù)器。同時(shí),基于數(shù)據(jù)區(qū)域之間的依賴關(guān)系,制定查詢計(jì)劃,既有利于選擇過(guò)濾效力強(qiáng)的數(shù)據(jù)作為過(guò)濾器,又使得算法能夠漸進(jìn)性地輸出查詢結(jié)果。并行式的查詢和過(guò)濾器技術(shù)有效地縮短了查詢時(shí)間。理論上證明了查詢計(jì)劃的最大跳數(shù)