分布式數(shù)據(jù)流查詢處理若干關(guān)鍵技術(shù)的研究.pdf

1、隨著大規(guī)模網(wǎng)絡(luò)的發(fā)展和Web的廣泛應(yīng)用，在網(wǎng)絡(luò)監(jiān)控、入侵檢測、傳感器網(wǎng)絡(luò)、通訊數(shù)據(jù)管理、股票分析等應(yīng)用領(lǐng)域中產(chǎn)生了一種新型數(shù)據(jù)—數(shù)據(jù)流(或流數(shù)據(jù))，如關(guān)系元組、傳感器讀入值、網(wǎng)絡(luò)性能參數(shù)、電話記錄和股票交易數(shù)據(jù)等。與傳統(tǒng)數(shù)據(jù)庫應(yīng)用模型不同，數(shù)據(jù)流模型具有以下特點：(1)數(shù)據(jù)連續(xù)、實時到達；(2)數(shù)據(jù)量大、無限制并且難以預(yù)測；(3)數(shù)據(jù)一經(jīng)處理，除非特意保存，否則不能被再次取出處理，即一次性處理(one—pass)，或者再次提取數(shù)據(jù)的代價

2、昂貴。如何對這些流數(shù)據(jù)進行存儲、查詢處理已經(jīng)成為當(dāng)前國際數(shù)據(jù)庫研究領(lǐng)域的熱點問題。 在許多實際應(yīng)用中，如決策支持系統(tǒng)、查詢優(yōu)化等，用戶并不需要獲得確切值，而只需要一個近似值。因此，數(shù)據(jù)流分析和管理的核心是設(shè)計一次掃描算法，即在一個遠小于數(shù)據(jù)規(guī)模的內(nèi)存空間里不斷更新一個代表數(shù)據(jù)集的結(jié)構(gòu)—概要數(shù)據(jù)結(jié)構(gòu)，使得在任何時候都能夠根據(jù)這個結(jié)構(gòu)快速實時地獲得近似查詢結(jié)果。如果流的長度為N，則概要數(shù)據(jù)結(jié)構(gòu)的規(guī)模大小不超過0(polylog(N)

3、)，并且處理流上每一組數(shù)據(jù)的時間不超過0(polylog(N))。 傳統(tǒng)數(shù)據(jù)庫中的查詢主要是一次查詢，即系統(tǒng)根據(jù)當(dāng)前數(shù)據(jù)集合的快照給出查詢結(jié)果，并將該結(jié)果返回給用戶。而數(shù)據(jù)流的查詢?yōu)檫B續(xù)查詢，即查詢隨著新數(shù)據(jù)的到來而不斷的返回查詢結(jié)果。連續(xù)查詢是數(shù)據(jù)流上特有的操作，具有長期運行的特點。由于數(shù)據(jù)流環(huán)境中的數(shù)據(jù)集不是靜態(tài)的，而是不斷有數(shù)據(jù)插入和更新。用戶需要的也不是在某個時刻的靜態(tài)查詢結(jié)果，而是對整個數(shù)據(jù)流的一個動態(tài)監(jiān)測，隨著數(shù)據(jù)流

4、的不斷變化持續(xù)地產(chǎn)生查詢結(jié)果。 現(xiàn)有的數(shù)據(jù)流的研究主要為集中式的流數(shù)據(jù)系統(tǒng)，而數(shù)據(jù)流的本質(zhì)是分布式的，越來越多如傳感器網(wǎng)絡(luò)、數(shù)據(jù)通訊、Internet流量分析和Web日志等的大量數(shù)據(jù)都來自不同的遠程數(shù)據(jù)源，因此，需要構(gòu)建分布式數(shù)據(jù)流查詢處理的中間件以支持上述各種應(yīng)用。 P2P技術(shù)利用互聯(lián)網(wǎng)的終端機來建立一個龐大的分布式計算網(wǎng)絡(luò)，并對迅速涌出的大量信息進行處理。這些計算機(即對等點)在網(wǎng)絡(luò)中處于同等的地位，各自擁有獨立的

5、網(wǎng)絡(luò)自主權(quán)，以解決把所有的計算壓力全部加在服務(wù)器一端所造成的瓶頸問題。P2P以其可擴展性、通信負載平衡，資源的高利用率以及由基于內(nèi)容的路由機制所提供的動態(tài)變化的適應(yīng)性等特性成為構(gòu)建中間件的良好平臺，以便在減少網(wǎng)絡(luò)帶寬和網(wǎng)絡(luò)連接所消耗的計算資源情況下，提供快速有效的數(shù)據(jù)流查詢處理的實時響應(yīng)。 本論文以分布式數(shù)據(jù)流為主要研究對象，分析了國內(nèi)外的研究現(xiàn)狀，從目前存在的問題和不足出發(fā)，研究數(shù)據(jù)流基于時間變化的特性，監(jiān)測當(dāng)前流入的數(shù)據(jù)，探

