數(shù)據(jù)流管理和挖掘技術(shù)探析

（大慶石油學(xué)院 計算機與信息技術(shù)學(xué)院， 黑龍江 大慶 163318）

摘 要：數(shù)據(jù)流管理和挖掘技術(shù)是數(shù)據(jù)庫領(lǐng)域的新研究方向之一。概述了數(shù)據(jù)庫技術(shù)的發(fā)展趨勢以及數(shù)據(jù)流的概念、特點、體系結(jié)構(gòu)、應(yīng)用領(lǐng)域，分析了數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)的構(gòu)造問題和數(shù)據(jù)流的連續(xù)近似查詢技術(shù)，最后介紹了數(shù)據(jù)流挖掘技術(shù)。旨在描述數(shù)據(jù)流管理和挖掘技術(shù)的發(fā)展概況，為進一步的研究提供有益的借鑒。

關(guān)鍵詞：泛數(shù)據(jù)； 數(shù)據(jù)流； 概要數(shù)據(jù)結(jié)構(gòu)； 連續(xù)近似查詢； 數(shù)據(jù)流挖掘

中圖法分類號：TP391文獻標識碼：A

文章編號：1001-3695(2006)08-0085-04



Technology of Data Stream Management and Mining



MA Rui min， WANG Xiao long

(College of Computer Information Technology， Daqing Petroleum Institute， Daqing Heilongjiang 163318， China)

Abstract:The research on data stream is one of the hot topics among the database domain all over the world resently. Firstly， the trend of database technology is summarized， and concepts， characteristics， architecture， applications of data stream are outlined. Second， some methods of constructing synopsis data structure are analyzed concisely， the technology of continuous approximate query is analyzed summarily. Finally， the research on data stream mining is analyzed. The objective of this paper is to contribute to the overall understanding of the technologies available for managing and mining data streams.

Key words:Pan data; Data Stream; Synopsis Data Structure; Continuous Approximate Query; Data Stream Mining

近年來，數(shù)據(jù)庫領(lǐng)域出現(xiàn)了眾多的新技術(shù)，如數(shù)據(jù)流管理和挖掘、XML數(shù)據(jù)管理和分析、對等（P2P）數(shù)據(jù)管理、Web數(shù)據(jù)管理和挖掘、網(wǎng)格數(shù)據(jù)管理、移動數(shù)據(jù)管理、DBMS自適應(yīng)管理、數(shù)據(jù)庫用戶界面、文本挖掘、空間—時間數(shù)據(jù)庫、微小型數(shù)據(jù)庫、生物信息數(shù)據(jù)庫、數(shù)字圖書館、數(shù)據(jù)安全以及One Hundred Year存儲技術(shù)等。Dr. Jim Gray在ACM SIGMOD 2004年會的主題發(fā)言中提到，數(shù)據(jù)庫體系結(jié)構(gòu)面臨著變革，新的應(yīng)用需求將促進這一變革的實現(xiàn)[1]。特別地，Internet的發(fā)展對數(shù)據(jù)庫的研究起到了革命性的推動作用：從深度上，在Internet環(huán)境下，傳統(tǒng)數(shù)據(jù)庫管理技術(shù)的基本假設(shè)不再成立，需要對已經(jīng)比較成熟的傳統(tǒng)數(shù)據(jù)庫技術(shù)進行變革；從廣度上，數(shù)據(jù)庫領(lǐng)域內(nèi)出現(xiàn)的眾多新問題要求研究者不斷地創(chuàng)新求解。在Web背景下，有學(xué)者提出了泛數(shù)據(jù)[2]的概念。所謂的泛數(shù)據(jù)，是指相對于傳統(tǒng)的關(guān)系數(shù)據(jù)庫系統(tǒng)（RDBMS）等處理的企業(yè)業(yè)務(wù)數(shù)據(jù)而言的，它包括如下兩方面內(nèi)容：

(1)X data。XML Data(XML Databases)， Streaming Data(data Streams， Streaming Databases)， etc.。

