本文關(guān)鍵詞： 數(shù)據(jù)立方 分布式 MapReduce TeraSort　出處：《中山大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：數(shù)據(jù)立方(Data Cube)是一種有效支持OLAP的多維數(shù)據(jù)計(jì)算模型。它通過預(yù)先計(jì)算數(shù)據(jù)表中各屬性間所有組合對(duì)應(yīng)的GroupBy結(jié)果并將其存儲(chǔ)起來，以縮短系統(tǒng)的響應(yīng)時(shí)間從而提高查詢效率。隨著數(shù)據(jù)量的急劇增長(zhǎng)，分布式計(jì)算(如MapReduce)的使用日益廣泛，將數(shù)據(jù)立方計(jì)算與分布式結(jié)合是必然的趨勢(shì)。 對(duì)于代數(shù)度量，如SUM等，簡(jiǎn)單地采用MapReduce框架即可高效地完成數(shù)據(jù)立方的計(jì)算。但對(duì)于整體性度量，如DISTINCT等，若與MapReduce簡(jiǎn)單地結(jié)合，則會(huì)出現(xiàn)負(fù)載不均衡、中間數(shù)據(jù)過多等問題。當(dāng)前最好的分布式數(shù)據(jù)立方計(jì)算算法MR-Cube，通過數(shù)據(jù)劃分、合并計(jì)算的方法減緩上述問題。但是該算法對(duì)數(shù)據(jù)劃分不夠精準(zhǔn)，會(huì)導(dǎo)致一些不必要的數(shù)據(jù)劃分，加重之后的合并操作。而對(duì)于合并計(jì)算，該算法僅提出了一些規(guī)則，而無簡(jiǎn)單且有效的合并方法，并且進(jìn)行合并計(jì)算時(shí)使用BUC算法亦未充分利用MapReduce框架的特性。 為了更好地解決負(fù)載不均衡、中間數(shù)據(jù)過多的問題，本論文借鑒TeraSort與PipeSort，提出TeraSortPipeSort-Cube算法（以下簡(jiǎn)稱TSP-Cube算法）。TSP-Cube借鑒TeraSort隨機(jī)抽樣的思想，根據(jù)數(shù)據(jù)出現(xiàn)的頻率對(duì)數(shù)據(jù)進(jìn)行劃分，不僅可以有效避免不必要的劃分，，并且適用于各種分布類型的數(shù)據(jù)集，從而有效解決負(fù)載不均衡的問題。同時(shí)TSP-Cube采用能充分利用MapReduce框架特性的PipeSort替代MR-Cube中的BUC進(jìn)行合并計(jì)算，并且針對(duì)層次型的數(shù)據(jù)集，根據(jù)其屬性特征以及PipeSort的特性，采用更簡(jiǎn)單有效且均勻的合并計(jì)算方案，從而解決中間數(shù)據(jù)過多的問題。 論文通過實(shí)驗(yàn)證明，無論在均勻分布或是傾斜分布下，TSP-Cube在整體性度量函數(shù)中都有更好的性能，比已有的分布式算法更通用。此外，實(shí)驗(yàn)還對(duì)多種算法在代數(shù)度量下的性能進(jìn)行了比較，從而得出不同類型的度量應(yīng)采用的方法。
[Abstract]:Data Cube). It is a multidimensional data computing model that effectively supports OLAP. It computes and stores the GroupBy results corresponding to all the combinations of attributes in the data table in advance. In order to shorten the response time of the system and improve the query efficiency. With the rapid growth of data, distributed computing (such as MapReduce) is becoming more and more widely used. It is an inevitable trend to combine data cube computing with distributed computing. For algebraic metrics, such as SUM, the calculation of data cubes can be accomplished efficiently by using MapReduce framework, but for integral measures, such as DISTINCT, etc. If combined with MapReduce simply, there will be some problems, such as load imbalance, excessive intermediate data, etc. MR-Cube, the best distributed data cube computing algorithm, is partitioned by data. The method of merging reduces the above problem, but the algorithm is not accurate enough to divide the data, which will lead to some unnecessary data partition, which will aggravate the merging operation. The algorithm only proposes some rules, but has no simple and effective merging method, and the BUC algorithm is not fully utilized in the MapReduce framework. In order to solve the problem of load imbalance and excessive data, this paper draws lessons from TeraSort and PipeSort. TeraSortPipeSort-Cube algorithm (hereinafter referred to as TSP-Cube algorithm). TSP-Cube uses the idea of TeraSort random sampling for reference. Dividing the data according to the frequency of data occurrence can not only effectively avoid unnecessary partitioning, but also be applicable to all kinds of distributed data sets. In order to effectively solve the problem of load imbalance, at the same time, TSP-Cube uses PipeSort, which can make full use of the characteristics of MapReduce framework, instead of BUC in MR-Cube. Combined calculations. According to the attribute characteristics of hierarchical data sets and the characteristics of PipeSort, a more simple, effective and uniform scheme is adopted to solve the problem of excessive data in the middle. The experimental results show that TSP-Cube has better performance in the integral metric function under uniform distribution or tilt distribution, and is more general than the existing distributed algorithm. The performance of many algorithms under algebraic metric is compared, and the methods used in different types of metrics are obtained.
【學(xué)位授予單位】：中山大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP338.8

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 吳敵;準(zhǔn)系統(tǒng) Aopen XC Cube[J];個(gè)人電腦;2004年02期

