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

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

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

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

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

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é)果表明，相對(duì)于已有方法，GDPS方法不僅能夠滿(mǎn)足用戶(hù)漸進(jìn)式的查詢(xún)需求、保證查詢(xún)結(jié)果的正確性，而且能夠顯著降低查詢(xún)所需的通信開(kāi)銷(xiāo)。
　　針對(duì)已有的Skyline查詢(xún)技術(shù)在分布式區(qū)間Skyline查詢(xún)建模和查詢(xún)效率方面不足的問(wèn)題

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

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

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

9、種流數(shù)據(jù)映射策略。集中式策略中各計(jì)算節(jié)點(diǎn)均維護(hù)著全局窗口，計(jì)算節(jié)點(diǎn)之間無(wú)需通信，適合于帶寬受限的處理環(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)，能夠通過(guò)強(qiáng)化流數(shù)據(jù)之間的支配關(guān)系來(lái)提高查詢(xún)效率，適合于高帶寬環(huán)境且無(wú)需完全

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

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

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

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