多環(huán)境下Skyline計(jì)算問(wèn)題研究.pdf

1、Skyline計(jì)算，也稱輪廓查詢，本質(zhì)是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，目的旨在發(fā)現(xiàn)給定數(shù)據(jù)集中所有用戶可能感興趣的信息。作為一種基礎(chǔ)的數(shù)據(jù)操作方法，Skyline計(jì)算在多目標(biāo)決策支持系統(tǒng)、導(dǎo)航系統(tǒng)、環(huán)境監(jiān)控、數(shù)據(jù)挖掘等領(lǐng)域有著廣泛的應(yīng)用。因此，自2001年被提出以來(lái)，Skyline計(jì)算研究一直是數(shù)據(jù)庫(kù)和數(shù)據(jù)挖掘領(lǐng)域許多研究者關(guān)注的焦點(diǎn)。
　　Skyline查詢算法的設(shè)計(jì)主要受三個(gè)因素影響:數(shù)據(jù)特征、運(yùn)行環(huán)境和設(shè)計(jì)目標(biāo)。數(shù)據(jù)特征包含數(shù)據(jù)的生成

2、方式、存儲(chǔ)結(jié)構(gòu)、空間維度及規(guī)模等信息。運(yùn)行環(huán)境指執(zhí)行查詢操作的計(jì)算和網(wǎng)絡(luò)環(huán)境，分集中式和分布式兩種。設(shè)計(jì)目標(biāo)則包括執(zhí)行效率、漸進(jìn)性、公平性、友好性等指標(biāo)。三種因素的交織造成了Skyline計(jì)算環(huán)境的復(fù)雜多樣性。
　　目前，已有多種Skyline算法被相繼提出，涵蓋了靜態(tài)和動(dòng)態(tài)數(shù)據(jù)、固定和移動(dòng)對(duì)象、集中和分布式系統(tǒng)、低維和高維數(shù)據(jù)空間等不同環(huán)境。不過(guò)，隨著近年來(lái)云計(jì)算、傳感網(wǎng)、大數(shù)據(jù)、移動(dòng)互聯(lián)等技術(shù)的飛速發(fā)展，新的應(yīng)用環(huán)境和需求不斷

3、涌現(xiàn)，同時(shí)也對(duì)以往相對(duì)成熟的環(huán)境帶來(lái)了影響。面對(duì)這種情況，現(xiàn)有算法已難以適應(yīng)發(fā)展的需要。
　　本文針對(duì)多種環(huán)境下的Skyline計(jì)算問(wèn)題進(jìn)行了研究與探索，主要研究點(diǎn)包括:集中式靜態(tài)數(shù)據(jù)集下算法效率的提升問(wèn)題;移動(dòng)環(huán)境中基于位置依賴的連續(xù)查詢問(wèn)題;分布式架構(gòu)下的Skyline計(jì)算問(wèn)題和集中式靜態(tài)數(shù)據(jù)集上的反Skyline查詢問(wèn)題。主要貢獻(xiàn)如下:
　　(1)在集中式靜態(tài)數(shù)據(jù)集環(huán)境下，為提升大規(guī)模、高維數(shù)據(jù)集的Skyline計(jì)算效

4、率，從算法自身和計(jì)算平臺(tái)等方面考慮，提出了兩種基于多核并行技術(shù)的Skyline算法。第一種算法采用預(yù)排序策略，將數(shù)據(jù)集按照任意指定維度排序，然后劃分為多個(gè)子集進(jìn)行并行化處理。第二種算法在第一種算法的基礎(chǔ)上，首先改進(jìn)了預(yù)排序策略，然后通過(guò)選擇樞軸點(diǎn)，將數(shù)據(jù)空間劃分為若干區(qū)域，利用區(qū)域支配關(guān)系，減少數(shù)據(jù)對(duì)象之間的支配測(cè)試次數(shù)，進(jìn)一步提高了效率。兩種算法處理過(guò)程簡(jiǎn)潔，具有較好的漸進(jìn)性、用戶友好型和可擴(kuò)展性。實(shí)驗(yàn)結(jié)果表明，對(duì)于規(guī)模較大、維數(shù)較高

5、的數(shù)據(jù)集，計(jì)算效率有較大提升。
　　(2)在移動(dòng)環(huán)境下，針對(duì)查詢點(diǎn)快速移動(dòng)時(shí)連續(xù)、高效輸出指定搜索區(qū)域Skyline集合的問(wèn)題，結(jié)合數(shù)據(jù)流技術(shù)，提出一種基于位置依賴的連續(xù)查詢算法。首先使用R-樹(shù)快速更新查詢數(shù)據(jù)，然后利用兩次連續(xù)計(jì)算時(shí)搜索區(qū)域的重疊性構(gòu)造被動(dòng)數(shù)據(jù)流，并對(duì)新增和失效數(shù)據(jù)分別進(jìn)行處理，最終連續(xù)輸出Skyline集合。由于充分利用了已有計(jì)算結(jié)果，算法計(jì)算量有大幅下降。實(shí)驗(yàn)結(jié)果表明，該算法特別適合計(jì)算頻度要求較高的場(chǎng)合，與

6、基于網(wǎng)格索引的算法相比，時(shí)間效率隨著數(shù)據(jù)集規(guī)模的增大提升明顯。
　　(3)在分布式環(huán)境下，針對(duì)層次化拓?fù)浣Y(jié)構(gòu)對(duì)等網(wǎng)，研究了分布式數(shù)據(jù)流環(huán)境下的Skyline計(jì)算問(wèn)題，提出了一種由下往上分層匯聚結(jié)果的算法。對(duì)下層網(wǎng)絡(luò)，通過(guò)構(gòu)造路由樹(shù)重建了的路由結(jié)構(gòu)，保證在每一跳均能對(duì)傳輸?shù)臄?shù)據(jù)進(jìn)行有效過(guò)濾，降低了計(jì)算和通信開(kāi)銷;對(duì)上層網(wǎng)絡(luò)，采用保序映射的方式將多維數(shù)據(jù)轉(zhuǎn)換到一維空間并排序，然后依據(jù)上層網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)識(shí)符的大小順序計(jì)算，保證了算法的漸進(jìn)性