(2)X computing。 Grid Data(Grid Databases)， Sensor Data (Sensor Databases)， Ubiquitous/Pervasive Computing (Ubiquitous /Pervasive Databases)， P2P Computing(P2P Databases)， etc.。

1數(shù)據(jù)流和數(shù)據(jù)流管理系統(tǒng)

最近出現(xiàn)了一些新的、動態(tài)的密集數(shù)據(jù)應(yīng)用環(huán)境，如傳感器網(wǎng)絡(luò)數(shù)據(jù)流、XML數(shù)據(jù)流、證券交易數(shù)據(jù)流、網(wǎng)絡(luò)入侵監(jiān)測、普適計算、P2P計算數(shù)據(jù)管理等。典型的實例[3]包括：航天飛機，每秒大約有20000個傳感器數(shù)據(jù)傳送到控制中心；美國的50 000余種有價證券，每秒可產(chǎn)生100 000筆交易數(shù)據(jù)。

1．1概念、特點與體系結(jié)構(gòu)

（1）概念。連續(xù)的、近似無限的、時變的、有序的且快速流動的數(shù)據(jù)元素組成的無限序列稱為數(shù)據(jù)流（Data Stream）。按照固定的次序，這些數(shù)據(jù)元素只能被讀取一次。若令t表示任一時間戳（Time Stamp），x_t表示在t時刻到達的數(shù)據(jù)元素，則數(shù)據(jù)流可以表示為無限集合{…，x_t-1，x_t，x_t+1，…}。位于用戶和操作系統(tǒng)之間，能夠完成數(shù)據(jù)流定義、數(shù)據(jù)流操作、數(shù)據(jù)流操縱、數(shù)據(jù)流維護等功能的系統(tǒng)軟件稱為數(shù)據(jù)流管理系統(tǒng)(Data Streams Management System，DSMS)。處理數(shù)據(jù)流的系統(tǒng)環(huán)境統(tǒng)稱為數(shù)據(jù)流系統(tǒng)(Data Streams System，DSS)。

（2）特點：①有序性、連續(xù)性、實時（或隨時）性，數(shù)據(jù)有序地、連續(xù)地到達并實時地變化；②無限性，大數(shù)據(jù)量，甚至是無限的數(shù)據(jù)量，存儲所有數(shù)據(jù)的代價是極大的；③單遍性，由于內(nèi)存的限制，只能對數(shù)據(jù)流進行單遍掃描；④概要性，處理數(shù)據(jù)流數(shù)據(jù)時，要求構(gòu)造概要數(shù)據(jù)結(jié)構(gòu)；⑤低層次性和多維性，數(shù)據(jù)流的原始細節(jié)數(shù)據(jù)的概念層次較低且具有多維（或高維）的特點；⑥近似性，數(shù)據(jù)流查詢以及挖掘處理得到的結(jié)果是近似的；⑦即時性，用戶要求得到即時的處理結(jié)果。

另外，分布式數(shù)據(jù)流還具有分布性、并行性和多重性的特點。

值得指出的是，傳統(tǒng)的實時數(shù)據(jù)庫(Real time Database)技術(shù)以及中間件（Middleware）技術(shù)一般不適合于用來解決數(shù)據(jù)流的查詢、挖掘等問題，或在某種程度上只能滿足部分的數(shù)據(jù)流處理要求，其原因之一是這兩種技術(shù)的處理引擎的效率與數(shù)據(jù)流的流速不匹配。

（3）體系結(jié)構(gòu)。數(shù)據(jù)流管理系統(tǒng)體系結(jié)構(gòu)如圖1[4]所示。比較圖1和圖2可知，數(shù)據(jù)流系統(tǒng)的相關(guān)數(shù)據(jù)結(jié)構(gòu)和算法是基于內(nèi)存的，只有有限的存儲與處理空間；而傳統(tǒng)數(shù)據(jù)庫(數(shù)據(jù)倉庫)系統(tǒng)的相關(guān)數(shù)據(jù)結(jié)構(gòu)和算法是基于內(nèi)存和磁盤的，一般情況下具有足夠的存儲與處理空間。

