一種流數據立方體分析挖掘框架*

金蒼宏 ，劉澤民 ，吳明暉 ，應 晶 ,

（1.浙江大學計算機科學與技術學院 杭州 310027；2.浙江大學城市學院 杭州 310015）

1 引言

聯機分析挖掘（online analytical mining，OLAM）是一種結合數據挖掘和聯機分析處理 （online analytical processing，OLAP）的知識發現方法。使用OLAM可在多維數據庫的不同數據子集和抽象層次上進行探索式挖掘，因此在決策定制、市場分析、可視化等領域都發揮著重要作用。隨著移動互聯網的迅速發展和廣泛應用，各種類型的數據流規模急劇增大，如金融流數據、圖像流數據、社交流數據等。挖掘數據流中包含用戶刻面和行為動作的相關信息，成為當前研究的一個熱點[1]。如在移動應用分析系統中，通過SDK（軟件開發工具包）可以采集應用的名稱、使用時間、GPS信息、IP地址、手機型號、網絡類型等多個維度的信息。對此類信息進行OLAM分析，可提供靈活的多角度數據分析場景，提高商業競爭能力。例1給出一個流數據OLAM的分析場景。

例1：運營方希望能實時監控某款應用在不同人群中的活躍度，以便其能分析出核心用戶，實時調整留存和激活策略，增強其競爭力。

對于不同人群的劃分可以使用數據立方體分析，可以在多個子空間中統計相關活躍度。但是，流數據處理具有單次掃描、較低的時間和空間復雜度、適應動態變化的流速等要求，且系統挖掘時效性強，需實時返回分析結果，而事先又無法指定所需要觀察的維度組合，需要對維度組合進行全量分析，因此實時計算量巨大。

基于上述的要求，使用現有的OLAM方法，把數據倉庫中的記錄通過OLAP投射到不同空間生成數據單元，再通過多角度綜合分析數據的方法[2]無法滿足上述要求，原因如下。

（1）數據量大

和傳統的數據倉庫相比，移動互聯網下的流式數據是海量的且增長迅速。傳統OLAP工具在存儲空間和計算效率上都無法滿足實時性能要求。

（2）數據動態性強

傳統OLAP方法，通過對數據立方體建立物化視圖（materialized view）可以預計算部分結果，從而提高實時查詢的效率，達到空間和效率上的平衡[3]，如QC-Tree、侏儒立方體等方法[4]。但流式數據是動態可變的，因此對于數據無法做靜態的預處理，必須要實時計算。

（3）數據時效性強

傳統OLAP框架處理的是歸檔數據，對數據的實效性要求不高。而數據流內含的時態特征表明，數據是有生命周期的。用戶往往只對特定時間窗口內的數據感興趣，而忽略窗口外的數據。如例1中，只需要統計分析促銷活動過程中的最近的數據，而忽略其他歷史歸檔數據。

由此可見，傳統的OLAM方法不能很好地處理數據流。而其他基于數據抽樣[5,6]和基于數據壓縮[4]兩種流式數據處理方法受限于計算能力和存儲空間的大小，只在整體空間或幾個分組中進行數據分析，如stream[7]、TelegraphCQ[8]、SMM[9]等。但它們沒有提供在任意子空間或任意層次中對數據進行分析的方案。

本文提出一種流數據立方體處理框架——sketch cube（概要立方體）。并在storm開源流處理平臺中實現。sketch cube在較小的空間中實時聚合有效數據單元信息，可滿足OLAM的分析需求，其貢獻在于以下幾點。

·提出一種可擴展的數據單元標識方法，對流數據的任意維度組合通過配對函數 （pairing function）[10]映射生成唯一標識且保證維度擴展后數據仍不沖突。

·提出一種改進概要統計模型——ACM（advanced count model），ACM根據數據分布特性和存儲模型的設計特征，可有效裁剪長尾的數據單元，以提高計算能力和存儲空間效率，同時可改進數據單元統計精確度。

·提出一種基于時間窗口的倒排檢索模型，可支持任意時間粒度的組合。在類線性存儲空間中存放所有有效數據單元的統計信息，最大限度地保證了信息的完整性。

