數(shù)據(jù)流上Skyline查詢處理算法研究.pdf

1、數(shù)據(jù)流是連續(xù)、實時、有序的數(shù)據(jù)項序列。數(shù)據(jù)流廣泛存在于因特網(wǎng)與傳感器網(wǎng)絡、交通與環(huán)境監(jiān)控、工業(yè)控制、金融股市與電子商務交易等應用中。流數(shù)據(jù)挖掘與管理是近年來學術(shù)界和工業(yè)界所共同關(guān)注的問題。作為一種重要的數(shù)據(jù)挖掘技術(shù)，Skyline查詢是近年來的研究熱點。Skyline是定義在一個多維對象集上的集合，它由所有不被其它對象所支配的對象組成。Skyline對于數(shù)據(jù)挖掘可視化、用戶偏好查詢及多約束決策等問題具有重要意義。自從Skyline查詢在

2、學術(shù)界被提出以來，對該課題的研究迄今為止都非?；钴S。
　　 數(shù)據(jù)流的特點是數(shù)據(jù)實時到達、規(guī)模宏大、次序獨立以及數(shù)據(jù)往往只能一次讀取。這就要求Skyline查詢處理算法必需高效地處理數(shù)據(jù)流中到來的每一個對象，并且要求算法具有較低的時間復雜度。學術(shù)界已經(jīng)出現(xiàn)了一些有關(guān)該課題的研究成果，但這些成果僅涉及數(shù)據(jù)流上全空間Skyline的查詢處理，并且數(shù)據(jù)形式也僅限于集中式、確定性數(shù)據(jù)流。此外，現(xiàn)存算法沒有很好地解決求影響時間與淘汰被新來對

3、象所支配的對象這兩個關(guān)鍵問題，導致算法性能較低。本文在對現(xiàn)有技術(shù)之不足進行了徹底改進的基礎(chǔ)上，進一步解決了一些新的重要實際應用與需求。用戶對數(shù)據(jù)對象各屬性的關(guān)注往往是有差異的；實際應用中的數(shù)據(jù)流往往以分布式的形式出現(xiàn)，例如：金融股票交易、環(huán)境監(jiān)測以及網(wǎng)絡通訊等應用；最近兩年以來，一種全新的被稱為概率數(shù)據(jù)流的數(shù)據(jù)形態(tài)逐步引起了研究者們的關(guān)注，針對概率數(shù)據(jù)流的挖掘與分析方興未艾。這些新的應用需求為數(shù)據(jù)流上的Skyline查詢處理帶了新的挑戰(zhàn)

4、。本文對數(shù)據(jù)流上的Skyline查詢處理算法進行了系統(tǒng)地研究，主要成果概括為以下幾個方面：
　　 (1).提出了一個高效地處理滑動窗口上Skyline持續(xù)查詢的算法GridSky。對于數(shù)據(jù)流上的Skyline查詢處理，決定其性能的主要因素是計算新到達對象的影響時間以及淘汰被新到達對象所支配的對象這兩個關(guān)鍵過程的效率。對這兩個關(guān)鍵過程，現(xiàn)有工作中只是簡單地依靠R樹上的窗口查詢機制來實施，直接導致了算法性低下。GridSky算法采用

5、更適合數(shù)據(jù)流這種頻繁更新環(huán)境的基本網(wǎng)格作為索引結(jié)構(gòu)，并在此基礎(chǔ)上開發(fā)了基于時間戳的剪枝策略、基于網(wǎng)格的的剪枝策略以及分層遍歷策略等優(yōu)化措施，大幅度地提高了算法的性能。大量的對比實驗表明，在空間復雜度略低的情況下，GridSky與其競爭對手相比時間性能優(yōu)勢在1個數(shù)量級以上。此外，GridSky算法對不同的數(shù)據(jù)分布、數(shù)據(jù)規(guī)模與維度具有很強的可擴展性。
　　 (2).研究了分布式數(shù)據(jù)流上的Skyline查詢問題，提出了一個通信最優(yōu)的分