（4）數(shù)據(jù)流管理系統(tǒng)。其功能包括數(shù)據(jù)流定義、數(shù)據(jù)流操作、數(shù)據(jù)流操縱、數(shù)據(jù)流維護等，其與傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)的比較如表1所示。

（5）數(shù)據(jù)流管理系統(tǒng)原型。目前，部分已公開的數(shù)據(jù)流管理的原型系統(tǒng)如表2所示。其中，STREAM是一個通用的數(shù)據(jù)流管理原型系統(tǒng)，該系統(tǒng)提供了一種連續(xù)查詢語言CQL（Continuous Query Language），它既可以處理數(shù)據(jù)流數(shù)據(jù)又可以處理關(guān)系型數(shù)據(jù)。提供了STREAM的結(jié)構(gòu)圖[4]以便于理解該數(shù)據(jù)流管理系統(tǒng)。Aurora是應(yīng)用于數(shù)據(jù)流監(jiān)控的原型系統(tǒng)，其核心組成是多個觸發(fā)器（Triggers）組成的網(wǎng)絡(luò)，該系統(tǒng)可以執(zhí)行一些優(yōu)化處理，如Compile time和Run time優(yōu)化，以及降載（Load Shedding）處理技術(shù)等。

（6）應(yīng)用領(lǐng)域。它包括：①經(jīng)濟金融領(lǐng)域，如金融、股票、商業(yè)交易數(shù)據(jù)流的管理和分析。②通信領(lǐng)域，如電信呼叫記錄數(shù)據(jù)流的管理和分析等。③科學(xué)計算領(lǐng)域，如天氣預(yù)報、災(zāi)害預(yù)防、天文數(shù)據(jù)等實時數(shù)據(jù)流分析。④控制領(lǐng)域，如傳感器網(wǎng)絡(luò)數(shù)據(jù)流處理、制造業(yè)、工業(yè)過程控制、交通管理、網(wǎng)絡(luò)路由。⑤安全領(lǐng)域，如Web日志分析、網(wǎng)絡(luò)入侵檢測，安全、設(shè)施、設(shè)備監(jiān)控。⑥普適計算領(lǐng)域。⑦軍事領(lǐng)域。



2概要數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)流管理、查詢和挖掘任務(wù)對數(shù)據(jù)結(jié)構(gòu)、算法等提出了新的要求。在處理數(shù)據(jù)流時，要求設(shè)計出有效的單遍掃描算法，在有限的內(nèi)存空間里不斷更新能夠表征數(shù)據(jù)流的概要數(shù)據(jù)結(jié)構(gòu)，使得查詢、挖掘算法在任意時刻都能夠根據(jù)概要數(shù)據(jù)結(jié)構(gòu)獲得近似的且其準確性有概率保證的計算結(jié)果。一般地，數(shù)據(jù)流處理的聯(lián)機（On line）算法主要包括兩部分內(nèi)容：①監(jiān)控數(shù)據(jù)流并不斷更新概要數(shù)據(jù)結(jié)構(gòu)的算法；②響應(yīng)用戶的查詢請求和挖掘任務(wù)，并且能實時地計算得到近似結(jié)果的算法。在此，相關(guān)的算法要能夠以概率1-δ保證計算結(jié)果的誤差被限制在一個小的范圍內(nèi)，其中δ是一個接近于0的小數(shù)。同時，由于內(nèi)存空間的限制，要求概要數(shù)據(jù)結(jié)構(gòu)模型的復(fù)雜度至多是次線性的，即如果被處理的數(shù)據(jù)流的長度是n，則概要數(shù)據(jù)結(jié)構(gòu)的空間復(fù)雜度不能超過O(polylog(n))，且處理數(shù)據(jù)流上的各部分相對獨立數(shù)據(jù)的時間復(fù)雜度也不能超過O(polylog(n))[5]。根據(jù)數(shù)據(jù)流的特點可知，數(shù)據(jù)結(jié)構(gòu)模型的及時更新問題是數(shù)據(jù)流技術(shù)要解決的關(guān)鍵問題之一。

