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

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

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

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

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

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

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