不確定數(shù)據(jù)的分布并行Skyline查詢技術研究.pdf

1、不確定數(shù)據(jù)作為一種特殊的數(shù)據(jù)類型，廣泛存在于諸如傳感器網(wǎng)絡、RFID網(wǎng)絡、金融數(shù)據(jù)分析、基于位置的服務以及移動對象管理等各種實際應用中。不確定數(shù)據(jù)的Skyline查詢在信息檢索、數(shù)據(jù)挖掘、決策制定和環(huán)境監(jiān)控等眾多應用中發(fā)揮著重要作用，目前已成為數(shù)據(jù)庫領域的一個研究熱點。隨著分布式不確定性應用的廣泛存在和普及，當前不確定數(shù)據(jù)的Skyline查詢應用已逐步向分布式應用拓展。對于廣泛分布的不確定數(shù)據(jù)集上的Skyline查詢，當前研究的挑戰(zhàn)在于

2、探索優(yōu)化分布式查詢處理的剪枝策略，高效漸進地返回查詢結果，以提高分布式不確定Skyline查詢處理的效率。隨著近年來不確定數(shù)據(jù)流應用的興起和發(fā)展，使得高效處理不確定數(shù)據(jù)流的Skyline查詢成為當前亟待解決的問題。由于不確定流數(shù)據(jù)源源不斷地高速到達且用戶關注的滑動窗口逐漸增大，導致已有的集中式不確定數(shù)據(jù)流Skyline查詢方法難以滿足數(shù)據(jù)流應用對查詢效率的需求。當前諸如數(shù)據(jù)中心等分布式計算環(huán)境的興起和廣泛運用，為實現(xiàn)不確定數(shù)據(jù)流的分布并

3、行 Skyline查詢處理提供了有利條件。對于高速到達的不確定數(shù)據(jù)流上的Skyline查詢，當前研究的挑戰(zhàn)在于如何充分利用分布式計算環(huán)境實現(xiàn)并行查詢處理，以提高不確定數(shù)據(jù)流 Skyline查詢處理的效率。以上研究挑戰(zhàn)表明，不確定數(shù)據(jù)的分布并行Skyline查詢技術研究具有極其重要的現(xiàn)實意義，且已成為當前Skyline查詢技術研究的必然趨勢。本文圍繞上述研究挑戰(zhàn)，分別針對不確定數(shù)據(jù)集和不確定數(shù)據(jù)流開展分布并行Skyline查詢技術的研究工

4、作。
　　針對已有的分布式概率Skyline查詢方法因剪枝效率不高而導致查詢的通信開銷較大的問題，提出了一種基于網(wǎng)格過濾的分布式概率Skyline查詢方法GDPS。GDPS查詢處理過程包括基于網(wǎng)格概要剪枝的預處理階段和基于迭代剪枝的處理階段。在預處理階段，對數(shù)據(jù)空間進行網(wǎng)格劃分并收集全局網(wǎng)格概要信息，利用該信息提前過濾大部分不可能成為最終結果的對象。在迭代剪枝處理階段，一方面，協(xié)調節(jié)點充分利用歷史處理信息最大化地過濾候選對象，并選

5、擇具有最大支配能力的候選元組傳輸至各局部節(jié)點；另一方面，各局部節(jié)點不斷更新元組的臨時Skyline概率并基于此剪枝局部節(jié)點內的候選元組，同時選擇該概率值最大的元組傳輸至協(xié)調節(jié)點，以增強候選元組的剪枝能力。實驗結果表明，相對于已有方法，GDPS方法不僅能夠滿足用戶漸進式的查詢需求、保證查詢結果的正確性，而且能夠顯著降低查詢所需的通信開銷。
　　針對已有的Skyline查詢技術在分布式區(qū)間Skyline查詢建模和查詢效率方面不足的問題

6、，提出了一種基于迭代反饋的分布式區(qū)間 Skyline查詢方法 DISQ。在DISQ方法中，首先對區(qū)間 Skyline查詢問題進行有效建模，并采用一種四階段的迭代反饋機制執(zhí)行查詢處理。對于各局部節(jié)點，根據(jù)協(xié)調節(jié)點的反饋信息不斷更新元組的臨時區(qū)間Skyline概率，并快速剪枝該概率值低于閾值的元組；選擇最具代表性的元組及其概率信息發(fā)送至協(xié)調節(jié)點，以優(yōu)化反饋對象的剪枝效率；選擇最優(yōu)的返回元組數(shù)目，以進一步降低查詢的通信開銷。對于協(xié)調節(jié)點，一方

