反skyline查詢及變體處理研究.pdf

1、Skyline查詢處理技術是近年來數(shù)據(jù)庫領域中的一個研究重點與熱點。傳統(tǒng)的skyline查詢從用戶的角度進行查詢，返回所有不被別的數(shù)據(jù)對象支配(dominate)的數(shù)據(jù)對象集。然而，反skyline查詢從決策者的角度進行查詢，返回一個給定數(shù)據(jù)集的子集，且該子集中每個對象的動態(tài)skyline都包含一個預先給定的查詢點。由于反skyline查詢在市場決策、環(huán)境監(jiān)測、投資等領域有著重要的應用價值，近幾年來受到了許多學者的重視。當前，最好的反s

2、kyline查詢處理方法是RSSA算法。盡管RSSA算法有其優(yōu)點（如可應用于任意數(shù)據(jù)分布和維度等），但它在查詢過程中需要重復遍歷R樹索引結構，導致了大量冗余的I/O和CPU時間。另外，在實際應用中，傳統(tǒng)的反skyline查詢也可能無法滿足一些需求。這些新的應用需求為傳統(tǒng)的反skyline查詢處理帶了新的挑戰(zhàn)。
　　 鑒于此，本文著重研究了反skyline查詢及變體處理技術，主要包括如下四個方面:
　　 1.利用重用技術和

3、新穎的剪枝策略，提出了若干高效的反skyline查詢算法。
　　 2.首次引入了反k-skyband查詢，并給出其形式化定義及特性;提出了一系列有效的反k-skyband查詢算法。
　　 3.首次引入了受限反skyline查詢，并給出其形式化定義及特性;提出了若干有效的受限反skyline查詢算法。
　　 4.分析了本文提出的所有算法的正確性和時間復雜度，并在真實與合成數(shù)據(jù)集上通過大量的實驗評價其性能。