目前，較為有效地構(gòu)造概要數(shù)據(jù)結(jié)構(gòu)的方法如下所述：

（1）批處理的方法。該方法的前提條件是所使用的數(shù)據(jù)結(jié)構(gòu)可以增量更新[6]。根據(jù)數(shù)據(jù)流的特性可知，運用批處理方法處理數(shù)據(jù)流時很可能出現(xiàn)數(shù)據(jù)流數(shù)據(jù)到達（即更新）的速率大于算法執(zhí)行速率的情況，此時應(yīng)該對數(shù)據(jù)流數(shù)據(jù)進行緩沖（Buffer），以適應(yīng)批處理周期性的處理結(jié)果的生成。批處理方法的優(yōu)點是：①特別適合于處理經(jīng)常出現(xiàn)負載峰值的數(shù)據(jù)流數(shù)據(jù)；②與基于滑動窗口、界標等模型的方法相比，它可以提供準確性更高的計算結(jié)果。

（2）基于滑動窗口模型的方法。一般地，通過在內(nèi)存中創(chuàng)建滑動窗口來保存最近一段時間內(nèi)到達的數(shù)據(jù)流數(shù)據(jù)集合，以實時地支持連續(xù)查詢或挖掘。滑動窗口模型的查詢范圍可表示為{x_{max(0，n-W+1)}，…，x_n}，其中W稱為滑動窗口的大小，即滑動窗口中最新到達的數(shù)據(jù)或元組（Tuple）個數(shù)，n表示當前時間戳，滑動窗口的起始時刻取為max(0，n-W+1)是因為要考慮n＜W的情況。x_n是n時刻到達的數(shù)據(jù)或元組。滑動窗口也可以根據(jù)有序到達的元組的個數(shù)來定義，即在滑動窗口中保存最近到達的k個元組，k為設(shè)定的自然數(shù)。

基于滑動窗口模型的方法包括基本窗口[3]（Basic Window）、指數(shù)直方圖[7](Exponential Histogram)、鏈式抽樣[8](Chain Sampling)方法；Chris Giannella等人提出的為每個模式增量地保持不同的時間粒度，使用了傾斜的滑動窗口（Tilted time Windows）的方法[9]；李建中等人提出了一種滑動窗口規(guī)模的動態(tài)調(diào)整算法[10]等。

（3）基于界標模型(Landmark Model)的方法。界標模型的數(shù)據(jù)流查詢和處理范圍可表示為{x_s，…，x_n}，其中n表示當前時間戳，s是設(shè)定的初始時間戳，x_s是s時刻到達的數(shù)據(jù)，x_n是n時刻到達的數(shù)據(jù)。

基于界標模型的方法包括：①抽樣（Sampling）方法。該方法從連續(xù)到達的數(shù)據(jù)流中隨機抽取樣本數(shù)據(jù)以表征整個數(shù)據(jù)流，并被用于查詢和挖掘處理，它包括Reservoir Sampling[11]，Concise Sampling[12]，Counting Sampling[12]等。②直方圖(Histogram)方法。該方法將連續(xù)到達的數(shù)據(jù)流劃分為不同的子集，可以有效地表征數(shù)據(jù)流的輪廓，它包括等寬直方圖[13]、壓縮直方圖[14]、V optimal直方圖[15]等。③Hash方法。該方法是利用Hash函數(shù)將數(shù)據(jù)流數(shù)據(jù)映射到一個較小數(shù)值區(qū)間，對該區(qū)間內(nèi)的數(shù)據(jù)進行分析可以得到原始數(shù)據(jù)流的特征，它包括Sketch[16]，Bloom Filter[17]，F(xiàn)lajolet Martin[18]方法等。④小波（Wavelet）變換方法[19]。該方法利用對數(shù)據(jù)流進行變換后生成的少量小波參數(shù)來近似模擬原始數(shù)據(jù)流，Haar Wavelet是常用的小波類型。

