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

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

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

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