[發(fā)明專利]一種大數(shù)據(jù)多區(qū)間查詢條件下的基數(shù)估計(jì)方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201310484503.6
• 申請(qǐng)日: 2013-10-16
• 公開（公告）號(hào): CN103544258B
• 公開（公告）日: 2016-11-30
• 發(fā)明（設(shè)計(jì)）人: 云曉春;徐小琳;王明華;劉陽;李志輝;吳廣君;王樹鵬;王勇;常為領(lǐng)
• 申請(qǐng)（專利權(quán)）人: 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心;中國(guó)科學(xué)院信息工程研究所
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京輕創(chuàng)知識(shí)產(chǎn)權(quán)代理有限公司 11212
• 代理人: 楊立

技術(shù)領(lǐng)域

本發(fā)明涉及大數(shù)據(jù)計(jì)算領(lǐng)域，特別涉及一種大數(shù)據(jù)多區(qū)間查詢條件下的基數(shù)估計(jì)方法及裝置。

背景技術(shù)

隨著移動(dòng)互聯(lián)網(wǎng)和Web2.0的發(fā)展，全球數(shù)據(jù)量正在驚人的增長(zhǎng)：2008年全球產(chǎn)生的數(shù)據(jù)量為0.49ZB（1ZB=1021字節(jié)），2009年為0.8ZB，2010年為1.2ZB，2011年高達(dá)1.82ZB。IDC預(yù)計(jì)到2020年，全人類會(huì)產(chǎn)生超過40ZB的數(shù)據(jù)。在大數(shù)據(jù)中一類重要的數(shù)據(jù)是結(jié)構(gòu)化、半結(jié)構(gòu)化數(shù)據(jù)，主要包括：交易數(shù)據(jù)，日志數(shù)據(jù)等。據(jù)了解，淘寶網(wǎng)每日新增的交易數(shù)據(jù)達(dá)10TB，eBay分析平臺(tái)日處理數(shù)據(jù)量高達(dá)100PB，沃爾瑪每小時(shí)有大約2.5PB的數(shù)據(jù)存入數(shù)據(jù)庫。基于日志類數(shù)據(jù)進(jìn)行挖掘、分析可以獲得越來越多的有價(jià)值的信息。如Google?Trends對(duì)用戶上網(wǎng)記錄進(jìn)行統(tǒng)計(jì)，成功預(yù)測(cè)流感在全球的擴(kuò)散范圍，其準(zhǔn)確度高達(dá)到97%以上。

多區(qū)間條件大數(shù)據(jù)基數(shù)估算是統(tǒng)計(jì)同時(shí)符合多個(gè)區(qū)間查詢條件下的不同的記錄的個(gè)數(shù)，是聚合運(yùn)算、統(tǒng)計(jì)分析的基礎(chǔ)計(jì)算工具，在數(shù)據(jù)分析、網(wǎng)絡(luò)監(jiān)控及數(shù)據(jù)庫優(yōu)化等領(lǐng)域都有廣泛的相關(guān)需求。但是目前的大數(shù)據(jù)分析統(tǒng)計(jì)系統(tǒng)本質(zhì)是一種精確計(jì)算的方法，例如Hadoop為基礎(chǔ)的大數(shù)據(jù)管理系統(tǒng)Hive，pig等通過掃描原始數(shù)據(jù)獲得準(zhǔn)確的計(jì)算值，但是隨著數(shù)據(jù)規(guī)模的增大計(jì)算效率顯著下降。近似查詢是通過降低部分計(jì)算精度，來提高大數(shù)據(jù)的計(jì)算效率。傳統(tǒng)的基數(shù)估算算法，如Linear?Counting、LogLog?Counting、HyperLogLog?Counting、Adaptive?Counting，以及Bloomfilter等能解決簡(jiǎn)單的不同元素個(gè)數(shù)的統(tǒng)計(jì)，但是不支持區(qū)間查詢條件下的基數(shù)統(tǒng)計(jì)。實(shí)現(xiàn)多區(qū)間條件下的大數(shù)據(jù)高精度基數(shù)統(tǒng)計(jì)成為本發(fā)明需要解決的核心問題。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是提供一種大數(shù)據(jù)多區(qū)間查詢條件下的進(jìn)行高精度近似計(jì)算的基數(shù)估計(jì)方法及裝置。

本發(fā)明解決上述技術(shù)問題的技術(shù)方案如下：一種大數(shù)據(jù)多區(qū)間查詢條件下的基數(shù)估計(jì)方法，包括以下步驟：

