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

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

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

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

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

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

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

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

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

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

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

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