數(shù)據(jù)流上序敏感查詢處理關(guān)鍵技術(shù)研究.pdf

1、近年來(lái)，隨著網(wǎng)絡(luò)通信技術(shù)發(fā)展和應(yīng)用，在很多應(yīng)用處理領(lǐng)域出現(xiàn)了一種新新型數(shù)據(jù)模型----數(shù)據(jù)流。典型的數(shù)據(jù)流包括：網(wǎng)絡(luò)安全監(jiān)測(cè)、無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用環(huán)境中由傳感器傳回的各種監(jiān)測(cè)數(shù)據(jù)、股票交易所的股票價(jià)格信息、道路交通監(jiān)測(cè)系統(tǒng)的監(jiān)測(cè)數(shù)據(jù)、電信部門的通話記錄數(shù)據(jù)，以及網(wǎng)站的日志信息等。與傳統(tǒng)數(shù)據(jù)庫(kù)模型不同，數(shù)據(jù)流具有快速、實(shí)時(shí)、連續(xù)、無(wú)界等特點(diǎn)。由于在線處理系統(tǒng)的存儲(chǔ)容量不是無(wú)限擴(kuò)展的，無(wú)法保存全部數(shù)據(jù)流元組，因此數(shù)據(jù)流上的查詢處理算法應(yīng)該是單

2、遍掃描（one-pass）的。傳統(tǒng)數(shù)據(jù)庫(kù)上的查詢處理只能處理存儲(chǔ)在磁盤或內(nèi)存等介質(zhì)中的靜態(tài)數(shù)據(jù)，大多要做多遍掃描，空間復(fù)雜度和時(shí)間復(fù)雜度較高，不能直接應(yīng)用到數(shù)據(jù)流上。面對(duì)這些持續(xù)快速到達(dá)的海量數(shù)據(jù)流，如何利用有限的資源進(jìn)行高效的處理分析成為當(dāng)前研究的熱點(diǎn)。在海量數(shù)據(jù)流環(huán)境下，由于存儲(chǔ)和計(jì)算能力的限制，很難對(duì)所有的數(shù)據(jù)存儲(chǔ)處理。Top-k查詢和Skyline查詢能夠幫助用戶從海量數(shù)據(jù)集中返回對(duì)用戶價(jià)值最大的少量信息，成為數(shù)據(jù)庫(kù)領(lǐng)域最為重要

3、的查詢之一。Top-k查詢的目標(biāo)是根據(jù)用戶定義的排序函數(shù)找出評(píng)價(jià)值最高的k個(gè)對(duì)象集，而Skyline查詢是一種多目標(biāo)決策，是根據(jù)用戶在各個(gè)屬性上的偏好查找不被其它對(duì)象“支配”的對(duì)象集。由于top-k查詢和Skyline查詢都是關(guān)注含有排序信息的結(jié)果集，在本文中我們把top-k查詢和Skyline查詢統(tǒng)稱為序敏感查詢。
　　本研究主要內(nèi)容包括：⑴數(shù)據(jù)流上約束Skyline查詢技術(shù)研究。約束Skyline查詢(Constrained

4、Skyline queries)是常規(guī)Skyline的一個(gè)變種，結(jié)果集不再是全局的Skyline結(jié)果，而是在滿足用戶偏好要求的數(shù)據(jù)子集上的Skyline結(jié)果集，即由用戶在每個(gè)維度上定義取值約束，返回滿足用戶自定義約束集要求的結(jié)果集。約束Skyline查詢的意義在于能夠更細(xì)致的滿足用戶的需求。比如用戶在尋找一家價(jià)格便宜且距海濱近的飯店，對(duì)住宿的費(fèi)用有一定的要求，價(jià)格太低可能住宿條件不好，價(jià)格太高又超出預(yù)算。因此對(duì)飯店的價(jià)格有一個(gè)選擇區(qū)間，

5、這個(gè)區(qū)間可以稱為用戶在價(jià)格這個(gè)維度上定義的約束。本文對(duì)數(shù)據(jù)流上具有約束條件的Skyline查詢特點(diǎn)進(jìn)行了分析，針對(duì)約束Skyline的特點(diǎn)，提出兩個(gè)算法用于計(jì)算和維護(hù)Skyline集合。⑵數(shù)據(jù)流上動(dòng)態(tài)Skyline查詢技術(shù)研究。約束Skyline是動(dòng)態(tài)Skyline的一個(gè)特例，約束Skyline是在每維上定義約束，而動(dòng)態(tài)Skyline則要求計(jì)算在數(shù)據(jù)空間中與某元組最相近的數(shù)據(jù)集合。我們采用了網(wǎng)格索引存儲(chǔ)數(shù)據(jù)元組，通過(guò)為每個(gè)查詢定義影響區(qū)

6、域，使得在元組到達(dá)和失效時(shí)需要處理的元組個(gè)數(shù)最小化，提出了GBDS算法用于計(jì)算和維護(hù)動(dòng)態(tài)Skyline。⑶分布式數(shù)據(jù)流上的連續(xù) Skyline計(jì)算方法。數(shù)據(jù)流的本質(zhì)是分布的。在分布式數(shù)據(jù)流環(huán)境下，不僅要考慮中心節(jié)點(diǎn)和各個(gè)子節(jié)點(diǎn)上的計(jì)算效率，還要考慮中心節(jié)點(diǎn)和子節(jié)點(diǎn)間的通信開(kāi)銷。本文提出了一種高效的分布式數(shù)據(jù)流上的連續(xù)Skyline計(jì)算方法，在各節(jié)點(diǎn)上采用基于網(wǎng)格索引的Skyline提高計(jì)算效率，同時(shí)通過(guò)在各個(gè)子節(jié)點(diǎn)維護(hù)最有支配能力的k個(gè)

7、Skyline點(diǎn)，降低各節(jié)點(diǎn)間的通信開(kāi)銷。⑷一種數(shù)據(jù)流上的多 top-k查詢資源共享技術(shù)研究。研究了單數(shù)據(jù)流上的多個(gè) top-k查詢場(chǎng)景下的資源共享問(wèn)題，提出了一種資源共享策略 RS-Tpk，充分利用了top-k查詢本身的特點(diǎn)，通過(guò)在不同切片間進(jìn)行數(shù)據(jù)傳遞，提高切片間資源共享的范圍，降低了計(jì)算時(shí)間。⑸一種基于裁剪策略的高效數(shù)據(jù)流 top-k連續(xù)查詢方法。針對(duì)數(shù)據(jù)流存儲(chǔ)開(kāi)銷大問(wèn)題，我們采用了一種方法對(duì)數(shù)據(jù)元組進(jìn)行裁剪，僅保存未來(lái)可能成為t