（4）快照（Snapshot）方法。該方法將數(shù)據(jù)流處理限制在預(yù)定義的時間點或時間段內(nèi)。值得指出的是，利用快照方法處理數(shù)據(jù)流數(shù)據(jù)的效率較低，因為數(shù)據(jù)流是連續(xù)的、時變的、快速的，并且數(shù)據(jù)流的處理也要求具有連續(xù)性、快速性、概要性。

（5）近期還有研究者提出On line Amnesic[20]以及對數(shù)據(jù)流進行壓縮[21]等方法。

（6）在查詢或挖掘傳統(tǒng)數(shù)據(jù)庫和數(shù)據(jù)倉庫時，數(shù)據(jù)預(yù)處理階段的數(shù)據(jù)歸約和數(shù)據(jù)變換技術(shù)是非常重要的。可以假設(shè)，運用滑動窗口、抽樣、直方圖等方法抽取動態(tài)的數(shù)據(jù)流后形成的數(shù)據(jù)集合就是靜態(tài)的，這樣就可以利用數(shù)據(jù)庫的數(shù)據(jù)歸約和變換技術(shù)來進一步調(diào)整數(shù)據(jù)流的概要數(shù)據(jù)結(jié)構(gòu)和算法的空間復(fù)雜度，例如進行屬性歸約可以排除冗余和不重要的屬性。

提出更有效的概要數(shù)據(jù)結(jié)構(gòu)，以減約數(shù)據(jù)流問題的復(fù)雜度并提高處理結(jié)果的精確性是當前研究面臨的問題。

3數(shù)據(jù)流查詢——連續(xù)近似查詢

數(shù)據(jù)流環(huán)境下的查詢是連續(xù)的近似查詢。連續(xù)近似查詢是指用戶提交（定義）查詢請求后，查詢過程持續(xù)地執(zhí)行并返回近似的查詢結(jié)果，當查詢過程所涉及的數(shù)據(jù)流的內(nèi)容發(fā)生變化時，可以獲得新的近似查詢結(jié)果，查詢過程直到用戶顯式地終止它時才結(jié)束(或通過設(shè)定一個確定的運行時間終止)。例如，用戶要求查詢得到當前時刻之后的兩個小時內(nèi)股價至少上漲15%的股票名稱。

數(shù)據(jù)流連續(xù)近似查詢的特性可歸納為預(yù)定性、隨時性、連續(xù)性、概要性、近似性。連續(xù)近似查詢所面臨的問題主要包括：

（1）降載問題。在數(shù)據(jù)流的動態(tài)連續(xù)查詢過程中，數(shù)據(jù)的流量可能比較大，并有可能出現(xiàn)流量達到某峰值的情況；再者，分布式數(shù)據(jù)流系統(tǒng)中節(jié)點之間的通信帶寬的有限性和瓶頸性、內(nèi)存空間的有限性均可能要求考慮對數(shù)據(jù)流進行降載處理。

（2）多次自適應(yīng)優(yōu)化問題。在數(shù)據(jù)流連續(xù)近似查詢的過程中，數(shù)據(jù)流的流速很有可能會發(fā)生明顯改變等，將造成查詢執(zhí)行環(huán)境的頻繁變化，因此要求查詢算法進行多次的自適應(yīng)優(yōu)化。

（3）基于實時QoS模型的多目標優(yōu)化問題，如文獻[22]中分析了查詢精度QoS和響應(yīng)時間之間的權(quán)衡。

（4）索引問題。為了提高單數(shù)據(jù)流或多重數(shù)據(jù)流操作的執(zhí)行效率，需要考慮采用基于內(nèi)存的索引技術(shù)。

（5）共享策略問題。在進行單數(shù)據(jù)流或多數(shù)據(jù)流查詢時，可能同時需要提交和執(zhí)行多個連續(xù)查詢，為了節(jié)約內(nèi)存空間，需要考慮多個查詢間的共享策略。

（6）Non blocking查詢問題。Blocking查詢[5]是指必須對所有的相關(guān)數(shù)據(jù)掃描后才能進行的查詢，顯然在數(shù)據(jù)流環(huán)境下，Blocking查詢不可能被執(zhí)行。因此，在進行數(shù)據(jù)流查詢時，需要考慮將傳統(tǒng)的分塊查詢轉(zhuǎn)換為Non blocking查詢的方法。