·從理論上給出sketch cube的適用場景和準確率范圍。通過storm實現sketch cube功能，且在海量真實數據流下測試模型在不同參數和時間片長度下的吞吐量和準確率。理論分析和實驗證明sketch cube的查詢效率高且能支持流式數據下的立方體全量分析。

本文研究主要結合傳統的OLAP方法和流數據處理方法。

已有的對傳統OLAP的擴展研究如（參考文獻[11～13]）引入了文本屬性，提出文本立方體（text cube）概念。Lin C等[13]提出基于關鍵詞的數據立方體查詢，對數值和文本維度分別建立層次結構，通過倒排索引檢索出相應的數據單元。在此基礎上，Ding B等[12]提出基于關鍵詞的top-k數據單元查詢問題，通過對關鍵詞的信息檢索（information retrieval）度量，提取出與關鍵詞最相關的k個數據單元。與此相反，參考文獻[11]提出了數據單元主題判定問題，對給定層次的數據單元結合自然語言模型，判斷其所屬的主題和相關概率。

流數據結合OLAP操作產生了流立方體（stream cube）的概念。參考文獻[4]使用傾斜時間框架（tilted time framework）管理數據，使用線性回歸函數對流數據在不同維度上進行壓縮。但是該方法物化數據帶有主觀性，會丟失部分信息。同時在上下層節點合并時需要頻繁更新head表，更新速度較慢。文本流數據立方體（如Liu X等[14]）通過Twitterstream數據，建立熱點圖和情感圖等應用。該方法雖然使用時間序列分析，但還是把信息看成靜態地存放在數據倉庫中而進行分析。其他的流數據分析方法，如抽樣方法[6,15]，通過建立不同的分布概率函數 （probability distribution function,PDF）對異構源數據進行抽樣和語義分析，獲得不同的權重，通過樣本值的上下限來估計實際的聚合值。方法依賴于樣本的采集和分布情況，因此對于錯誤率無法進行有效的控制。參考文獻[16]的方法則使用壓縮策略，通過對數據特征分析，只保留其主要元素，而過濾其他元素。但它們把數據看成整體，挖掘不同數據流和不同時間段之間的關聯關系，而不是有層次的可以進行OLAP操作的模型。

此外，計數型散列技術統計數據的方法有 na觙ve counting bloom filter （NCBF）、d-left counting bloom filter（dlCBF） 和 binary shrinking d-left counting bloom filter（BSdlCBF）等[17]。在此基礎上，概要技術[18,19]可在二階矩陣大小空間內保存流數據，把N個輸入元素壓縮在lb N的存儲空間中。

2 問題描述

2.1 基本概念

定義1 （多維數據流模型 （multi-attribute stream data model，MSDM））定義某時間點上的數據流記錄。MSDM為一個二元組結構（S,T），其中，S為多維度數據模型S=（A0,A1,…,Ai:M），Ai表示標準屬性，M為度量維度，T為某個時間點。

如 ((Wi-Fi,hz,Samsung∶1)，20140510081559) 中 ，S=(Wi-Fi,hz,Samsung∶1) 為 維 度 模 型 ，hz表 示 “杭 州 ”，20140510081559為時間點，1為度量值。

定義2 （流立方體）表示給定一個時間段內的MSDM，按不同的維度構建的一個數據立方體stream cube=(A1,A2,…,An,M,T)。對于stream cube中的每條數據r=(a1,a2,…,an,m,t)，其中 r[Ai]=ai∈Ai，ai為屬性 Ai的值 ，m 為度量值。對于時間維度T有ti-1

如例1中，給定時間間隔為5 min，在該時間段內收集的所有數據產生的數據立方體，即該時間段內的流立方體。

定義3 （祖先單元和后代單元）對于流立方體中的數據單元Cm和Cn，定義*表示該維度折疊且計算不考慮，則Cm是Cn的祖先（Cn是Cm的后代）可表示為：

記為Cn[t]奐Cm[t]，即兩個數據單元之間的時間相同，祖先單元至少在一個維度上包含子孫單元且在其他所有維度上和子孫單元的值相等。

對于給定的流數據單元D0=((Wi-Fi,hz,Samsung),20140510081559)的父節點有如下7個：

上述例子中沒有顯示數據單元的度量值M，祖先單元的度量值可以由其子孫單元的度量值通過聚合操作而計算得出。聚合操作可以分為分布型（distributive）、代數型（algebraic）和整體型（holistic）3 類[20]。

