金蒼宏 ，劉澤民 ，吳明暉 ，應(yīng) 晶 ,

（1.浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310027；2.浙江大學(xué)城市學(xué)院 杭州 310015）

1 引言

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

例1：運(yùn)營(yíng)方希望能實(shí)時(shí)監(jiān)控某款應(yīng)用在不同人群中的活躍度，以便其能分析出核心用戶，實(shí)時(shí)調(diào)整留存和激活策略，增強(qiáng)其競(jìng)爭(zhēng)力。

對(duì)于不同人群的劃分可以使用數(shù)據(jù)立方體分析，可以在多個(gè)子空間中統(tǒng)計(jì)相關(guān)活躍度。但是，流數(shù)據(jù)處理具有單次掃描、較低的時(shí)間和空間復(fù)雜度、適應(yīng)動(dòng)態(tài)變化的流速等要求，且系統(tǒng)挖掘時(shí)效性強(qiáng)，需實(shí)時(shí)返回分析結(jié)果，而事先又無法指定所需要觀察的維度組合，需要對(duì)維度組合進(jìn)行全量分析，因此實(shí)時(shí)計(jì)算量巨大。

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

（1）數(shù)據(jù)量大

和傳統(tǒng)的數(shù)據(jù)倉(cāng)庫(kù)相比，移動(dòng)互聯(lián)網(wǎng)下的流式數(shù)據(jù)是海量的且增長(zhǎng)迅速。傳統(tǒng)OLAP工具在存儲(chǔ)空間和計(jì)算效率上都無法滿足實(shí)時(shí)性能要求。

（2）數(shù)據(jù)動(dòng)態(tài)性強(qiáng)

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

（3）數(shù)據(jù)時(shí)效性強(qiáng)

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

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

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

·提出一種可擴(kuò)展的數(shù)據(jù)單元標(biāo)識(shí)方法，對(duì)流數(shù)據(jù)的任意維度組合通過配對(duì)函數(shù) （pairing function）[10]映射生成唯一標(biāo)識(shí)且保證維度擴(kuò)展后數(shù)據(jù)仍不沖突。

·提出一種改進(jìn)概要統(tǒng)計(jì)模型——ACM（advanced count model），ACM根據(jù)數(shù)據(jù)分布特性和存儲(chǔ)模型的設(shè)計(jì)特征，可有效裁剪長(zhǎng)尾的數(shù)據(jù)單元，以提高計(jì)算能力和存儲(chǔ)空間效率，同時(shí)可改進(jìn)數(shù)據(jù)單元統(tǒng)計(jì)精確度。

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

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

本文研究主要結(jié)合傳統(tǒng)的OLAP方法和流數(shù)據(jù)處理方法。

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

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

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

2 問題描述

2.1 基本概念

定義1 （多維數(shù)據(jù)流模型 （multi-attribute stream data model，MSDM））定義某時(shí)間點(diǎn)上的數(shù)據(jù)流記錄。MSDM為一個(gè)二元組結(jié)構(gòu)（S,T），其中，S為多維度數(shù)據(jù)模型S=（A0,A1,…,Ai:M），Ai表示標(biāo)準(zhǔn)屬性，M為度量維度，T為某個(gè)時(shí)間點(diǎn)。

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

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

如例1中，給定時(shí)間間隔為5 min，在該時(shí)間段內(nèi)收集的所有數(shù)據(jù)產(chǎn)生的數(shù)據(jù)立方體，即該時(shí)間段內(nèi)的流立方體。

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

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

對(duì)于給定的流數(shù)據(jù)單元D0=((Wi-Fi,hz,Samsung),20140510081559)的父節(jié)點(diǎn)有如下7個(gè)：

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

2.2 流數(shù)據(jù)立方體問題描述

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

3 sketch cube框架結(jié)構(gòu)

本節(jié)給出構(gòu)造sketch cube框架所需的主要部件：數(shù)據(jù)單元標(biāo)識(shí)算法及其改進(jìn)模型、流數(shù)據(jù)立方體存儲(chǔ)結(jié)構(gòu)和裁剪模型、時(shí)間窗口索引等。

3.1 數(shù)據(jù)單元標(biāo)識(shí)算法

