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

1、Skyline計(jì)算，也稱輪廓查詢，本質(zhì)是一個(gè)多目標(biāo)優(yōu)化問題，目的旨在發(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年被提出以來，Skyline計(jì)算研究一直是數(shù)據(jù)庫和數(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、方式、存儲結(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)和動態(tài)數(shù)據(jù)、固定和移動對象、集中和分布式系統(tǒng)、低維和高維數(shù)據(jù)空間等不同環(huán)境。不過，隨著近年來云計(jì)算、傳感網(wǎng)、大數(shù)據(jù)、移動互聯(lián)等技術(shù)的飛速發(fā)展，新的應(yīng)用環(huán)境和需求不斷

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

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

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

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