高維數(shù)據(jù)集SKYLINE計(jì)算研究.pdf

1、隨著Skyline查詢?cè)诙鄻?biāo)準(zhǔn)決策、數(shù)據(jù)挖掘、用戶偏好查詢、數(shù)據(jù)庫(kù)可視化等領(lǐng)域的廣泛應(yīng)用，國(guó)內(nèi)外學(xué)者已經(jīng)提出了多種Skyline算法，但由于Skyline查詢方面的研究發(fā)展時(shí)間尚短，目前對(duì)于高維數(shù)據(jù)的Skyline計(jì)算研究還很有限。高維Skyline計(jì)算面臨以下挑戰(zhàn)：（1）維度災(zāi)難——即隨著數(shù)據(jù)集規(guī)模增大維數(shù)增多，Skyline查詢的結(jié)果數(shù)目將隨數(shù)據(jù)集大?。∟）和維數(shù)（D）呈指數(shù)增長(zhǎng)。得到的Skyline查詢結(jié)果集巨大，不能提供有效信息

2、。（2）計(jì)算代價(jià)高——Skyline算法的開(kāi)銷本來(lái)就比較大，其中BNL，SFS和LESS算法最壞情況復(fù)雜度均達(dá)到了O（kn2）， k是查詢空間的維數(shù)，n是數(shù)據(jù)對(duì)象個(gè)數(shù)。（3）算法要求高——算法不僅需要正確得出Skyline結(jié)果，還應(yīng)具有漸進(jìn)性（progressive）和偏好性（preferable），即算法獲得Skyline點(diǎn)的響應(yīng)時(shí)間快，并且能根據(jù)用戶對(duì)不同屬性的喜好程度給出相應(yīng)Skyline結(jié)果。 本文集中研究了高維數(shù)據(jù)集的

3、Skyline算法和查詢數(shù)據(jù)集Skyline點(diǎn)輸出數(shù)目過(guò)多的問(wèn)題。深入分析了高維空間Skyline計(jì)算的特點(diǎn)及難點(diǎn)，在此基礎(chǔ)上提出了一種基于排序的高維數(shù)據(jù)集Skyline算法。算法采用一種新穎的預(yù)排序結(jié)構(gòu)，并結(jié)合已有算法的優(yōu)點(diǎn)，能夠較好地達(dá)到算法要求。與現(xiàn)有同類算法相比，具有以下優(yōu)點(diǎn)：（1）可以根據(jù)用戶的需求，順序輸出結(jié)果，減少用戶后期篩選數(shù)據(jù)點(diǎn)的計(jì)算量。（2）根據(jù)預(yù)處理結(jié)構(gòu)的特點(diǎn)，可以保證優(yōu)先掃描較好的點(diǎn)，能夠快速漸進(jìn)地返回Skyli

4、ne結(jié)果。（3）采用優(yōu)化啟發(fā)式規(guī)則減少訪問(wèn)的數(shù)據(jù)點(diǎn)數(shù)目，無(wú)需訪問(wèn)整個(gè)數(shù)據(jù)集就能得到Skyline集。理論分析和實(shí)驗(yàn)結(jié)果表明，本文的算法有很好的漸進(jìn)性，有效地改善了查詢的性能。另外，針對(duì)輸出結(jié)果過(guò)多的情況，集中研究了Skyline集的優(yōu)選策略，從定義和算法的局限性兩個(gè)方面分析比較了k支配，Skyline頻率概念和抽樣算法，引入維度權(quán)重和Skyline相關(guān)度的概念，進(jìn)一步改進(jìn)了本文提出的算法，精簡(jiǎn)了Skyline結(jié)果，提高了用戶友好度，使S