封閉直方圖數(shù)據(jù)立方體的構(gòu)建算法的研究與實(shí)現(xiàn).pdf

1、隨著信息科學(xué)與技術(shù)在生產(chǎn)實(shí)踐中的大量應(yīng)用，每天企業(yè)都積累了大量數(shù)據(jù)，這使得企業(yè)決策者為了從數(shù)據(jù)中發(fā)現(xiàn)知識(shí)越來越依賴于決策分析工具，OLAP就是這樣一種工具。然而受數(shù)據(jù)海量化和高維化影響，OLAP技術(shù)中的一些方面受到了嚴(yán)峻的挑戰(zhàn)，其中數(shù)據(jù)立方體技術(shù)受到的影響尤其巨大。數(shù)據(jù)立方體是數(shù)據(jù)一種預(yù)處理技術(shù)，它的缺點(diǎn)是構(gòu)建時(shí)的時(shí)間開銷和空間開銷都非常龐大。為了改變它這一缺點(diǎn)，封閉立方體等壓縮技術(shù)被提出來，大大減小了數(shù)據(jù)立方體的體積。然而在海量數(shù)據(jù)和

2、高維度面前，時(shí)空開銷依然是巨大的挑戰(zhàn)。另一方面數(shù)據(jù)立方體的靈活性也很差，后來出現(xiàn)了直方圖數(shù)據(jù)立方體，能夠很大程度上提高數(shù)據(jù)立方體的靈活性。隨著云時(shí)代的到來，MapReduce模型和它的開源實(shí)現(xiàn)Hadoop大量普及，出現(xiàn)了基于MapReduce模型的封閉立方體構(gòu)建方法。這種方法能利用集群的力量極大提升計(jì)算能力，從而應(yīng)對(duì)構(gòu)建封閉立方體的挑戰(zhàn)。然而這些方法在性能上還有很大不足，尤其是在應(yīng)對(duì)維度比較高的情況。
　　本文采用格分解的思想，提

3、出了一種新的基于MapReduce的構(gòu)建封閉數(shù)據(jù)立方體的方法MRC-Cubing，將龐大的計(jì)算完整的封閉立方體的任務(wù)，分解成若干個(gè)易并行的小任務(wù)。與過去的MapReduce方法相比，它能夠很大程度提升計(jì)算封閉立方體的效率，對(duì)維度很高的情況也可以有效支持。本文還為這種基于MapReduce的方法提出了負(fù)載不均衡問題的解決方案:調(diào)整哈希策略以解決邊界子封閉立方體元組數(shù)不均衡，遞進(jìn)分解邊界子封閉立方體以處理超大邊界子封閉立方體。本方法同樣適用

4、于解決封閉直方圖立方體的情況。
　　構(gòu)建封閉直方圖數(shù)據(jù)立方體是一種很大的開銷，因此當(dāng)對(duì)已有的數(shù)據(jù)集構(gòu)建了封閉數(shù)據(jù)立方體后，而隨著時(shí)問的推移有新的數(shù)據(jù)來臨并積累了一定數(shù)據(jù)量時(shí)，如果能夠不用重新構(gòu)建封閉直方圖立方體，而只是在原有立方體的基礎(chǔ)上將新來的數(shù)據(jù)集加入到數(shù)據(jù)立方體中是更好的。本文基于對(duì)增量更新中利用已有的封閉立方體所帶來的收益與代價(jià)的分析，提出了一種在單機(jī)環(huán)境下，對(duì)已有封閉直方圖數(shù)據(jù)立方體進(jìn)行增量更新的方法。這種方法能夠用比重