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

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

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

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

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

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

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

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