流數(shù)據(jù)立方體產(chǎn)生了海量的維度組合，即數(shù)據(jù)單元，這些數(shù)據(jù)單元中的不同屬性值包含多種類型，有連續(xù)型、離散數(shù)值型、字符型等。需要對(duì)這些屬性值進(jìn)行字典化處理，并給每個(gè)數(shù)據(jù)單元一個(gè)唯一的標(biāo)識(shí)，用于后續(xù)計(jì)算。

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

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

（2）在步驟（1）中產(chǎn)生 n 個(gè)自然數(shù) Ni，形成集合 S，使用配對(duì)函數(shù)對(duì)S中的任意非空子集生成唯一的自然數(shù)。

配對(duì)函數(shù)的定義為把兩維度元組映射成一維度元組的函數(shù)N×N→N。它是一個(gè)雙射函數(shù)，其單調(diào)遞增的特性如式（3）所示，保證其不會(huì)重復(fù)。

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

圖1 有限元素算術(shù)圖

3.1.1 改進(jìn)配對(duì)函數(shù)

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

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

關(guān)，即數(shù)據(jù)單元(A1,A2)=(A2,A1)；

·在嵌套方法中，越早進(jìn)入計(jì)算的數(shù)值參與循環(huán)的次數(shù)越多，對(duì)結(jié)果值大小的影響越大。

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

對(duì)給定屬性Ai：

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

3.1.2 算法步驟

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

算法1 數(shù)據(jù)單元標(biāo)識(shí)算法

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

輸出：r所有維度組合標(biāo)識(shí)

①根據(jù)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 存儲(chǔ)結(jié)構(gòu)描述

提出一種通過sketch技術(shù)對(duì)流數(shù)據(jù)單元進(jìn)行統(tǒng)計(jì)的方法，首先給出模型所需的獨(dú)立散列族定義。

3.2.1 獨(dú)立散列族定義

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

定義5 （互相獨(dú)立散列函數(shù)族）在F散列族中任意選擇a、b兩個(gè)隨機(jī)函數(shù)，如果且則F為相互獨(dú)立的散列函數(shù)族。

3.2.2 計(jì)數(shù)最小概要模型

計(jì)數(shù)最小概要（count-min sketch,CM sketch）模型[10]是一個(gè)使用相互獨(dú)立散列函數(shù)族函數(shù)統(tǒng)計(jì)流數(shù)據(jù)元素出現(xiàn)頻率的模型。其結(jié)構(gòu)如圖2所示，是一個(gè)d×w的二維數(shù)組。

圖2 CM sketch存儲(chǔ)結(jié)構(gòu)

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

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

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

由ha,b(z)產(chǎn)生的散列值是變長(zhǎng)的，式（10）把值規(guī)約到w大小的數(shù)組中。

3.2.3 CM sketch效率

對(duì)于第t次到達(dá)的元素c，計(jì)數(shù)最小概要模型更新操作如式（11）所示：

即使用不同散列函數(shù)找到存儲(chǔ)結(jié)構(gòu)中的下標(biāo)位置，并添加相應(yīng)值，其更新時(shí)間復(fù)雜度為

統(tǒng)計(jì)元素ai在CM sketch中的估計(jì)值a^i的操作如式（12）所示：

即通過散列函數(shù)族中的每個(gè)函數(shù)計(jì)算該元素在對(duì)應(yīng)數(shù)組中的下標(biāo)值，獲得所有可能值中的最小值即該元素的估計(jì)值，其查詢時(shí)間復(fù)雜度為O(1)。

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

3.2.4 模型精度和前提條件

式（14）給出了預(yù)測(cè)元素ai統(tǒng)計(jì)值的偏差范圍，即預(yù)測(cè)統(tǒng)計(jì)值a^i小于實(shí)際值ai+綴||a||的概率為1-δ，可以根據(jù)元素多樣性和期望精確度調(diào)整綴和δ，進(jìn)而調(diào)整存儲(chǔ)模型中的w和d值。

計(jì)數(shù)最小概要模型是一個(gè)數(shù)據(jù)敏感模型，對(duì)于偏斜數(shù)據(jù)（skew data）的支持較好（Zipfian參數(shù) 1

