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

1、近年來，skyline查詢在多目標決策、數(shù)據(jù)挖掘、數(shù)據(jù)庫可視化等方面得到廣泛應用。然而在高維空間環(huán)境下，skyline查詢因為返回的結果集過大而不能提供有用的信息。因此，學術界提出了k-支配skyline查詢的概念。它通過弱化對“支配”的定義，使數(shù)據(jù)點間更容易產(chǎn)生支配關系，從而使結果集的大小保持在一個合適的范同內。在靜態(tài)k-支配skyline查詢問題上，現(xiàn)有算法要么存在建立索引開銷太大問題；要么在高維空問中存在過多重復計算問題。而在連續(xù)

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

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

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

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