6、數(shù)據(jù)流上Skyline查詢處理算法研究布式算法BOCS。近年來隨著大規(guī)模分布式應用的涌現(xiàn)，分布式數(shù)據(jù)流上的查詢處理與數(shù)據(jù)挖掘越來越引起了研究者們的關(guān)注。此前相關(guān)工作局限于集中式數(shù)據(jù)流上的Skyline計算，沒有人考慮更具挑戰(zhàn)性的分布式數(shù)據(jù)流上的Skyline查詢問題。本文圍繞著降低系統(tǒng)反應延遲與最小化通信負荷的目標，在對GridSky進行重大適應性改造的基礎(chǔ)上，提出了一個兩階段漸進求解的分布式算法BOCS。并對BOCS的關(guān)鍵實現(xiàn)環(huán)節(jié)，如

7、：遠程站點與協(xié)調(diào)站點間的通信協(xié)議、Skyline增量的計算等進行了優(yōu)化，使算法達到了通信效率與反應延遲的合理均衡。理論分析證明在所有基于非共享策略的算法中，BOCS算法通信最優(yōu)。大量的對比實驗也表明，BOCS算法高效、穩(wěn)定且具有良好的可擴展性。
　　 (3).提出了一個高效地計算滑動窗口中任意子空間上Skyline的算法StreamSubsky。此前相關(guān)工作僅限于維護滑動窗口全空間上的Skyline，未涉及到子空間上Skylin

8、e的計算問題。而用戶的偏好與傾向性天然不同，這就催生了滑動窗口中子空間上的Skyline查詢問題的研究。本文首次提出并較好地解決了該問題，提出的StreamSubsky算法巧妙地利用了全空間與各子空間上Skyline之間的關(guān)系，采用自項向下的方式通過兩個階段增量地返回目標子空間上的計算結(jié)果。此外，算法還采用了多個優(yōu)化策略顯著地提高了計算效率。理論分析和實驗結(jié)果表明，與同類算法相比StreamSubsky以極少的時間開銷就能使查詢得到響應

9、，算法具有良好的時間與空間性能。
　　 (4).對概率數(shù)據(jù)流上的Skyline查詢問題進行了深入研究，提出了一個高效的解決方案。數(shù)據(jù)的內(nèi)在不確定性在信息集成、RFID以及傳感器網(wǎng)絡等普適計算環(huán)境中普遍存在。對概率數(shù)據(jù)流進行管理與分析近年來引起了研究者們的廣泛關(guān)注，而此前尚無解決概率數(shù)據(jù)流上Skyline持續(xù)查詢的算法出現(xiàn)。本文基于“可能世界”語義對該問題首次進行了建模，并提出了一個高效的查詢處理算法SOPDS。與傳統(tǒng)確定性數(shù)據(jù)流

10、上的Skyline查詢處理不同，SOPDS算法主要考慮以下兩個基本問題：一是如何高效地確定對象的身份(判斷其是否為Skyline對象)，即減少身份判斷過程中支配測試的次數(shù)以降低CPU開銷；二是在保證算法正確性的前提下盡可能早地淘汰那些不再有機會加入Skyline的對象，以減少內(nèi)存開銷。圍繞著以上兩個基本問題，本文先后提出了概率定界、逐步求精、提前淘汰與選擇補償?shù)葍?yōu)化措施對算法從時間與空間上進行了系統(tǒng)地優(yōu)化。理論分析與詳細的對比實驗表明，

11、SOPDS算法在時間與空間上具有較高的整體性能，算法高效、穩(wěn)定。
　　 本文研究了數(shù)據(jù)流上Skyline查詢的四個重要問題，并分別提出了有效的解決方案。本文提出GridSky算法對現(xiàn)有技術(shù)進行了徹底地改進，而提出的BOCS、StreamSubsky和SOPDS算法則進一步填補了一些重要新興應用的空白。理論分析證明這些算法高效地解決了相應的問題；大量的對于比實驗也表明，與現(xiàn)有技術(shù)相比本文提出的算法在存儲空間、查詢處理速度等方面具有