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

【摘要】：數(shù)據(jù)立方(Data Cube)是一種有效支持OLAP的多維數(shù)據(jù)計算模型。它通過預(yù)先計算數(shù)據(jù)表中各屬性間所有組合對應(yīng)的GroupBy結(jié)果并將其存儲起來，以縮短系統(tǒng)的響應(yīng)時間從而提高查詢效率。隨著數(shù)據(jù)量的急劇增長，分布式計算(如MapReduce)的使用日益廣泛，將數(shù)據(jù)立方計算與分布式結(jié)合是必然的趨勢。 對于代數(shù)度量，如SUM等，簡單地采用MapReduce框架即可高效地完成數(shù)據(jù)立方的計算。但對于整體性度量，如DISTINCT等，若與MapReduce簡單地結(jié)合，則會出現(xiàn)負載不均衡、中間數(shù)據(jù)過多等問題。當前最好的分布式數(shù)據(jù)立方計算算法MR-Cube，通過數(shù)據(jù)劃分、合并計算的方法減緩上述問題。但是該算法對數(shù)據(jù)劃分不夠精準，會導(dǎo)致一些不必要的數(shù)據(jù)劃分，加重之后的合并操作。而對于合并計算，該算法僅提出了一些規(guī)則，而無簡單且有效的合并方法，并且進行合并計算時使用BUC算法亦未充分利用MapReduce框架的特性。 為了更好地解決負載不均衡、中間數(shù)據(jù)過多的問題，本論文借鑒TeraSort與PipeSort，提出TeraSortPipeSort-Cube算法（以下簡稱TSP-Cube算法）。TSP-Cube借鑒TeraSort隨機抽樣的思想，根據(jù)數(shù)據(jù)出現(xiàn)的頻率對數(shù)據(jù)進行劃分，不僅可以有效避免不必要的劃分，，并且適用于各種分布類型的數(shù)據(jù)集，從而有效解決負載不均衡的問題。同時TSP-Cube采用能充分利用MapReduce框架特性的PipeSort替代MR-Cube中的BUC進行合并計算，并且針對層次型的數(shù)據(jù)集，根據(jù)其屬性特征以及PipeSort的特性，采用更簡單有效且均勻的合并計算方案，從而解決中間數(shù)據(jù)過多的問題。 論文通過實驗證明，無論在均勻分布或是傾斜分布下，TSP-Cube在整體性度量函數(shù)中都有更好的性能，比已有的分布式算法更通用。此外，實驗還對多種算法在代數(shù)度量下的性能進行了比較，從而得出不同類型的度量應(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.
【學位授予單位】：中山大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：TP338.8

【相似文獻】

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

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

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

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

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

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

6 孫宇;王永娟;;Cube攻擊原理與改進[J];計算機科學;2012年S1期

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

8 ;主打XC Cube[J];每周電腦報;2003年42期

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

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

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

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

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

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

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

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

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

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

1 ;與Cube說再見[N];中國計算機報;2001年

2 ;AOpen XC cube準系統(tǒng)[N];電腦商報;2004年

3 本報記者 崔謙;XC Cube:變革的黎明[N];計算機世界;2003年

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

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

6 TWICE 評測實驗室 李丹;PC家電化的使者[N];計算機世界;2004年

7 肖冠丁;家居的味道[N];中國計算機報;2004年

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

9 本報記者　李治鋼;打造X時代PC[N];計算機世界;2004年

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號：1474559