2.2 流數據立方體問題描述

在一組給定的持續的MSDM中，按時間窗口大小，劃分出不同的數據片段，按照其維度生成流數據立方體。流數據立方體實時提供了清潔、有組織和匯總的數據，因此可以在不同粒度父子數據單元中分析挖掘。通過和流數據框架的結合，大大增強探索式數據挖掘能力和靈活性。如例1所示，可以滿足實時的、全量的多層次數據挖掘的需求。

3 sketch cube框架結構

本節給出構造sketch cube框架所需的主要部件：數據單元標識算法及其改進模型、流數據立方體存儲結構和裁剪模型、時間窗口索引等。

3.1 數據單元標識算法

流數據立方體產生了海量的維度組合，即數據單元，這些數據單元中的不同屬性值包含多種類型，有連續型、離散數值型、字符型等。需要對這些屬性值進行字典化處理，并給每個數據單元一個唯一的標識，用于后續計算。

數據單元標識（data cell identifier，DCI）算法的功能就是把不同的維度組合映射成唯一整數，且算法支持維度的擴展，即新增維度或修改維度值都不會與原有映射值沖突。在流數據R=(A1,A2,…,An,M)中，|Ai|表示第i維的基數。使用兩個步驟進行數據單元標識。

（1）由于維度值的多樣性，需要先把記錄R的維度Ai映射成連續的自然數，即：

（2）在步驟（1）中產生 n 個自然數 Ni，形成集合 S，使用配對函數對S中的任意非空子集生成唯一的自然數。

配對函數的定義為把兩維度元組映射成一維度元組的函數N×N→N。它是一個雙射函數，其單調遞增的特性如式（3）所示，保證其不會重復。

對于高于兩維度的元組可以使用嵌套模式進行，文本使用康托爾配對函數（Cantor tuple function），如圖1和式（4）所示，按維度順序進行嵌套配對，把中間結果當成下一步操作的輸入。

圖1 有限元素算術圖

3.1.1 改進配對函數

康托爾配對函數用嵌套方式生成映射值，當元組維度較高或者某些維度基數較大時，會導致巨大的映射值。提出改進配對函數（advanced pairing function，APF）模型，其思想是在不改變計算模型的同時，產生較小的映射值。其理論依據如下：

·在數據立方體中，維度的順序與數據單元描述無

關，即數據單元(A1,A2)=(A2,A1)；

·在嵌套方法中，越早進入計算的數值參與循環的次數越多，對結果值大小的影響越大。

APF 模型定義如式（5）和式（6）所示。

對給定屬性Ai：

如圖1所示，嵌套計算從尾部開始，式（5）表示輸入配對函數的維度順序由維度基數大小決定，基數大的維度靠前。式（6）表示把維度值映射成連續自然數時，對出現頻率高（freq值大）的維度值賦給小自然數。維度基數的大小和維度值的頻率可以由統計或經驗獲得。如本文實驗中，手機操作系統維度基數小于城市維度基數，Android機型多于蘋果機型。使用APF模型可以有效地減少大數值在遞歸中的計算次數，達到最終控制輸出映射值的目的。

3.1.2 算法步驟

結合APF模型，給出算法1數據單元標識（DCI）算法的步驟。DCI算法先把流數據中每條記錄的維度值映射成由小到大的自然數（行①），通過遞歸函數得到與之相關的所有維度組合（行②），并使用康托爾配對函數獲得所有組合唯一標識（行③～⑦）。

算法1 數據單元標識算法

輸入：流數據記錄r=(a1,a2,…,ai,m,t)

輸出：r所有維度組合標識

①根據APF模型中式（5）和式（6），將記錄r中的維度映射成(n1,n2,…,nn)

②set=(n1,n2,…,ni)的所有組合，size of=2i。

③set←{}；

④for all x∈{}do

⑤←pairing function(x)；

⑥end for

⑦return；

3.2 存儲結構描述

提出一種通過sketch技術對流數據單元進行統計的方法，首先給出模型所需的獨立散列族定義。

3.2.1 獨立散列族定義

