連續(xù)K-支配SKYLINE查詢算法研究.pdf

1、近年來(lái)，skyline查詢?cè)诙嗄繕?biāo)決策、數(shù)據(jù)挖掘、數(shù)據(jù)庫(kù)可視化等方面得到廣泛應(yīng)用。然而在高維空間環(huán)境下，skyline查詢因?yàn)榉祷氐慕Y(jié)果集過(guò)大而不能提供有用的信息。因此，學(xué)術(shù)界提出了k-支配skyline查詢的概念。它通過(guò)弱化對(duì)“支配”的定義，使數(shù)據(jù)點(diǎn)間更容易產(chǎn)生支配關(guān)系，從而使結(jié)果集的大小保持在一個(gè)合適的范同內(nèi)。在靜態(tài)k-支配skyline查詢問(wèn)題上，現(xiàn)有算法要么存在建立索引開銷太大問(wèn)題；要么在高維空問(wèn)中存在過(guò)多重復(fù)計(jì)算問(wèn)題。而在連續(xù)

2、k-支配skyline查詢方面，現(xiàn)有算法中剪枝方式和分治策略都存在刪除數(shù)據(jù)點(diǎn)后維護(hù)困難的問(wèn)題。
　　 本文通過(guò)分析現(xiàn)有算法存在的缺點(diǎn)，結(jié)合k-支配skyline查詢的內(nèi)在特性，分別在靜態(tài)k-支配skyline查詢和連續(xù)k-支配skyline查詢這兩個(gè)方面提出了新的算法。本文的主要貢獻(xiàn)可以分為以下幾點(diǎn)：
　　 (1)提出了不支配關(guān)系的概念。兩個(gè)支配能力弱的數(shù)據(jù)點(diǎn)之間不容易發(fā)生支配關(guān)系；兩個(gè)支配能力強(qiáng)的數(shù)據(jù)點(diǎn)之間也不容易發(fā)生

3、支配關(guān)系。本文通過(guò)計(jì)算數(shù)據(jù)點(diǎn)的支配能力，然后使數(shù)據(jù)點(diǎn)只和有可能與自己互相支配的數(shù)據(jù)點(diǎn)進(jìn)行比較，避免與不可能產(chǎn)生支配關(guān)系的數(shù)據(jù)點(diǎn)進(jìn)行不必要的比較，從而節(jié)省了大量的計(jì)算時(shí)間。
　　 (2)針對(duì)建立索引和不建立索引兩類算法在進(jìn)行靜態(tài)k-支配skyline查詢上存在的問(wèn)題，本文提出了一種基于簡(jiǎn)化預(yù)排序的k-支配skyline查詢算法。該算法的核心思想是引入平均數(shù)據(jù)點(diǎn)，并通過(guò)與之比較把各個(gè)數(shù)據(jù)點(diǎn)按支配能力大小進(jìn)行分塊，之后根據(jù)支配能力值對(duì)

4、各分塊進(jìn)行排序。這樣的排序不儀大幅度降低了預(yù)排序的時(shí)間，而且也很大程度減少了數(shù)據(jù)點(diǎn)間無(wú)意義的比較。
　　 (3)提出了準(zhǔn)skyline點(diǎn)的概念。在連續(xù)k-支配skyline查詢問(wèn)題上，由于維護(hù)傳統(tǒng)skyline點(diǎn)需要很大的計(jì)算量，所以使用傳統(tǒng)skyline點(diǎn)來(lái)進(jìn)行剪枝并不是很好的策略。本文提出的準(zhǔn)skyline點(diǎn)的概念，準(zhǔn)skyline數(shù)據(jù)集比傳統(tǒng)skyline數(shù)據(jù)集更易于維護(hù)，并且其能發(fā)揮傳統(tǒng)skyline數(shù)據(jù)集所具有的剪枝效

5、果。因此引入準(zhǔn)skyline思想能夠很大提高k-支配skyline查詢效率。
　　 (4)提出了保留支配關(guān)系的方法。由于在連續(xù)k-支配skyline查詢問(wèn)題上，任何數(shù)據(jù)點(diǎn)的更新都有可能影響到數(shù)據(jù)集的k-支配skyline點(diǎn)。如果每次數(shù)據(jù)點(diǎn)更新都重新計(jì)算k-支配skyline點(diǎn)是效率低下的。本文通過(guò)保留數(shù)據(jù)點(diǎn)之間一些重要的支配關(guān)系，當(dāng)數(shù)據(jù)更新時(shí)能夠很快的找到需要喚醒的數(shù)據(jù)點(diǎn)，從而提高了算法的時(shí)間效率。
　　 最后，通過(guò)理論