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

1、隨著大規(guī)模網(wǎng)絡(luò)的發(fā)展和Web的廣泛應(yīng)用，在網(wǎng)絡(luò)監(jiān)控、入侵檢測(cè)、傳感器網(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ù)庫(kù)應(yīng)用模型不同，數(shù)據(jù)流模型具有以下特點(diǎn)：(1)數(shù)據(jù)連續(xù)、實(shí)時(shí)到達(dá)；(2)數(shù)據(jù)量大、無(wú)限制并且難以預(yù)測(cè)；(3)數(shù)據(jù)一經(jīng)處理，除非特意保存，否則不能被再次取出處理，即一次性處理(one—pass)，或者再次提取數(shù)據(jù)的代價(jià)

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

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

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

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

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

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

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

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

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

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