定義4 （均勻散列函數）對于給定的元素集合U通過散列函數h(x)投射到n個元素中，對每個j=1,…,n，給定x∈U，有 P[h(x)=j]=1/n，h(x)則為均勻散列函數。

定義5 （互相獨立散列函數族）在F散列族中任意選擇a、b兩個隨機函數，如果且則F為相互獨立的散列函數族。

3.2.2 計數最小概要模型

計數最小概要（count-min sketch,CM sketch）模型[10]是一個使用相互獨立散列函數族函數統計流數據元素出現頻率的模型。其結構如圖2所示，是一個d×w的二維數組。

圖2 CM sketch存儲結構

其中，d表示相互獨立散列族函數的個數，w表示每個散列函數的映射范圍，如式（7）所示：

顯然，n個元素可以表示2n個兩兩組合元素集合。因此，設計包含d個函數的相互獨立散列函數族，只需用個不同元素，如式（8）所示：

從SeedSet中隨機取不同的元素a和b，定義散列函數方法如式（9）所示：

由ha,b(z)產生的散列值是變長的，式（10）把值規約到w大小的數組中。

3.2.3 CM sketch效率

對于第t次到達的元素c，計數最小概要模型更新操作如式（11）所示：

即使用不同散列函數找到存儲結構中的下標位置，并添加相應值，其更新時間復雜度為

統計元素ai在CM sketch中的估計值a^i的操作如式（12）所示：

即通過散列函數族中的每個函數計算該元素在對應數組中的下標值，獲得所有可能值中的最小值即該元素的估計值，其查詢時間復雜度為O(1)。

流數據有收款機模型（cash register model）和十字轉門模型（turnstile model）兩種模型。計數最小概要模型只支持收款機模型，即統計值只能遞增，因此基于此的sketch cube只支持分布型聚合操作。對于(A1,A2,…,An)數據立方體，所有數據單元個數則 sketch cube模型的壓縮率P為式（13）所示：

3.2.4 模型精度和前提條件

式（14）給出了預測元素ai統計值的偏差范圍，即預測統計值a^i小于實際值ai+綴||a||的概率為1-δ，可以根據元素多樣性和期望精確度調整綴和δ，進而調整存儲模型中的w和d值。

計數最小概要模型是一個數據敏感模型，對于偏斜數據（skew data）的支持較好（Zipfian參數 1

3.2.5 計數平均最小概要模型

對于分布較為均勻的數據集，不同元素之間的沖突影響較大，可使用計數平均最小概要（countmean min sketch，CMM sketch）統計個數。CMM sketch假設元素均勻分布在散列數組中，則對于元素ct的噪音因子定義如式（15）所示：

元素的預測值需要減去噪音因子，元素概要預測值返回結果取各散列數組中的值的中位數，如式（16）所示：

使用上述哪種模型進行統計，由流數據分布特征和業務需求而定。在本文實驗中，由于數據單元標識產生的維度組合值是偏斜的，因此采用計數最小概要模型。

3.3 裁剪模型

由數據單元標識模型產生的維度組合是冪級增長的，如給定n維記錄r=(a1,a2,…,an,m,t)可以產生2n種維度的組合。隨著維度數量增加，產生的數據單元數量是巨大的。海量的維度組合會導致計數最小概要模型的沖突率變大，影響精確度。因此，需要對維度組合進行裁剪。

在數據立方體不同聚合操作類型中，對分布類型的操作如sum和count，祖先單元（低維數據單元）聚合了其下的所有后代單元（高維數據單元）的值。由此可得后代數據單元的上限（up bound）和下限（low bound）,從而可以推理出祖先單元值的范圍（up bound-low bound），如式（17）所示：

其中，祖先單元X可以由最小單元Xi集合組成MSP（most specific partition）[13]。對于數據單元X下的任意子空間g的上下限為式（18）所示：

因計數最小概要模型適合于數據濃度大的元素（如大于閾值τ）。如圖3所示，結合式（18），數據單元間的包含關系在count操作中體現出單調性，即Cac[count]>τ→Ca[count]>τ,Cc[count]>τ。其他較復雜代數聚合操作如avg的上下限不等式在參考文獻[13]中有所定義。

裁剪規則：對于分布型聚合操作，如祖先單元的測量值小于閾值，則所有它的后代單元的測量值必定小于閾值，因此對于計數最小概要模型可以裁剪掉所有后代單元。

