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

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

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

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

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

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

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

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

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

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

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

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

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

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