6、索數(shù)據(jù)流變化的表示與建模方法，分析數(shù)據(jù)進化和變化的趨勢，并對未來流入的數(shù)據(jù)進行預(yù)測。在大規(guī)模分布式環(huán)境中，研究時間和空間復(fù)雜度最小的分布式數(shù)據(jù)流查詢處理和挖掘算法。一方面，研究小波分解技術(shù)，利用小波系數(shù)的近似處理方法構(gòu)建和維護小波直方圖，以獲得好的精確度，并且將其擴展到多維直方圖的構(gòu)建和維護，解決傳統(tǒng)的直方圖技術(shù)難以解決的問題，并利用小波系數(shù)構(gòu)造數(shù)據(jù)流集的概要，建立一個復(fù)合索引結(jié)構(gòu)來響應(yīng)各種查詢；還研究小波多分辨分析思想，構(gòu)造一種小波神

7、經(jīng)網(wǎng)絡(luò)模型，解決了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)中隱層節(jié)點數(shù)難以確定的問題，初步建立分布式時間序列數(shù)據(jù)流的預(yù)測模型。另一方面，運用草圖技術(shù)解決在數(shù)據(jù)流上的聚集查詢等難點問題。研究分布式數(shù)據(jù)流中頻繁項的發(fā)現(xiàn)算法，通過設(shè)置精確梯度來減少通信開銷，實現(xiàn)數(shù)據(jù)流查詢的實時響應(yīng)。同時，以P2P環(huán)境的Chord網(wǎng)絡(luò)結(jié)構(gòu)和協(xié)議為平臺，研究分布式數(shù)據(jù)流挖掘和及時響應(yīng)查詢處理的中間件，探索在對等計算系統(tǒng)中提供流數(shù)據(jù)的近似查詢功能所涉及到的數(shù)據(jù)和查詢路由、定位與查找、索引及數(shù)

8、據(jù)流概要的映射等關(guān)鍵技術(shù)問題。具體來說，本論文的主要創(chuàng)新點在于以下四個方面： (1)研究了基于小波技術(shù)的分布式數(shù)據(jù)流的查詢處理算法。首先通過離散小波變換理論與DWT分解哈爾小波方法獲得小波系數(shù)，然后分析了數(shù)據(jù)流的計算模型，形式化了數(shù)據(jù)流的查詢模型。在此基礎(chǔ)上，提出了一種新的方法來構(gòu)造數(shù)據(jù)流集的概要，建立一種復(fù)合索引結(jié)構(gòu)來處理內(nèi)積查詢和相似查詢。此外，還結(jié)合小波神經(jīng)網(wǎng)絡(luò)WNN良好的時頻局部化性質(zhì)以及神經(jīng)網(wǎng)絡(luò)的自學(xué)習(xí)功能，初步建立適

9、應(yīng)于時間序列數(shù)據(jù)流的預(yù)測模型。 (2)研究了基于草圖技術(shù)的分布式數(shù)據(jù)流的聚集查詢算法。首先分析了基于草圖的近似處理算法，然后利用隨機技術(shù)，在數(shù)據(jù)流到達時實時計算數(shù)據(jù)的偽草圖概要。在此基礎(chǔ)上，提出新穎的草圖分割技術(shù)，通過屬性值域的智能分割來減小分割后的自聯(lián)接規(guī)模以及為每個分割的獨立草圖公平地分配存儲空間兩個方面來保證近似估算質(zhì)量。 (3)研究了大規(guī)模分布式數(shù)據(jù)流中頻繁項的發(fā)現(xiàn)算法。通過對單個數(shù)據(jù)流頻繁項的發(fā)現(xiàn)算法的分析，形

10、式化地定義了基于時間點的分布式數(shù)據(jù)流頻繁項的發(fā)現(xiàn)問題。并提出了基于Lossy Counting算法的、分布式的合并算法DMA(Distributed Merging Algotithm)的一種分層結(jié)構(gòu)來發(fā)現(xiàn)從葉子結(jié)點直至根結(jié)點的概要結(jié)構(gòu)，并通過設(shè)置精確梯度使網(wǎng)絡(luò)數(shù)量最小及數(shù)據(jù)中心和網(wǎng)絡(luò)鏈接所消耗的計算資源最小來優(yōu)化分布式系統(tǒng)的通信負載。 (4)研究了基于P2P的分布式數(shù)據(jù)流查詢處理的中間件和原型開發(fā)。首先利用P2P的特性改進了索

11、引結(jié)構(gòu)的定位查詢過程和穩(wěn)定性。然后，將數(shù)據(jù)流的概要映射到改進的弦環(huán)節(jié)點，將基于內(nèi)容的路由擴展到分布式流索引中，在此基礎(chǔ)上，提供連續(xù)近似查詢，并利用最小邊界矩形MBR等優(yōu)化方法，通過自適應(yīng)地調(diào)整MBR的每一維f的高低邊界來改進系統(tǒng)的精確度。在減小中心數(shù)據(jù)和網(wǎng)絡(luò)鏈接所消耗的計算資源的情況下，加快和提高流數(shù)據(jù)查詢和挖掘的效率，及時響應(yīng)客戶的查詢請求。 本論文的研究依托于國家863項目“基于Web服務(wù)的數(shù)據(jù)庫新技術(shù)”的子項目“基于Web