數據流上序敏感查詢處理關鍵技術研究.pdf

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

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

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

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

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

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

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