臺灣博碩士論文加值系統

在今日各企業需要計算的資料量日趨多量化的環境下，因為單一雲端的運算能力有限，有時已無法有效率負荷龐大的資料量。此時適當分配另一個雲端幫忙協調運算，使整體運算變得有效率，互聯雲端(inter-cloud)基於此概念產生。FP-Growth演算法是資料探勘中非常重要的一個理論，因此本論文將其建構於互聯雲端來運算。因為目前運算平行化FP-Growth演算法大多以單一雲端為主，運用互聯雲端運算仍是新興領域。

在互聯雲端的異構環境情況下，由於不同的Hadoop雲端整合在一起時，需要透過排程演算法分配資料到各個雲端和彙整各個雲端的輸出結果，為了解決這個問題，本論文提出一個根據Compute Capacity Aware Scheduling (CCAS)的排程演算法,此方法根據雲端所能處理的資料量分配適當的資料給該雲端運算。當資料量未超過雲端的最大運算量時就啟動單一雲端運算；當資料量超過雲端的最大運算量時，這時透過互聯雲端的異質群集幫忙協調運算。實驗證明此方法確可讓FP-Growth的互聯雲端運算能有效率的執行。

At present enterprises need to calculate more and more data in environment, single cloud system have limited computing power and unable to process a huge data. In this time coordinate the appropriate cloud to compute so that the overall operation becomes efficiency, inter-cloud system generated based on this concept. Moreover, FP-Growth algorithm is a famous tool in the field of Data Mining for finding association rules from data. Thus the FP-Growth algorithm running on the inter-cloud environment based on a scheduling algorithm is presented. Currently FP-Growth algorithm mostly process in single cloud, processing in inter-cloud system is still emerging field.

When several cloud systems are interconnected, data need be processed over various cloud systems with flexible and/or efficient methods. In this paper, a scheduling algorithm based on the Compute Capacity Aware Scheduling (CCAS) method is proposed. If the data volume does not exceed the maximal compute capacity of default cloud, only this single cloud will be used to perform the computation; otherwise, heterogeneous clusters organized as inter-cloud system will coordinate the computation. The experimental results show that the proposed method can achieve more efficient computing in inter-cloud environment.

中文摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 V
表目錄 VI
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 論文架構 3
第二章 背景知識 4
2.1 雲端運算 4
2.2 Hadoop系統 6
2.3 互聯雲端 7
2.4 排程演算法 8
2.5 關聯性法則 10
2.6 平行FP-Growth演算法 14
第三章 實驗方法 15
3.1 FP-Growth互聯雲端平行化架構 15
3.2 實作方法 15
3.3 雲端運算量 20
3.4 雲端資料區塊大小 21
3.5 MapReduce工作參數 21
3.6 互聯雲端資料分配運算 23
第四章 實驗結果 25
4.1 實驗設備 25
4.2 單一雲端運算的效能分析 26
4.3 CCAS在互聯雲端運算的分析與比較 28
4.4 單一雲端和互聯雲端運算的效能比較 31
4.5 CCAS和Request Base排程法在互聯雲端運算的分析與比較 33
第五章 結論與未來展望 35
參考文獻 36