3.4 改進統計模型

由于sketch cube使用計數最小概要模型，針對分布型聚合操作，結合裁剪規則，提出改進統計模型（ACM）。模型通過預測單維數據單元的測量值，達到減少維度組合的目的。如果測量值小于閾值，可以刪除所有包含該維度值的子孫單元。如在記錄r=(a,b,c)中，若 Ca[count]<τ，則[count]<τ。對于n維度的流數據中，先進行n次單維度統計，假設有k個單維數據單元測量值小于閾值，則可以裁剪的維度為2k，在對于每條流數據中可減少統計操作2k-n次。因為流數據中的維度值往往是稀疏的，因此裁剪模型可以排除大多數的維度組合。如果一維裁剪模型的裁剪效果不佳，可以使用二維或高維裁剪模型，方法類似。算法2結合裁剪方法的維度生成規則。維度裁剪規則如圖3所示。

圖3 維度裁剪規則

算法2 改進統計模型

輸入：流數據記錄 r=(a1,a2,…,ai,m,t)，τ

輸出：r所有維度組合標識。

①set<1-DCounter>←{}；

②<1-DCounter>←Cak[Count]>τ,1≤k≤i；

③(a1,a2,…,aj)←(a1,a2,…,ai)<1-DCounter>；

④(a1,a2,…,aj)→(n1,n2,…,nj)

⑤set=(n1,n2,…,nj)的所有組合；

⑥set←{}；

⑦for all x∈{}do

⑧←Pairing Function(x)；

⑨end for

⑩return；

本文使用ACM(m)表示模型取每個維度上頻率最高的m個維度值進行組合，可以減少計算模型的復雜度和存儲的空間，且能保證最后的高頻數據單元不會被裁剪掉。實驗給出了使用ACM模型在不同m參數值下的優化效率。

3.5 時間序列索引描述

流數據具體有內在時序性，對流數據挖掘用傾斜時間窗口（tilted-time window，TTW）[23]在不同時間粒度（multiple time granularities）上進行分析。如圖4所示，sketch cube按時間片段對元素組合進行統計把結果放入計數最小概要模型。sketch cube設計的存儲結構可支持任意時間粒度的組合，其合并計算式如式（19）所示：

對于給定散列函數族，相同維度組合在不同時間中的映射地址相等，可單次掃描小顆粒時間累加得到大顆粒時間度量值。

圖4 時間窗口聚合操作

4 實驗結果與分析

目前已有流處理框架都是先存儲數據片段再進行實時的OLAP操作，和文本所提實時計算和預存儲模型的sketch cube不同。因此本文主要通過如下3個方面驗證方法的有效性和正確性。

·通過真實移動應用日志記錄分析場景進行實驗。分析sketch cube框架在不同時間窗口、不同裁剪模型參數和不同存儲模型大小下的正確率、剪枝能力、框架吞吐效率；驗證參數之間的影響和整體框架的有效性。

·理論分析和比較sketch cube在存儲空間上和其他存儲模型的差異。

·描述使用storm開源流框架搭建sketch cube的實現方式，并給出一個應用場景。

4.1 實驗環境和數據描述

實驗機器選擇4臺Dell服務器，16核IntelXeon 2.27 GHz，內存為32 GB，硬盤為4 TB，操作系統為Cenos 6.3，Java版本為JDK7。因為系統每秒接收流數據在1萬條左右，采用Kafka和storm框架對數據進行處理，存儲模型保存在MongoDB中。

數據集合：測試數據集來源于真實的移動嵌入式SDK中采集的應用記錄，每條記錄包含56個維度數值。本實驗選擇其中8個有代表性的維度進行OLAP統計，使用5%的均勻抽樣（uniform sampling）方法運行 1 h，其含義和維度值的基數見表1。

表1 移動數據信息結構

對上述8個維度進行全立方體組合可得超過1017個數據單元。但通過分析可得，數據單元的分布是稀疏且偏斜的。在不同大小的時間窗口中，對維度組合的分布進行Zipfian的計算結果見表2。可得維度組合結果是偏斜的，因此，本實驗數據符合使用sketch cube框架的條件。

表2 抽樣移動數據分布