步驟1：按照數(shù)值屬性對(duì)大數(shù)據(jù)預(yù)先劃分成多個(gè)分區(qū)，每個(gè)分區(qū)內(nèi)保存所述大數(shù)據(jù)中的一段數(shù)據(jù)源，各個(gè)分區(qū)之間有序排列；

步驟2：建立樹形索引結(jié)構(gòu)，每個(gè)分區(qū)作為樹形索引結(jié)構(gòu)的一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)用于記錄對(duì)應(yīng)的分區(qū)的最大值和最小值，每個(gè)節(jié)點(diǎn)中設(shè)置數(shù)據(jù)文件和基數(shù)估算器；

步驟3：獲取待寫入樹形索引結(jié)構(gòu)的數(shù)據(jù)源，對(duì)支持區(qū)間查詢條件的數(shù)據(jù)源進(jìn)行倒排索引處理；

步驟4：將經(jīng)過倒排索引處理的數(shù)據(jù)源的相應(yīng)部分分別寫入數(shù)據(jù)文件及基數(shù)估算器內(nèi)；

步驟5：根據(jù)區(qū)間查詢條件在樹形索引結(jié)構(gòu)中查詢滿足區(qū)間查詢條件的節(jié)點(diǎn)，得到節(jié)點(diǎn)中的基數(shù)估算器，對(duì)基數(shù)估算器中的數(shù)據(jù)源的相應(yīng)部分進(jìn)行邏輯處理，得到基數(shù)估算值。

本發(fā)明的有益效果是：本發(fā)明針對(duì)大數(shù)據(jù)統(tǒng)計(jì)分析中通常使用的多區(qū)間查詢條件，提出一種近似查詢方法，通過降低數(shù)據(jù)的計(jì)算精度提高基數(shù)統(tǒng)計(jì)效率。本發(fā)明在每個(gè)分區(qū)內(nèi)使用了HyperLogLog基數(shù)估算算法，公開的資料和理論證明該算法可以在較小內(nèi)存條件下（5KB），在10億規(guī)模的數(shù)據(jù)中，獲得小于1.14%的計(jì)算誤差，并且，估算器之間的合并不會(huì)降低計(jì)算誤差，因此本發(fā)明同樣可以在任意的多區(qū)間條件下，提供較高計(jì)算精度；

本發(fā)明在任意多區(qū)間查詢條件下，具備較高的查詢效率，適用于大數(shù)據(jù)的在線統(tǒng)計(jì)查詢。本發(fā)明基于分區(qū)信息建立層次化的索引結(jié)構(gòu)RC-Tree，在執(zhí)行具體的查詢操作時(shí)僅在RC-Tree中進(jìn)行檢索，查詢效率與RC-Tree的節(jié)點(diǎn)數(shù)目相關(guān)與具體的數(shù)據(jù)量無關(guān)。在多個(gè)區(qū)間條件下的檢索運(yùn)算，都轉(zhuǎn)化為二進(jìn)制或運(yùn)算，因此都具有較高計(jì)算效率；

本發(fā)明使用了大數(shù)據(jù)增量更新技術(shù)提高索引數(shù)據(jù)在線更新效率。發(fā)明使用臨時(shí)表索引結(jié)構(gòu)保存增量更新的數(shù)據(jù)，并對(duì)數(shù)據(jù)進(jìn)行合并，當(dāng)?shù)竭_(dá)到一定的數(shù)據(jù)規(guī)模后，把合并以后的數(shù)據(jù)批量更新到全局的索引結(jié)構(gòu)中，并與全局索引進(jìn)行再次合并，提高大數(shù)據(jù)的更新效率。

在上述技術(shù)方案的基礎(chǔ)上，本發(fā)明還可以做如下改進(jìn)。

進(jìn)一步，所述步驟3具體為：為每個(gè)待寫入的數(shù)據(jù)源分配一個(gè)全局唯一的ID,將每個(gè)數(shù)據(jù)源分別拆分為<value,ID>結(jié)構(gòu)。

進(jìn)一步，所述步驟4具體為：將<value,ID>結(jié)構(gòu)中的value寫入相應(yīng)的節(jié)點(diǎn)內(nèi)的數(shù)據(jù)文件中，ID利用哈希算法寫入節(jié)點(diǎn)內(nèi)的基數(shù)估算器中。