中文文獻
[1] 呂雪驥、李龍澍。FP-Growth演算法MapReduce化研究。電腦技術與發展，第22卷。2012。
英文文獻
[1] Jiawei Han, Jian Pei, and Yiwen Yin. Mining frequent patterns without candidate generation. SIGMOD '00 Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp.1-12, New York, NY, USA, June. 2000.
[2] M. Armbrust, A. Fox, R. Griffith, A.D. Joseph, R. Katz, A. Konwinski, G. Lee, D.Patterson, A. Rabkin, I. Stoica, and M. Zaharia. Above the Clouds: A Berkeley View of Cloud Computing. UCB/EECS-2009-28, EECS Department, University of California, Berkeley, Feb. 2009.
[3] Deepak Puthal, B. P. S. Sahoo, Sambit Mishra, Satyabrata Swain. Cloud Computing Features, Issues, and Challenges: A Big Picture. Computational Intelligence and Networks (CINE), 2015 International Conference on, pp. 116 – 123, Bhubaneshwa, Jan. 2015.
[4] Anam Alam and Jamil Ahmed. Hadoop Architecture and Its Issues. Computational Science and Computational Intelligence (CSCI), 2014 International Conference on, pp. 288 – 291, Las Vegas, NV, March 2014.
[5] D.Borthakur. The Hadoop Distributed File System: Architecture and Design. The Apache Software Foundation, 2007.
[6] J. Dean and S. Ghemawat. MapReduce: Simplied Data Processing on Large Clusters. Communications of the ACM, vol. 51 Issue 1, pp. 107-113, New York, January 2008.
[7] ADEL NADJARAN TOOSI, RODRIGO N. CALHEIROS, and RAJKUMAR BUYYA. Interconnected Cloud Computing Environments: Challenges, Taxonomy, and Survey. ACM Computing Surveys, Vol. 47, No. 1, Article 7, New York, NY, July 2014.
[8] Mohammad Aazam, Marc StHilaire, and EuiNam Huh. Towards Media Intercloud Standardization Evaluating Impact of Cloud Storage Heterogeneity. Journal of Grid Computing, pp.1-19, March 2016.
[9] Stelios Sotiriadis, Nik Bessis, Ashiq Anjum, and Rajkumar Buyya. An Inter-Cloud Meta-Scheduling (ICMS) Simulation Framework: Architecture and Evaluation. IEEE Transactions on Services Computing, pp.1, Feb.2015.
[10] Ian Kelley. A Distributed Architecture for Intra- and Inter- Cloud Data Management. ScienceCloud '14 Proceedings of the 5th ACM workshop on Scientific cloud computing, pp.53-60, New York, NY, 2014.
[11] Yuan Luo and Beth Plale. Hierarchical MapReduce Programming Model and Scheduling Algorithms. CCGRID '12 Proceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, pp. 769-774, Washington, DC, 2012.
[12] Stelios Sotiriadis, Nik Bessis, and Pierre Kuonen, Nick Antonopoulos. The inter-cloud meta-scheduling (ICMS) framework. Advanced Information Networking and Applications (AINA), 2013 IEEE 27th International Conference on, pp. 64 – 73, Barcelona, March 2013.
[13] Aysan Rasooli and Douglas G. Down. A Hybrid Scheduling Approach for Scalable Heterogeneous Hadoop Systems. High Performance Computing, Networking, Storage and Analysis (SCC), 2012 SC Companion, pp. 1284 – 1291, Salt Lake City, UT, Nov. 2012.
[14] Dazhao Cheng, Jia Rao, Changjun Jiang, and Xiaobo Zhou. Resource and Deadline-aware Job Scheduling in Dynamic Hadoop Clusters. Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International, pp. 956 – 965, Hyderabad, May 2015.
[15] R. Agrawal and T. Lmielinski, A. Swami. Mining Association Rules between Sets of Items in Large Databases. SIGMOD '93 Proceedings of the 1993 ACM SIGMOD international conference on Management of data, pp.207-216, New York, NY, , May 1993.
[16] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules. Proc. 20th Int. Conf. Very Large Data Bases, VLDB, 1994.
[17] Iko Pramudiono and Masaru Kitsuregawa. Parallel FP-Growth on PC cluster. Advances in Knowledge Discovery and Data Mining Volume 2637 of the series Lecture Notes in Computer Science, pp. 467-473, April 2003.
[18] Haoyuan Li, Yi Wang, Dong Zhang, Ming Zhang, and Edward Y, Chang. Pfp: parallel FP-Growth for query recommendation. RecSys '08 Proceedings of the 2008 ACM conference on Recommender systems, pp.107-114, New York, NY, 2008.
[19] Cloud Computing三種雲端服務介紹. Available from：
https://dotblogs.com.tw/jimmyyu/archive/2009/12/03/12275.aspx
[20] Kevin Kelly. A cloudbook for the cloud：http://www.kk.org/thetechnium/archives/2007/11/a_cloudbook_for.php Luettu, Nov. 2007.
[21] Cisco Inter-Cloud介紹. Available from：http://www.convergedigest.com/2015/06/cisco-expands-its-intercloud-ecosystem.html