當前數(shù)據(jù)流連續(xù)近似查詢研究的熱點問題還包括傳感器網(wǎng)絡(luò)數(shù)據(jù)流查詢、XML數(shù)據(jù)流的連續(xù)近似查詢以及普適計算信息連續(xù)查詢等。

4數(shù)據(jù)流連續(xù)挖掘

自20世紀90年代中后期數(shù)據(jù)挖掘（Data Mining）技術(shù)引起研究者的重視以來，這個研究方向發(fā)展非常迅速。經(jīng)過近十年的發(fā)展，關(guān)聯(lián)規(guī)則、聚類、分類等的基本挖掘算法已經(jīng)比較成熟。目前，挖掘技術(shù)的研究重點逐漸轉(zhuǎn)移到新應(yīng)用領(lǐng)域上，即演變?yōu)閿?shù)據(jù)流上的知識發(fā)現(xiàn)。在分析和挖掘數(shù)據(jù)流時，由于數(shù)據(jù)流迅速、大量、連續(xù)地到達，算法只能對數(shù)據(jù)流進行單遍掃描，僅臨時在內(nèi)存中存儲少量數(shù)據(jù)，因此原來許多較為成熟的靜態(tài)數(shù)據(jù)挖掘技術(shù)變得不再適用了，需要提出新的內(nèi)存駐留算法。這是數(shù)據(jù)流連續(xù)挖掘問題出現(xiàn)的技術(shù)背景。

支持數(shù)據(jù)流上的連續(xù)挖掘的算法一般需要滿足三個條件，即基于內(nèi)存、快速和能夠適應(yīng)概念轉(zhuǎn)移（Concept Drift）。在數(shù)據(jù)流上，需要挖掘的知識類型主要包括分類（Classification）、聚類(Clustering)、頻繁項集（Frequent Itemset）、變化（Change）等。

（1）數(shù)據(jù)流上的分類就是提出一個分類模型（或函數(shù)），并通過單遍掃描數(shù)據(jù)流，持續(xù)地利用分類模型將數(shù)據(jù)對象（數(shù)據(jù)流的數(shù)據(jù)點或元組等）映射到某一個給定的類別中。例如，Geoff Hulten等人提出了CVFDT方法來動態(tài)地構(gòu)造判定樹，并通過Hoeffding來保證用于構(gòu)造每棵子樹所使用的數(shù)據(jù)均包含足夠的信息量，隨著數(shù)據(jù)的連續(xù)流入動態(tài)地增加新分支或動態(tài)剪枝[23]。CVFDT算法是在VFDT基礎(chǔ)上設(shè)計的，CVFDT的準確性與反復(fù)地使用VFDT的效果類似，并且其復(fù)雜度很小（處理每個Example的復(fù)雜度僅為O(1)）。

（2）數(shù)據(jù)流上的聚類就是通過單遍掃描數(shù)據(jù)流，持續(xù)地將數(shù)據(jù)流數(shù)據(jù)對象（數(shù)據(jù)點、元組等）分組成多個類或簇（Cluster），在同一個簇中的數(shù)據(jù)對象之間具有較高的相似度，而不同簇間的數(shù)據(jù)對象的相似度很小。例如，Moses Charikar等人提出了基于 K means的隨機方法[24]，該方法單遍掃描數(shù)據(jù)流所需的空間復(fù)雜度是O(k×polylog(n))。

（3）數(shù)據(jù)流上的頻繁項集挖掘就是單遍掃描數(shù)據(jù)流來連續(xù)地發(fā)現(xiàn)其中的頻繁項集。頻繁項集是滿足最小支持度的項集（Itemset），對于數(shù)據(jù)流上的頻繁項集挖掘的研究方法大多數(shù)均采用ε 算法，可參閱文獻[25]。