表2還表明數據是線性增加的，維度組合數量（DCIsize）隨時間增加而趨于穩定，而偏斜因子和時間窗口長短無關。

表3給出了實驗涉及參數的取值范圍和缺省值。對于sketch cube所涉及的散列函數使用MurmurHash V3產生d個相互獨立的散列族，時間窗口以20 min為基本單位，ACM選擇m大小的裁剪模型，且在多組產生結果中進行分析和比較。

表3 實驗參數

表4給出了ACM模型在3個不同參數下和全量計算模型（full count model,FCM）在包括吞吐量、裁剪能力和模型準確率方面的比較結果。

4.2 sketch cube計算性能

本節討論ACM(m)裁剪方法在不同參數m下對sketch cube模型的剪枝能力。FCM表示統計全部維度組合，取m=(10,20,30,40,50)5個值，在3個不同時間長度中觀察ACM的輸出變化。如圖5所示，ACM模型在不同參數下都具有10倍左右的裁剪能力且很顯然參數值越小，保留的數據單元越少，裁剪能力越強。

表4 部分實驗結果

圖5 ACM剪枝實驗

接著，需要測試剪枝模型的有效性和可用性，即裁剪后的模型是否仍然可以滿足需求，而不會丟失很多有效數據。實驗取20 min數據，分別統計ACM不同參數下提取DCI數量和裁剪后維度組合數量。如圖6所示，ACM模型參數從10增加到50過程中，雖然DCI的數量有所提高，即計算得到的數據單元數量有明顯的增加，但是裁剪后維度組合出現次數卻基本相等。這說明數據是偏斜的，大量的高頻數據反復出現，而長尾的數據只有少量出現。因此，ACM（10）基本包含了所有高頻率的組合，在后續的框架構建和查詢中，筆者使用ACM（10）作為裁剪模型。

圖6 ACM裁剪模型效率

4.3 存儲空間和誤差

使用計數最小概要模型的sketch cube中保存的元素統計數據值要大于元素實際值，本實驗使用平均百分比誤差（mean percentage error，MPE）統計計數的準確率。計算式如下：

其中，at是實際值，ft是預測值，n是測試數據數量。

圖7展示sketch cube中的存儲空間大小和ACM參數對MPE的影響。取10 min數據，在不同存儲寬度中比較4類模型的MPE值。ACM（m）中m越小，裁剪能力越強，模型準確率越高。隨著存儲空間的增大(即w參數的變大)，所有模型的準確率都有所提高，這是因為存儲空間的增加可以減少散列的碰撞概率，從而提高模型的準確率，但ACM整體準確率在任意存儲模型下都較FCM有明顯提高。

圖7 w和ACM(n)對MPE的影響

圖8 顯示存儲空間、結果集大小和MPE之間的關系。top-N從大到小排序，從橫軸看，頻率越高的數據單元，其MPE值越小，準確率越高。如在1 021寬度的存儲模型中，ACM （10）模型對前20的高頻數據單元的統計錯誤率為1%左右，而FCM的錯誤率超過20%。隨著top-N的變大，MPE值也上升，說明sketch cube產生的數據單元是偏斜的。在不同的系統應用中，可以選擇合適的存儲空間大小和計算結果大小，如需要計算的top-N較大，則需要使用較小的ACM和較大的存儲空間w。

4.4 吞吐能力和計算時間比較

接著計算模型的吞吐計算能力，因為運行時間受分布式框架節點數據和數據傳輸影響較大，因此吞吐能力測試在單節點上進行。取170 880條數據，在單節點中測量DCI計算時間和sketch cube計算時間。DCI時間表示計算數據單元標識集合的時間，sketch時間表示計算存入二維數組的偏移值的時長。測試取w=1 021。如圖9所示，折線表示DCI集合的大小變化。從DCI運行時間和DCI集合變化曲線看，兩者之間成正比關系，即模型的裁剪能力越強，DCI集合越小，DCI運行時間越短。對于任意模型，DCI運行時間遠大于sketch計算時間。這些結論將被用于sketch cube模型的實現中。

圖8 w和ACM(m)對MPE的增長趨勢

圖9 不同模型的運行時間

4.5 實時挖掘效率