3.2.5 計(jì)數(shù)平均最小概要模型

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

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

使用上述哪種模型進(jìn)行統(tǒng)計(jì)，由流數(shù)據(jù)分布特征和業(yè)務(wù)需求而定。在本文實(shí)驗(yàn)中，由于數(shù)據(jù)單元標(biāo)識(shí)產(chǎn)生的維度組合值是偏斜的，因此采用計(jì)數(shù)最小概要模型。

3.3 裁剪模型

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

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

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

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

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

3.4 改進(jìn)統(tǒng)計(jì)模型

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

圖3 維度裁剪規(guī)則

算法2 改進(jìn)統(tǒng)計(jì)模型

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

輸出：r所有維度組合標(biāo)識(shí)。

①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)表示模型取每個(gè)維度上頻率最高的m個(gè)維度值進(jìn)行組合，可以減少計(jì)算模型的復(fù)雜度和存儲(chǔ)的空間，且能保證最后的高頻數(shù)據(jù)單元不會(huì)被裁剪掉。實(shí)驗(yàn)給出了使用ACM模型在不同m參數(shù)值下的優(yōu)化效率。

3.5 時(shí)間序列索引描述

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

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

圖4 時(shí)間窗口聚合操作

4 實(shí)驗(yàn)結(jié)果與分析

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

·通過真實(shí)移動(dòng)應(yīng)用日志記錄分析場(chǎng)景進(jìn)行實(shí)驗(yàn)。分析sketch cube框架在不同時(shí)間窗口、不同裁剪模型參數(shù)和不同存儲(chǔ)模型大小下的正確率、剪枝能力、框架吞吐效率；驗(yàn)證參數(shù)之間的影響和整體框架的有效性。

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

·描述使用storm開源流框架搭建sketch cube的實(shí)現(xiàn)方式，并給出一個(gè)應(yīng)用場(chǎng)景。

4.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)描述

實(shí)驗(yàn)機(jī)器選擇4臺(tái)Dell服務(wù)器，16核IntelXeon 2.27 GHz，內(nèi)存為32 GB，硬盤為4 TB，操作系統(tǒng)為Cenos 6.3，Java版本為JDK7。因?yàn)橄到y(tǒng)每秒接收流數(shù)據(jù)在1萬(wàn)條左右，采用Kafka和storm框架對(duì)數(shù)據(jù)進(jìn)行處理，存儲(chǔ)模型保存在MongoDB中。

數(shù)據(jù)集合：測(cè)試數(shù)據(jù)集來源于真實(shí)的移動(dòng)嵌入式SDK中采集的應(yīng)用記錄，每條記錄包含56個(gè)維度數(shù)值。本實(shí)驗(yàn)選擇其中8個(gè)有代表性的維度進(jìn)行OLAP統(tǒng)計(jì)，使用5%的均勻抽樣（uniform sampling）方法運(yùn)行 1 h，其含義和維度值的基數(shù)見表1。

表1 移動(dòng)數(shù)據(jù)信息結(jié)構(gòu)

對(duì)上述8個(gè)維度進(jìn)行全立方體組合可得超過1017個(gè)數(shù)據(jù)單元。但通過分析可得，數(shù)據(jù)單元的分布是稀疏且偏斜的。在不同大小的時(shí)間窗口中，對(duì)維度組合的分布進(jìn)行Zipfian的計(jì)算結(jié)果見表2?？傻镁S度組合結(jié)果是偏斜的，因此，本實(shí)驗(yàn)數(shù)據(jù)符合使用sketch cube框架的條件。

表2 抽樣移動(dòng)數(shù)據(jù)分布

表2還表明數(shù)據(jù)是線性增加的，維度組合數(shù)量（DCIsize）隨時(shí)間增加而趨于穩(wěn)定，而偏斜因子和時(shí)間窗口長(zhǎng)短無關(guān)。

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

表3 實(shí)驗(yàn)參數(shù)

表4給出了ACM模型在3個(gè)不同參數(shù)下和全量計(jì)算模型（full count model,FCM）在包括吞吐量、裁剪能力和模型準(zhǔn)確率方面的比較結(jié)果。

4.2 sketch cube計(jì)算性能

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