7、面不斷收集并遴選來自各局部節(jié)點的優(yōu)勢元組，以最大化反饋元組的剪枝效率；一方面利用歷史信息剪枝候選反饋元組，以優(yōu)化反饋對象的選擇和減少反饋元組的數(shù)目。實驗結果表明，相對于已有方法，DISQ不僅能夠有效建模分布式區(qū)間Skyline查詢問題，滿足查詢的正確性和漸進性，而且能夠極大地減少查詢的通信開銷。
　　針對已有的分布并行處理模型(如 MapReduce)由于其自身結構的原因而難以支持不確定數(shù)據(jù)流的并行Skyline查詢的問題，提出了

8、一種基于窗口劃分的分布并行查詢模型WPS。在WPS模型中，在邏輯上將全局滑動窗口劃分為多個局部窗口，并將各局部窗口中的查詢任務映射至各計算節(jié)點，以實現(xiàn)并行查詢處理；基于排隊理論建模分析流數(shù)據(jù)的到達速率、處理速率和緩存容量之間的關系，自適應地調整窗口滑動的粒度；根據(jù)滑動窗口的綜合處理能力劃分各局部窗口長度，以優(yōu)化各計算節(jié)點上的負載均衡性能。特別地，為了適應各種分布式計算環(huán)境和并行查詢需求，WPS模型中實現(xiàn)了集中式、輪轉式、分布式和角劃分四

9、種流數(shù)據(jù)映射策略。集中式策略中各計算節(jié)點均維護著全局窗口，計算節(jié)點之間無需通信，適合于帶寬受限的處理環(huán)境；輪轉式策略以輪轉的方式依次按序更新完各計算節(jié)點上的局部窗口，能夠降低各局部窗口的動態(tài)變化性且適合高帶寬網(wǎng)絡環(huán)境；分布式策略逐個交替地將流數(shù)據(jù)按序映射至各計算節(jié)點，能夠最大化并行處理的效率且具有較好的負載均衡性；角劃分策略根據(jù)流數(shù)據(jù)的角坐標確定其映射的計算節(jié)點，能夠通過強化流數(shù)據(jù)之間的支配關系來提高查詢效率，適合于高帶寬環(huán)境且無需完全

10、負載均衡的查詢應用。實驗結果表明，與已有方法相比，基于WPS模型實現(xiàn)的分布并行Skyline查詢方法的處理效率顯著提高，且對于不同的更新粒度、數(shù)據(jù)維度和窗口長度，能夠維持較好的查詢處理和負載均衡性能。
　　針對已有的不確定數(shù)據(jù)流Skyline查詢方法難以解決高吞吐率數(shù)據(jù)流環(huán)境下對大規(guī)?；瑒哟翱谶M行高效Skyline查詢的問題，提出了一種基于兩級優(yōu)化的分布并行Skyline查詢方法PSS。在PSS方法中，利用基于窗口劃分的WPS模型

11、實現(xiàn)基本的分布并行查詢處理框架，并利用計算節(jié)點之間以及計算節(jié)點內部的兩級優(yōu)化處理來實現(xiàn)高效的并行查詢處理。在計算節(jié)點之間，利用新到達流數(shù)據(jù)的映射策略對計算節(jié)點進行有效組織，并對其各自維護的局部窗口中的元組建立支配關系，以減少各計算節(jié)點所維護的元組之間的支配測試次數(shù)。在計算節(jié)點內部，采用網(wǎng)格索引結構優(yōu)化其內部計算，包括元組之間的支配測試、候選對象的Skyline概率計算與更新等；采用一種基于Z-order曲線的管理策略對大量網(wǎng)格元胞的進行

12、高效管理，并利用Z-order列表的單調性優(yōu)化網(wǎng)格元胞之間的支配關系測試。實驗結果表明，相對于已有方法，PSS方法能夠極大地改進并行查詢處理的效率，同時其所消耗的通信開銷較小且具有較好的負載均衡性能。
　　針對在不確定數(shù)據(jù)流的分布并行Skyline查詢過程中由于故障發(fā)生而導致查詢結果不準確和查詢中斷的問題，提出了一種基于復制的容錯分布并行Skyline查詢方法FTPS。在FTPS方法中，一方面采用了基于WPS模型和兩級優(yōu)化策略實現(xiàn)

13、的分布并行查詢處理框架，以實現(xiàn)不確定數(shù)據(jù)流上Skyline查詢的高效并行查詢處理；一方面將各種基于復制的容錯優(yōu)化策略與并行查詢處理框架有效結合，以實現(xiàn)高效的容錯并行查詢處理。在FTPS中選擇參與并行處理的計算節(jié)點作為副本節(jié)點，并對各計算節(jié)點上的多個副本進行層次化管理，通過選擇優(yōu)先級高的副本恢復數(shù)據(jù)，以保證數(shù)據(jù)恢復的高效性；同時將故障檢測、丟失數(shù)據(jù)恢復和查詢過程恢復貫穿于整個查詢更新過程中，以減少容錯處理的額外通信和計算開銷并實現(xiàn)快速的容