上述實驗過程把每條記錄可能的維度組合保存在類線性空間中。本實驗將統計數據存儲于MongoDB中，使用應用ID和時間窗口對數據檢索。通過時間序列索引模型可知sketch cube支持任意時間窗口的組合。實驗取3個不同的應用做實時查詢，其效率分析見表5。

表5 查詢效率分析

每個應用分別以10、20、30 min為長度，隨機選擇高維度值產生數據單元，進行OLAP查詢。數據大小表示查詢所涉及應用的日志數據大小。運行時間包括用時間序列索引找到相關的存儲單元，通過數據單元標識模型產生唯一自然數標識，使用最小計數模型找到該數據單元的估計值所需的時間總和。從運行時間看，因為數據已經做了索引和統計，時間片長短和數據量大小對查詢時間變化較小。同時查詢時間都在毫秒級，因此可以滿足實時查詢的需求。

4.6 空間效率

由于目前已有的對流數據的OLAP框架都是基于先存儲數據，再進行分析的過程，和本文所述的實時統計框架有所不同。因此，本節主要理論分析數據在HashMap和sketch cube中的存儲空間對比。假設，所有數據存儲的基本單元都是整型，則HashMap的結構可以表示為HashMap，key為維度計數器產生的數據單位標識，value為數據單元的統計個數。因此，對于每個數據單元需要2個Integer大小空間存儲，整體所需存儲空間為2×DCI個Integer。而使用sketch cube的存儲大小固定為w×d個Integer。例如，在表4中可得，ACM(10)在 20 min產生的 DCI為 15 896，則 HashMap的空間為 15 896×2=31 792個Integer，本實驗中 sketch cube大小為 1 021×5=5 105個Integer。因此，壓縮率為5 105/31 792=0.16。同理，可得ACM（30）和 ACM（50）壓縮率分別為 0.028和 0.022。由此可得，隨著ACM裁剪效率的下降，需要保存的數據單元數量增加，壓縮率會明顯降低，空間使用效率提高。

5 sketch cube平臺構建過程

5.1 系統結構

本節主要介紹使用storm開源流框架搭建sketch cube的過程。storm框架使用拓撲來描述不同計算節點之間的關系，根據前文的模塊定義，把sketch cube的不同模塊功能映射到storm的bolt中，且需要根據計算節點之間的I/O吞吐率和CPU計算量，調整節點的并發度，以達到系統整體的平衡。系統部署在第4.1節描述的4臺服務器中，其結構如圖10所示。

圖10 storm實現sketch cube框架

系統分為3個部分，數據源負責收集相關多維度流數據信息，并保存在Kafka框架中；storm框架使用5個不同的計算節點，分別為輸入數據接收、字典化處理、DCI計算，存儲節點計算和存儲節點。處理后的數據被保存在MongoDB數據庫中。實時挖掘層（mining layer）從MongoDB中獲得壓縮后的數據單元統計值，并且進行相關在線分析模塊（OLAM）操作得到結果返回給用戶。

5.2 相關示例

對例1中的場景，給定應用名稱和時間片段，實時統計不同的數據單元下的度量值，本實驗使用count計算數據單元的大小，最后選擇和該時段這個應用最相關的top-50個數據單元。輸出所在數據單元的維度值。對于給定應用appi，對于數據單元c的相關度(correlation)可以用式（21）所示：

其中，m表示數據單元度量值。

如對于流數據立方體c=((Wi-Fi,hz,Samsung),20140510081559)，包含應用A的條數為200條，應用B為300條，則

對上述top-50的數據單元相關屬性值進行統計，按每個屬性值出現次數多少排序，并產生如圖11所示的標簽云圖像。從圖11可得，不同時間窗口下的標簽云發生變化，這表明不同時間段的應用受眾群體在發生變化。該類圖像報表可以更好地幫助用戶實時定位目標客戶。

圖11 標簽云推薦

6 總結和展望

本文研究一種對海量流數據進行OLAM操作的框架sketch cube：

·提出數據單元標識模型及其改進算法；

·引入計數最小概要模型保存統計結果，并給出其適用場景；

·提出基于上下限的數據單元裁剪方法，提高存儲效率和準確率；

·基于傾斜時間窗口的索引模型可快速計算任意時間片中的統計結果；

·真實數據集實驗中，比較了相關參數對模型的影響，體現模型的優越性和可用性。