表4 部分實(shí)驗(yàn)結(jié)果

圖5 ACM剪枝實(shí)驗(yàn)

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

圖6 ACM裁剪模型效率

4.3 存儲(chǔ)空間和誤差

使用計(jì)數(shù)最小概要模型的sketch cube中保存的元素統(tǒng)計(jì)數(shù)據(jù)值要大于元素實(shí)際值，本實(shí)驗(yàn)使用平均百分比誤差（mean percentage error，MPE）統(tǒng)計(jì)計(jì)數(shù)的準(zhǔn)確率。計(jì)算式如下：

其中，at是實(shí)際值，ft是預(yù)測(cè)值，n是測(cè)試數(shù)據(jù)數(shù)量。

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

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

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

4.4 吞吐能力和計(jì)算時(shí)間比較

接著計(jì)算模型的吞吐計(jì)算能力，因?yàn)檫\(yùn)行時(shí)間受分布式框架節(jié)點(diǎn)數(shù)據(jù)和數(shù)據(jù)傳輸影響較大，因此吞吐能力測(cè)試在單節(jié)點(diǎn)上進(jìn)行。取170 880條數(shù)據(jù)，在單節(jié)點(diǎn)中測(cè)量DCI計(jì)算時(shí)間和sketch cube計(jì)算時(shí)間。DCI時(shí)間表示計(jì)算數(shù)據(jù)單元標(biāo)識(shí)集合的時(shí)間，sketch時(shí)間表示計(jì)算存入二維數(shù)組的偏移值的時(shí)長(zhǎng)。測(cè)試取w=1 021。如圖9所示，折線表示DCI集合的大小變化。從DCI運(yùn)行時(shí)間和DCI集合變化曲線看，兩者之間成正比關(guān)系，即模型的裁剪能力越強(qiáng)，DCI集合越小，DCI運(yùn)行時(shí)間越短。對(duì)于任意模型，DCI運(yùn)行時(shí)間遠(yuǎn)大于sketch計(jì)算時(shí)間。這些結(jié)論將被用于sketch cube模型的實(shí)現(xiàn)中。

圖8 w和ACM(m)對(duì)MPE的增長(zhǎng)趨勢(shì)

圖9 不同模型的運(yùn)行時(shí)間

4.5 實(shí)時(shí)挖掘效率

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

表5 查詢效率分析

每個(gè)應(yīng)用分別以10、20、30 min為長(zhǎng)度，隨機(jī)選擇高維度值產(chǎn)生數(shù)據(jù)單元，進(jìn)行OLAP查詢。數(shù)據(jù)大小表示查詢所涉及應(yīng)用的日志數(shù)據(jù)大小。運(yùn)行時(shí)間包括用時(shí)間序列索引找到相關(guān)的存儲(chǔ)單元，通過數(shù)據(jù)單元標(biāo)識(shí)模型產(chǎn)生唯一自然數(shù)標(biāo)識(shí)，使用最小計(jì)數(shù)模型找到該數(shù)據(jù)單元的估計(jì)值所需的時(shí)間總和。從運(yùn)行時(shí)間看，因?yàn)閿?shù)據(jù)已經(jīng)做了索引和統(tǒng)計(jì)，時(shí)間片長(zhǎng)短和數(shù)據(jù)量大小對(duì)查詢時(shí)間變化較小。同時(shí)查詢時(shí)間都在毫秒級(jí)，因此可以滿足實(shí)時(shí)查詢的需求。

4.6 空間效率

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

5 sketch cube平臺(tái)構(gòu)建過程

5.1 系統(tǒng)結(jié)構(gòu)

本節(jié)主要介紹使用storm開源流框架搭建sketch cube的過程。storm框架使用拓?fù)鋪砻枋霾煌?jì)算節(jié)點(diǎn)之間的關(guān)系，根據(jù)前文的模塊定義，把sketch cube的不同模塊功能映射到storm的bolt中，且需要根據(jù)計(jì)算節(jié)點(diǎn)之間的I/O吞吐率和CPU計(jì)算量，調(diào)整節(jié)點(diǎn)的并發(fā)度，以達(dá)到系統(tǒng)整體的平衡。系統(tǒng)部署在第4.1節(jié)描述的4臺(tái)服務(wù)器中，其結(jié)構(gòu)如圖10所示。