2 周繼鵬;k-aryn-cube網(wǎng)絡(luò)上的完美資源布局[J];暨南大學(xué)學(xué)報(bào)(自然科學(xué)與醫(yī)學(xué)版);2004年03期

3 胡孔法;陳];董逸生;;一種基于維層次聚集樹的Cube增量更新算法[J];小型微型計(jì)算機(jī)系統(tǒng);2005年12期

4 顧頎;胡孔法;陳];唐曉麗;劉海東;;基于維層次的語義Cube存儲(chǔ)與增量更新技術(shù)研究[J];計(jì)算機(jī)應(yīng)用研究;2007年06期

5 ;創(chuàng)意盒子 來自Logitech Cube的新體驗(yàn)[J];電腦迷;2012年05期

6 孫宇;王永娟;;Cube攻擊原理與改進(jìn)[J];計(jì)算機(jī)科學(xué);2012年S1期

7 ;抓取生活中的美妙色彩——SwatchMate Cube[J];流行色;2014年03期

8 ;主打XC Cube[J];每周電腦報(bào);2003年42期

9 胡孔法,董逸生,徐立臻;基于維層次的壓縮Cube[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年05期

10 胡孔法;陳];李斌;;高維層次聚集Cube并行創(chuàng)建與存儲(chǔ)方法[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年01期

相關(guān)會(huì)議論文 前6條

1 李駿;陸歡寰;周皓峰;王智慧;汪衛(wèi);施伯樂;;基于Contour Cube的有界近似壓縮算法[A];第二十三屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

2 高宏;李建中;;并行Cube存儲(chǔ)結(jié)構(gòu)—CMD_Forest[A];第十七屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2000年

3 孫延凡;陳紅;王珊;;FreeCube:有效減小Data Cube體積[A];第二十屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2003年

4 印瑩;趙宇海;張斌;;一種基于Dwarf的快速有效增量更新算法(英文)[A];第二十二屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2005年

5 劉延慶;甘亮;韓偉紅;;一種Hybrid數(shù)據(jù)庫(kù)上大時(shí)間窗口Cube查詢的研究[A];全國(guó)計(jì)算機(jī)安全學(xué)術(shù)交流會(huì)論文集（第二十四卷）[C];2009年

6 張夢(mèng)瑤;周宇;顧克驊;楊帥奇;范星河;沈志豪;;Synthesis and Self-Assembly of Cube-Disk Shape Amphiphiles[A];2014年兩岸三地高分子液晶態(tài)與超分子有序結(jié)構(gòu)學(xué)術(shù)研討會(huì)摘要集[C];2014年

相關(guān)重要報(bào)紙文章 前9條

1 ;與Cube說再見[N];中國(guó)計(jì)算機(jī)報(bào);2001年

2 ;AOpen XC cube準(zhǔn)系統(tǒng)[N];電腦商報(bào);2004年

3 本報(bào)記者 崔謙;XC Cube:變革的黎明[N];計(jì)算機(jī)世界;2003年

4 ;ICE Cube數(shù)據(jù)中心采用IBM刀片服務(wù)器[N];人民郵電;2008年

5 佚名;期待新型PC: Google Cube[N];計(jì)算機(jī)世界;2006年

6 TWICE 評(píng)測(cè)實(shí)驗(yàn)室 李丹;PC家電化的使者[N];計(jì)算機(jī)世界;2004年

7 肖冠丁;家居的味道[N];中國(guó)計(jì)算機(jī)報(bào);2004年

8 內(nèi)蒙古 王f ;PC還可以更小的[N];電腦報(bào);2004年

9 本報(bào)記者　李治鋼;打造X時(shí)代PC[N];計(jì)算機(jī)世界;2004年

相關(guān)博士學(xué)位論文 前2條

1 肖燦文;基于k-ary n-cube網(wǎng)絡(luò)的高效通信[D];國(guó)防科學(xué)技術(shù)大學(xué);2005年

2 劉楊;事件相關(guān)電位腦—機(jī)接口的最優(yōu)設(shè)計(jì)[D];國(guó)防科學(xué)技術(shù)大學(xué);2010年

相關(guān)碩士學(xué)位論文 前9條

1 周迎輝;基于樹形結(jié)構(gòu)的XML Cube研究[D];中國(guó)科學(xué)院大學(xué)(工程管理與信息技術(shù)學(xué)院);2013年

2 顧頎;OLAP系統(tǒng)中Cube并行與分布式處理技術(shù)的研究[D];揚(yáng)州大學(xué);2007年

3 陳琳;基于MapReduce的Data Cube相關(guān)技術(shù)的研究[D];湖南大學(xué);2013年

4 張延鵬;Data Cube中基于維層次的OLAP算法研究[D];燕山大學(xué);2010年

5 杜紅紅;祖沖之算法分析和Cube密碼分析方法研究[D];山東師范大學(xué);2013年

6 張琳;Cube軟件交通規(guī)劃建模特點(diǎn)研究[D];長(zhǎng)安大學(xué);2012年

7 王新寶;Quotient Cube技術(shù)研究[D];山東大學(xué);2009年

8 任鳳;P2P環(huán)境下Data Cube的更新與查詢研究[D];長(zhǎng)沙理工大學(xué);2011年

9 胡本瓊;幾類網(wǎng)絡(luò)的結(jié)構(gòu)及相關(guān)參數(shù)研究[D];電子科技大學(xué);2005年

本文編號(hào)：1474559