1、隨著移動終端、傳感器、互聯(lián)網(wǎng)等技術(shù)的飛速發(fā)展，流數(shù)據(jù)作為一種典型的大數(shù)據(jù)已經(jīng)在許多領(lǐng)域廣泛出現(xiàn)。當前，流數(shù)據(jù)包含時空數(shù)據(jù)、傳感數(shù)據(jù)、社交網(wǎng)絡數(shù)據(jù)等多種類型數(shù)據(jù)，數(shù)據(jù)本身蘊含巨大的價值，這使得流數(shù)據(jù)挖掘具有重要的學術(shù)價值和應用價值。與靜態(tài)數(shù)據(jù)相比，流數(shù)據(jù)有其自身特點:原始數(shù)據(jù)量巨大、數(shù)據(jù)到達速度快、數(shù)據(jù)處理對時效性要求高、數(shù)據(jù)難以重復獲取。由于流數(shù)據(jù)自身的特點，一些已有的數(shù)據(jù)挖掘技術(shù)很難直接用來解決流數(shù)據(jù)挖掘問題，因此研究流數(shù)據(jù)挖掘相關(guān)問

2、題具有重要意義。
　　本文針對海量流數(shù)據(jù)挖掘領(lǐng)域的相關(guān)問題進行了研究。第一個問題是多數(shù)據(jù)流的頻繁伴隨模式發(fā)現(xiàn)問題。頻繁伴隨模式（Frequent Co-occurrence Pattern）是指一組對象較短時間內(nèi)在同一個數(shù)據(jù)流里伴隨出現(xiàn)，并且在之后指定的一段時間內(nèi)以同樣的方式出現(xiàn)在多個數(shù)據(jù)流上。本文的目標是實時發(fā)現(xiàn)多個數(shù)據(jù)流里出現(xiàn)的所有頻繁伴隨模式。在實際應用中，城市交通管控系統(tǒng)的伴隨車輛發(fā)現(xiàn)、電子商務中的熱銷商品組合挖掘、基于簽

3、到數(shù)據(jù)的伴隨人群發(fā)現(xiàn)以及社交網(wǎng)絡數(shù)據(jù)中基于高頻伴隨詞組的熱點事件發(fā)現(xiàn)等應用都可以抽象為多數(shù)據(jù)流的頻繁伴隨模式發(fā)現(xiàn)問題。為解決這一問題，本文提出了基于segment片段的流數(shù)據(jù)劃分策略，并設計了DIMine和CooMine兩種挖掘方法。這兩種算法首先對有效的segment片段建立索引，然后基于segment索引結(jié)構(gòu)設計剪枝策略，通過不斷削減挖掘范圍以達到快速發(fā)現(xiàn)頻繁伴隨模式的目的。
　　DIMine和CooMine挖掘算法在挖掘效率

4、、內(nèi)存消耗和索引維護代價取得了很好的效果。但它們是適合單機運行的集中式算法，難以直接部署到分布式環(huán)境中應對規(guī)模巨大的流數(shù)據(jù)。為了能夠在大規(guī)模流數(shù)據(jù)中發(fā)現(xiàn)頻繁伴隨模式，本文設計了多數(shù)據(jù)流頻繁伴隨模式的分布式挖掘方法。該方法首先產(chǎn)生所有數(shù)據(jù)流中可能形成頻繁伴隨模式的候選模式，然后通過哈希方法將不同數(shù)據(jù)流的相同候選模式發(fā)送至至同一個計算單元，繼而判定該候選模式是否為頻繁伴隨模式。由于每個候選模式是獨立的，不同的候選模式可以由多個計算單元同時處

5、理，因此該方法能夠利用分布式服務器集群進行并行計算，從而具備良好的可擴展性。
　　本文研究的第三個問題是分布式時空數(shù)據(jù)的k近鄰搜索問題。時空數(shù)據(jù)是一種典型的流數(shù)據(jù)，k近鄰搜索是許多數(shù)據(jù)挖掘問題的基本操作。給定一個時空數(shù)據(jù)集和任意一個查詢點，k近鄰搜索要求實時地得到該時空數(shù)據(jù)集中與該查詢點距離最近的k個對象。已有的時空數(shù)據(jù)k近鄰搜索算法通常假設時空數(shù)據(jù)集規(guī)模有限且查詢數(shù)量較少，其研究重點是面向單個計算節(jié)點的k近鄰集中式查詢算法，很難

6、將它們應用到分布式環(huán)境下以處理大規(guī)模時空數(shù)據(jù)和高并發(fā)k近鄰搜索。為此，本文提出了面向海量時空數(shù)據(jù)的分布式k近鄰搜索算法。該算法首先設計了分布式動態(tài)條狀索引結(jié)構(gòu)(DynamicStrip Index，DSI)，與已有的網(wǎng)格索引相比，DSI索引結(jié)構(gòu)能夠適應不同的數(shù)據(jù)分布。此外，DSI索引結(jié)構(gòu)更容易分布式部署到多個計算節(jié)點之上?；谠撍饕?，我們設計了DKNN查詢算法。該算法能夠?qū)NN查詢的迭代次數(shù)減少至兩次，與已有的算法相比，DKNN算法的

7、性能更加高效且可以預測。隨后，我們將DSI索引結(jié)構(gòu)和DKNN查詢算法在開源的流數(shù)據(jù)處理平臺S4上進行了實現(xiàn)，通過大量實驗證明了算法良好的可擴展性和優(yōu)異性能。
　　本文對流數(shù)據(jù)挖掘相關(guān)問題進行了深入研究，針對特定問題，給出了針對性的解決方案。本文的創(chuàng)新點和貢獻如下:
　　(1)本文首次提出多數(shù)據(jù)流頻繁伴隨模式發(fā)現(xiàn)這一問題，并給出了DIMine算法和CooMine算法兩種解決方案。
　　(2)本文提出了分布式的多數(shù)據(jù)流頻繁