（4）數(shù)據(jù)流上的變化一般是指數(shù)據(jù)流上的模式的變化，此處的變化是在數(shù)據(jù)流上要挖掘的知識類型之一[26]。連續(xù)挖掘數(shù)據(jù)流上的數(shù)據(jù)模式的變化是在單遍掃描數(shù)據(jù)流的過程中完成的。例如，Guozhu Dong等學(xué)者提出聯(lián)機挖掘數(shù)據(jù)流上的變化是數(shù)據(jù)流挖掘技術(shù)的核心問題之一[26]。根據(jù)數(shù)據(jù)流的本質(zhì)和特點可知，一般地，數(shù)據(jù)流上的模式挖掘是重要的，但是模式的變化情況可能更加關(guān)鍵和有意義。

另外，數(shù)據(jù)流上的跳變（Burst）分析和挖掘也可以歸類為數(shù)據(jù)流上的變化的連續(xù)挖掘問題，跳變可以被理解為是數(shù)據(jù)流上的脈沖式變化或孤立點（Outlier）。

由于數(shù)據(jù)流具有獨特的性質(zhì)，對其進行連續(xù)挖掘是一個挑戰(zhàn)性的問題。當前的有關(guān)算法的研究有很多是在傳統(tǒng)的增量式挖掘技術(shù)基礎(chǔ)之上發(fā)展而來的，探索數(shù)據(jù)流連續(xù)挖掘技術(shù)與傳統(tǒng)的靜態(tài)數(shù)據(jù)挖掘技術(shù)之間的本質(zhì)區(qū)別，提出更有效、新穎的基于內(nèi)存的數(shù)據(jù)流連續(xù)、快速挖掘算法是當前研究面臨的重要問題。

5結(jié)束語

數(shù)據(jù)流管理和連續(xù)挖掘技術(shù)的研究正處于方興未艾階段，不但相關(guān)的數(shù)據(jù)結(jié)構(gòu)、算法的研究得到了重視，并且還有研究者提出需要對數(shù)據(jù)庫的體系結(jié)構(gòu)進行變革[27]以適應(yīng)新技術(shù)的發(fā)展需要。Dr. Jim Gray在ACM SIGMOD 2004年會的主題發(fā)言[1]以及Dr. Pat Selinger在ICDE 2005會議上提出的未來十年數(shù)據(jù)庫領(lǐng)域的五個挑戰(zhàn)性問題[28]可以為數(shù)據(jù)流技術(shù)研究者提供富有意義的借鑒。目前，特別需要重視的是數(shù)據(jù)流技術(shù)與XML數(shù)據(jù)管理以及對等計算環(huán)境下的數(shù)據(jù)管理這兩個重要數(shù)據(jù)庫研究問題的結(jié)合。

參考文獻：

[1]Jim Gray. The Revolution in Database Systems Architecture[EB/OL]. http://research.microsoft.com， 2004.

[2]孟小峰.數(shù)據(jù)庫技術(shù)發(fā)展的思考[EB/OL]. http://www.ccf dbs.org.cn/news/article_132.html， 2004.

[3]Yunyue Zhu， Dennis Shasha. StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time[EB/OL]. http://cs.nyu.edu， 2002.

[4]The Strean Group. Stanford Data Stream Management System(Lastest Overview Paper)[EB/OL]. http://db. stanford.edu， 2005.

[5]Brian Babcock， Shivnath Babu， et al. Models and Issues in Data Stream System[EB/OL]. http://www.cs.cmu.edu， 2002.

[6]T Urhan， M Franklin. XJoin: A Reactively scheduled Pipelined Join Operator[J]. IEEE Data Engineering Bulletin， 2000，23(2):27-33.

[7]Datar M， Gionis A， Indyk P， et al. Maintaining Stream Statistics over Sliding Windows[C]. San Francisco: Proc. of the 13th Annual ACM SIAM Symp. on Discrete Algorithms， 2002.635-644.

[8]Babcock B， Datar M， Motwani R. Sampling from a Moving Window over Streaming Data[C]. San Francisco: Proc. of the 13th Annual ACM SIAM Symp. on Discrete Algorithms， 2002.633-634.

