[發明專利]一種面向大數據聚集分析的近似計算方法

在審

• 申請號: 201710982111.0
• 申請日: 2017-10-20
• 公開（公告）號: CN107704611A
• 公開（公告）日: 2018-02-16
• 發明（設計）人: 黃震華;高軍;張志飛
• 申請（專利權）人: 同濟大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海科律專利代理事務所(特殊普通合伙)31290
• 代理人: 葉鳳

技術領域

本發明涉及計算機應用技術領域，尤其是涉及一種大數據分析的計算方法。

背景技術

近年來，隨著云計算、移動通信和信息技術的迅猛發展，大部分企業內部已積累了大量數據。而如何從海量數據中快速分析出有用的信息，并為企業各管理層提供有效的決策支持是提高企業經濟效益和市場競爭力的一個主要手段。聚集分析能夠通過復雜的數據查詢語句來有效獲取企業數據上的統計性指標，如SUM(求和)、AVG(求平均值)、COUNT(計數)、STDEV(標準差)、QUANTILE(分位數)等，使得它已成為近幾年企業數據分析的一個重要工具。

目前，提高聚集分析速度有幾個主要技術有：1)構建適合數據分布的多維索引技術，如B-樹、R-樹和網格；2)分布式計算技術，如基于Hadoop或Spark平臺的map-reduce分布式計算框架；3)并行計算技術，如基于多核GPU(Graphics Processing Unit)的并行化處理技術；4)物化視圖技術，即通過預先存儲大量中間結果來提高聚集分析的速度。現有的主流數據庫和OLAP(On-Line Analytical Processing)工具基本上都具有聚集分析的功能，并提供若干種有效的優化技術來降低聚集分析的用戶響應時間，并提高分析效率。

我們發現上述現有的聚集分析技術在處理較小或中等規模的企業數據時，能夠具有較快的速度和可接受的額外磁盤開銷。然而在大數據環境下，聚集分析需要處理的數據除了單個數據表數據量巨大之外，進行連接操作的數據表個數也將比較多，而且很有可能存在多層嵌套查詢的情況。因此，如果通過現有方法進行精確的計算聚集分析的結果，那么勢必會導致分析效率極其低下，而且需要巨大的額外磁盤開銷來存儲多維索引和中間輸出結果。例如，為了得到1T數據上包含2層嵌套查詢的聚集分析結果，四核GPU并行計算需要6.5個小時左右，并且需要1.8T的額外磁盤開銷，顯然，這是用戶無法接受的。

發明內容

本發明的目的就是為了解決上述現有方法存在的缺陷而提供一種處理速度快、分析結果準確度高且更為人性化的大數據聚集分析近似計算方法。

本發明需要保護的技術方案為：

一種面向大數據聚集分析的近似計算方法，其特征在于，包括如下步驟：

數據分割步驟(模塊1)：

首先將基礎大數據順序劃分成多個不相交的數據片，并按一定的比例交換不同數據片中的數據元組。

漸進近似計算步驟(模塊2)：

從第一個數據片開始，依次接收數據分割步驟輸入的數據片，并將所接收的數據片傳送給聚集增量更新步驟(模塊3)之后，等待聚集增量更新步驟計算并返回給定個數的聚集分析結果采樣值，然后，基于這些聚集分析結果采樣值來求取它們的平均值、相對標準偏差以及置信區間，并將這三個值返回給終端用戶。如果用戶接受相對標準偏差和置信區間，那么分析過程停止，否則，從數據分割步驟再輸入一個數據片并進行后續的處理。

聚集增量更新步驟(模塊3)：

接收漸進近似計算步驟傳送過來的數據片，將該數據片與歷史處理過的所有數據片進行合并，然后在合并后的全局數據片上進行給定次數的有放回采樣，并在每次采樣后的數據樣本集上增量計算并更新聚集分析的結果，從而得到該樣本集上的聚集分析結果采樣值。當所有樣本集均處理完畢后，將這些聚集分析結果采樣值返回給近似計算步驟。

本發明具有以下優點：

1.本發明通過近似計算和增量更新的策略來求取聚集分析結果值，這樣能夠顯著降低大數據上聚集分析的實際開銷。

2.本發明通過與終端用戶交互的方式來逐步逼近大數據上的聚集分析結果值，使得聚集分析操作更為人性化。

3.本發明主要由3個模塊組成，每個模塊的實施過程簡單、容易實現，同時不受具體開發工具和編程軟件的限制，并且能夠快速擴展到分布式和并行化的開發環境中。

附圖說明

圖1本發明的技術框架圖。

具體實施方式

本發明技術框架如圖1所示，本發明主要由數據分割、漸進近似計算以及聚集增量更新三個模塊組成。

數據分割模塊(模塊1)首先將基礎大數據順序劃分成多個不相交的數據片，并按一定的比例交換不同數據片中的數據元組。