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

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

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

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

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

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