圖10 storm實(shí)現(xiàn)sketch cube框架

系統(tǒng)分為3個(gè)部分，數(shù)據(jù)源負(fù)責(zé)收集相關(guān)多維度流數(shù)據(jù)信息，并保存在Kafka框架中；storm框架使用5個(gè)不同的計(jì)算節(jié)點(diǎn)，分別為輸入數(shù)據(jù)接收、字典化處理、DCI計(jì)算，存儲(chǔ)節(jié)點(diǎn)計(jì)算和存儲(chǔ)節(jié)點(diǎn)。處理后的數(shù)據(jù)被保存在MongoDB數(shù)據(jù)庫(kù)中。實(shí)時(shí)挖掘?qū)樱╩ining layer）從MongoDB中獲得壓縮后的數(shù)據(jù)單元統(tǒng)計(jì)值，并且進(jìn)行相關(guān)在線分析模塊（OLAM）操作得到結(jié)果返回給用戶。

5.2 相關(guān)示例

對(duì)例1中的場(chǎng)景，給定應(yīng)用名稱和時(shí)間片段，實(shí)時(shí)統(tǒng)計(jì)不同的數(shù)據(jù)單元下的度量值，本實(shí)驗(yàn)使用count計(jì)算數(shù)據(jù)單元的大小，最后選擇和該時(shí)段這個(gè)應(yīng)用最相關(guān)的top-50個(gè)數(shù)據(jù)單元。輸出所在數(shù)據(jù)單元的維度值。對(duì)于給定應(yīng)用appi，對(duì)于數(shù)據(jù)單元c的相關(guān)度(correlation)可以用式（21）所示：

其中，m表示數(shù)據(jù)單元度量值。

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

對(duì)上述top-50的數(shù)據(jù)單元相關(guān)屬性值進(jìn)行統(tǒng)計(jì)，按每個(gè)屬性值出現(xiàn)次數(shù)多少排序，并產(chǎn)生如圖11所示的標(biāo)簽云圖像。從圖11可得，不同時(shí)間窗口下的標(biāo)簽云發(fā)生變化，這表明不同時(shí)間段的應(yīng)用受眾群體在發(fā)生變化。該類圖像報(bào)表可以更好地幫助用戶實(shí)時(shí)定位目標(biāo)客戶。

圖11 標(biāo)簽云推薦

6 總結(jié)和展望

本文研究一種對(duì)海量流數(shù)據(jù)進(jìn)行OLAM操作的框架sketch cube：

·提出數(shù)據(jù)單元標(biāo)識(shí)模型及其改進(jìn)算法；

·引入計(jì)數(shù)最小概要模型保存統(tǒng)計(jì)結(jié)果，并給出其適用場(chǎng)景；

·提出基于上下限的數(shù)據(jù)單元裁剪方法，提高存儲(chǔ)效率和準(zhǔn)確率；

·基于傾斜時(shí)間窗口的索引模型可快速計(jì)算任意時(shí)間片中的統(tǒng)計(jì)結(jié)果；

·真實(shí)數(shù)據(jù)集實(shí)驗(yàn)中，比較了相關(guān)參數(shù)對(duì)模型的影響，體現(xiàn)模型的優(yōu)越性和可用性。

sketch cube只支持流數(shù)據(jù)分布型的聚合操作，在下一步工作中，將研究較為復(fù)雜的代數(shù)型和整體型聚合操作在流數(shù)據(jù)sketch cube模型中的應(yīng)用。同時(shí)把計(jì)算過程中的性能瓶頸通過合理設(shè)計(jì)拓?fù)浣Y(jié)構(gòu)分散到不同機(jī)器節(jié)點(diǎn)中，以提高流數(shù)據(jù)的處理能力和穩(wěn)定性。

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 胡文瑜，孫志揮，吳英杰.數(shù)據(jù)挖掘取樣方法研究.計(jì)算機(jī)研究與發(fā)展,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 張進(jìn)，鄔江興，劉勤讓.4種技術(shù)型Bloom Filter的性能分析與比較.軟件學(xué)報(bào)，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