[發(fā)明專利]面向大數(shù)據(jù)環(huán)境的概要信息動態(tài)構(gòu)建與查詢方法及裝置

有效

• 申請?zhí)枺?/td>: 201510061345.2
• 申請日: 2015-02-05
• 公開（公告）號: CN104657450B
• 公開（公告）日: 2018-09-25
• 發(fā)明（設(shè)計）人: 吳廣君;王樹鵬;陳明;張曉宇;張燕琴
• 申請（專利權(quán)）人: 中國科學(xué)院信息工程研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長江

1.一種面向大數(shù)據(jù)環(huán)境的概要信息動態(tài)構(gòu)建方法，其步驟包括：

1)以Count-Min Sketch方法為基礎(chǔ)，采用數(shù)據(jù)流的第一范數(shù)描述數(shù)據(jù)規(guī)模，采用數(shù)據(jù)的基數(shù)值描述數(shù)據(jù)的分布情況；

2)為流式大數(shù)據(jù)分配一較小空間的Count-Min Sketch結(jié)構(gòu)，隨著數(shù)據(jù)不斷加載，當初始的Count-Min Sketch記錄的數(shù)據(jù)項個數(shù)達到閾值且數(shù)值空間基數(shù)達到閾值以后，建立新的Count-Min Sketch結(jié)構(gòu)，用以接收后續(xù)到來的新數(shù)據(jù)；為每個Count-Min Sketch結(jié)構(gòu)構(gòu)建Bloomfilter，用于統(tǒng)計每個Count-Min Sketch內(nèi)部數(shù)據(jù)的存在性，每個Count-MinSketch接收的數(shù)據(jù)同時寫入到Bloomfilter中；

進行數(shù)據(jù)寫入的具體流程為：設(shè)到達的數(shù)據(jù)項為<key,value>，當有新數(shù)據(jù)到達時，首先把key寫入全局基數(shù)估算器中，并實時計算當前的基數(shù)規(guī)模Di，然后統(tǒng)計當前Count-MinSketch的第一范數(shù)的值||a||₁；

如果||a||₁<N，則把key加入到Bloomfilter中，并根據(jù)Count-Min Sketch更新原理，把CM[j][hash_j(key)]位置的計數(shù)器加上value，其中j為二維數(shù)組的第j行，N為預(yù)先設(shè)定的所要存儲的數(shù)據(jù)的第一范數(shù)；

如果||a||₁>＝N，則判斷D_i-D_i-1是否大于r×w，如果D_i-D_i-1<r×w則繼續(xù)寫入，否則創(chuàng)建新的Bloomfilter和Count-Min Sketch并接收新寫入的數(shù)據(jù)；其中r是預(yù)先設(shè)定的比率值，根據(jù)hash函數(shù)的碰撞概率計算獲得；w為二維計數(shù)數(shù)組的寬度；D_i-1表示到第i-1個Count-Min Sketch為止的全部數(shù)據(jù)的基數(shù)估算值。

2.如權(quán)利要求1所述的方法，其特征在于：所述Count-Min Sketch結(jié)構(gòu)采用限定誤差的概要設(shè)計方法，在概率參數(shù)為δ，誤差參數(shù)為ε條件下，可容忍的最大單點誤差滿足如下不等式：

其中：a_i為待查詢的變量，是由Count-Min Sketch所得a_i的估計值，||a||₁為Count-Min Sketch統(tǒng)計獲得的數(shù)據(jù)的第一范數(shù)，即當前Count-Min Sketch中頻數(shù)的總和，e為自然對數(shù)的底數(shù)，d為Count-Min Sketch結(jié)構(gòu)中hash數(shù)組的個數(shù)。

3.如權(quán)利要求1所述的方法，其特征在于：采用Hyperloglog算法獲得數(shù)據(jù)的基數(shù)值。

4.一種面向大數(shù)據(jù)環(huán)境的數(shù)據(jù)查詢方法，其步驟包括：

1)利用權(quán)利要求1～3中任一項所述方法建立Count-Min Sketch結(jié)構(gòu)，并在Count-MinSketch結(jié)構(gòu)中寫入和更新數(shù)據(jù)；

2)查詢數(shù)據(jù)項<key,value>時，首先利用Bloomfilter找到第一個含有關(guān)鍵字key的Count-Min Sketch，記錄所得估計值，然后判斷這個Count-Min Sketch的基數(shù)，若基數(shù)<＝r×w，停止查詢；若基數(shù)>r×w，繼續(xù)利用Bloomfilter查詢余下的Count-Min Sketch是否包含關(guān)鍵字為key的數(shù)據(jù)項，并記錄估計值，直到查完所有的Count-Min Sketch為止；

3)將所有Count-Min Sketch的估計值相加，得到的總和作為此數(shù)據(jù)數(shù)的頻數(shù)的估計值，并估計誤差。