sketch cube只支持流數據分布型的聚合操作，在下一步工作中，將研究較為復雜的代數型和整體型聚合操作在流數據sketch cube模型中的應用。同時把計算過程中的性能瓶頸通過合理設計拓撲結構分散到不同機器節點中，以提高流數據的處理能力和穩定性。

1 Aggarwal C C.An Introduction to Data Streams.Data Streams.Springer US,2007

2 Hellerstein J M,Haas P J,Wang H J.Online aggregation.ACM SIGMOD Record,1997,26(2):171～182

3 Zhang X,Chou P L,Dong G.Efficient computation of iceberg cubes by bounding aggregate functions.IEEE Transactions on Knowledge and Data Engineering,2007,19(7)

4 Chen Y,Do ng G,Han J,et al.Multi-dimensional regression analysis of time-series data streams.Proceedings of the 28th International Conference on Very Large Data Bases,VLDB Endowment,Hong Kong,China,2002:323～334

5 胡文瑜，孫志揮，吳英杰.數據挖掘取樣方法研究.計算機研究與發展,2009,48(1)：45～54

6 De Rougemont M,Cao P T.Approximate answers to OLAP queries on streaming data warehouses.Proceedings of the Fifteenth International Workshop on Data Warehousing and OLAP,Maui,Hi,USA,2012:121～128

7 Babcock B,Shinath B,Mayur D,et al.Models and issues in data stream systems.Proceedings of the 21st ACM Symposium on PrinciplesofDatabase Systems,Madison,Wiscomsin,USA,2002:1～16

8 Chandrasekaran S,Cooper O,Deshpande A.TelegraphCQ:continuous dataflow processing for an uncertain world.Proceedings of the Conf on Innovative Data Systems Research,Asilomar,CA,USA,2003

9 Hetal T,Nikolay L,Hamid M,et al.SMM:a data stream management system for knowledge discovery.Proceedings of International Conference on Data Engineering, Hannover,Germany,2011:757～768

10 Rosenberg A L.Efficient pairing functions-and why you should care.International Journal of Foundations of Computer Science,2003,14(1):3～17

11 Zhang D,Zhai C,Han J,et al.Topic modeling for OLAP on multidimensional text database:topic cube and its applications.Stat Anal Data Min,2009,2(56):378～395

12 Ding B,Zhao B,Lin C,et al.Topcells:keyword-based search of top-k aggregated documents in text cube.Proceedings of International Conference on Data Engineering (ICDE),Long Beach,USA,2010:381～384

13 Lin C,Ding B,Han J,et al.TextCube:computingirmeansures for multidimensional text database analysis.Proceedings of the 8th IEEE International Conference on Data Mining(ICDM),2008:905～910

14 Liu X,Tang K Z,Hancock J,et al.A text cube approach to human,social and cultural behavior in the Twitter stream.LNCS 7812,2013:321～330

15 Cuzzocrea A.Retrieving accurate estimates to OLAP queries over uncertain and imprecise multidimensional data streams.Proceedings of the 23rd International Conference on SSDBM,Portland,OR,USA,2011

16 Aggarwal C C.Managing and Mining Sensor Data.New York:Springer US,2013

17 張進，鄔江興，劉勤讓.4種技術型Bloom Filter的性能分析與比較.軟件學報，2010，21(5):1098～1114

18 Cormode G,Hadjieleftheriou M.Finding frequent items in data streams.Proceedings of the VLDB Endowment,2008,1(2):1530～1541

19 Considine J,Hadjieleftheriou M,Li F,et al.Robust approximate aggregation in sensor data management systems. ACM Transactions on Database Systems(TODS),2009,34(1)

20 Han J,Kamber M,Pei J.Data Mining Concepts and Techniques.Elsevier Ltd,2012

21 Cormode G,Muthukrishnan S.An improved data stream summary: the count-min sketch and its applications. J Algorithms,2005,55(1):58～75

22 Cormode G,Muthukrishnan S.Summarizing and mining skewed data streams.Proceedings of SDM,Trondheim,Normay,2005

23 Giannella C,Han J,Pei J,et al.Mining frequent patterns in data streams at multiple time granularities.Next Generation Data Mining,2003(212):191～212