[9]Chris Giannella， Jiawei Han， Jian Pei， et al. Mining Frequent Patterns in Data Streams at Multiple Time Granularities[EB/OL]. http://maids.ncsa.uiuc.edu， 2003.

[10]李建中，張冬冬.滑動窗口規(guī)模的動態(tài)調(diào)整算法[J].軟件學(xué)報， 2004，15(12):1800-1814.

[11]Vitter J S. Random Sampling with a Reservoir[J]. ACM Trans. on Mathematical Software， 1985，11(1):37-57.

[12]Gibbons P B， Matias Y. New Sampling based Summary Statistics for Improving Approximate Query Answers[C].Seattle:Proc.of the ACM SIGMOD Int’l Conf. on Management of Data， ACM Press， 1998.331-342.

[13]Gibbons P B， Matias Y， Poosala V. Fast Incremental Maintenance of Approximate Histograms[C]. Athens:Proc.of the 23rd Int’l Conf.， on Very Large Database， Morgan Kaufmann， 1997.466-475.

[14]Poosala V， Ioannidis Y， Haas P， et al. Improved Histograms for Selectivity Estimation of Range Predicates[J]. SIGMOD Record， 1996，25(2):294-305.

[15]Gilbert A， Guha S， Indyk P， et al. Fast Small space Algorithms for Approximate Histogram Maintenance[C]. Montral: Proc.of the 34th Annual ACM Symp. on Theory of Computing， ACM Press， 2002.389-398.

[16]Charikar M， Chen K， et al. Finding Frequent Items in Data Streams[J]. Theoretical Computer Science， 2004，312(1):3 15.

[17]Cohen S， Matias Y. Spectral Bloom Filters[C]. San Diego:Proc. of the ACM SIGMOD Int’l Conf. on Management of Data， ACM Press， 2003.241-252.

[18]Ganguly S， Garofalakis M， et al. Processing Set Expressions over Continuous Update Streams[EB/OL]. http://portal.acm.org， 2003.

[19]Garofalakis M， Gibbons P B. Wavelet Synopses with Error Guarantees[C]. Madison: Proc. of the ACM SIGMOD Int’l Conf. on Management of Data， ACM Press， 2002.476-487.

[20]T Palpanas， M Vlachos， et al. On line Amnesic: Approximation of Streaming Time Series[EB/OL]. http://portal.acm.org ， 2004.

[21]王栩，李建中，王偉平.基于滑動窗口的數(shù)據(jù)流壓縮技術(shù)及連續(xù)查詢處理方法[J]. 計算機研究與發(fā)展， 2004，41(10):1639-1644.

[22]Nesime Tatbul， et al. Load Shedding in a Data Stream Manager[EB/OL]. http://wilma.cs.brown.edu， 2003.

[23]G Hulten， L Spencer， P Domingos. Mining Time changing Data Streams[EB/OL]. http://portal.acm.org/， 2001.

[24]Moses Charikar， Liadan O’Callaghan， Rina Panigrahy. Better Streaming Algorithms for Clustering Problems[EB/OL]. http://portal.acm.org， 2003.

[25]M Garofalakis， J Gehrke， R Rastogi. Querying and Mining Data Streams: You Only Get One Look a Tutorial[EB/OL]. http://portal.acm.org ， 2002.

[26]Guozhu Dong， Jiawei Han， et al. On line Mining of Changes from Data Streams: Research Problems and Preliminary Results[EB/OL]. http://www.research.att.com/conf/mpds2003/schedule/donghlpwy.pdf， 2003.

[27]Anastassia Ailamaki. Database Architectures for New Hardware[EB/OL]. http://csdl.computer.org/comp/proceedings/ icde/2005/2285/00/22851148.pdf， 2005.

[28]Pat Selinger. Top Five Data Challenges for the Next Decade[EB/OL]. http:// icde2005.naist.jp/keynote1.pdf ， 2005.

作者簡介：馬瑞民，男，教授，主要研究方向為數(shù)據(jù)庫、數(shù)據(jù)挖掘；王小龍，男，碩士研究生，主要研究方向為數(shù)據(jù)流管理和挖掘技術(shù)。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。