基于索引的k-支配skyline算法研究.pdf

1、Skyline查詢是近年來數(shù)據(jù)庫和數(shù)據(jù)挖掘領(lǐng)域的一個(gè)研究熱點(diǎn)。給定兩個(gè)d維的數(shù)據(jù)點(diǎn)p和g，如果點(diǎn)p在所有維上的取值都不比點(diǎn)q差，并且在至少一個(gè)維上取值比g好，則稱點(diǎn)p支配點(diǎn)g。一個(gè)數(shù)據(jù)集的skyline定義為該數(shù)據(jù)集上不被任意其它點(diǎn)所支配的數(shù)據(jù)點(diǎn)集合。Skyline查詢在多標(biāo)準(zhǔn)決策的應(yīng)用中具有重要意義。 隨著數(shù)據(jù)集維數(shù)的增加，數(shù)據(jù)點(diǎn)之間形成支配關(guān)系的可能性越來越小，導(dǎo)致了skyline數(shù)據(jù)集變得過大而無法提供任何有效信息。為了在

2、高維數(shù)據(jù)集中找到更重要和更有意義的skyline點(diǎn)，有學(xué)者提出k-支配skyline的概念。由于k-支配skyline的特殊性質(zhì)，傳統(tǒng)的skyline算法不能適用于k-支配skyline查詢，而現(xiàn)有的k-支配skyline算法在時(shí)間效率、空間復(fù)雜度和漸進(jìn)輸出性上都存在不足。 根據(jù)傳統(tǒng)skyline的預(yù)排序過濾算法的思想，本文提出了一種基于索引的高效k-支配skyline算法，在時(shí)間效率、漸進(jìn)輸出性和空間復(fù)雜度三個(gè)方面部比現(xiàn)有算法