臺灣博碩士論文加值系統

在這篇論文中，我們為一個分散式且基於 NoSQL 資料庫的批價系統開發一套資料分散策略。我們先定義一個名為通話圖分割的最佳化問題，這個問題的目標在於平衡傳輸成本並提高資料本地性。我們證明這是一個 NP-complete 的問題，並設計一個貪婪演算法來解決這個問題。然後我們把通話圖分割技術應用於一個分散式且基於 NoSQL 資料庫的批價系統。我們藉由平衡機器間的傳輸並提高資料本地性來改善系統效能。

In this thesis, we develop a data distribution policy for a distributed NoSQLbased billing system. We define an optimization problem which is call graph partitioning problem. The objective of the problem is to balance communication while enhancing data locality. We prove that the problem is NP-complete and design a greedy algorithm to partition a call graph. Then we apply the call graph partitioning technique to a distributed NoSQL-based billing system. We improve system performance by balancing communication across servers and enhancing data locality.

Contents
口試委員會審定書 i
Acknowledgement ii
Chinese Abstract iii
Abstract iv
Contents v
List of Figures viii
List of Tables ix
1 Introduction 1
2 Related Work 4
2.1 Graph Partitioning with Local Search . . . . . . . . . . . . . . . . . . . 4
2.2 Graph Partitioning Using Global Graph Information . . . . . . . . . . . . 5
2.3 Multilevel Graph Partitioning . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Problem 9
3.1 Call Detail Record . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Call Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Call Graph Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4 Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Algorithm 13
4.1 Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Experiment 18
5.1 Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.1.1 Synthetic Call Detail Records . . . . . . . . . . . . . . . . . . . 18
5.1.2 Synthetic Call Graph . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Other Partitioning Methods . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.1 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.2 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.3 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2.4 METIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3 Call Graph Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3.1 Maximum Communication Cost . . . . . . . . . . . . . . . . . . 21
5.3.2 CH and CL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3.3 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.4 NoSQL-based Billing System . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4.1 System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4.2 Data Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.4.3 Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.4.4 Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.4.5 Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.4.6 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . 27
6 Conclusion 30
Bibliography 31

[1] Apache phoenix. http://phoenix.apache.org/.
[2] Hadoop. http://hadoop.apache.org/.
[3] Hbase. http://hbase.apache.org/.
[4] Metis. http://glaros.dtc.umn.edu/gkhome/metis/metis/overview.
[5] Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. CoRR, abs/1311.3144, 2013.
[6] Ralf Diekmann, Robert Preis, Frank Schlimbach, and Chris Walshaw. Shapeoptimized mesh partitioning and load balancing for parallel adaptive {FEM}. Parallel Computing, 26(12):1555 – 1581, 2000. Graph Partitioning and Parallel Computing.
[7] C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Design Automation, 1982. 19th Conference on, pages 175–181, June 1982.
[8] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
[9] Alan George and Joseph W. Liu. Computer Solution of Large Sparse Positive Definite. Prentice Hall Professional Technical Reference, 1981.
[10] Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. In Proceedings of the 1995 ACM/IEEE Conference on Supercomputing, Supercomputing ’95, New York, NY, USA, 1995. ACM.
[11] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359–392, December 1998.
[12] George Karypis and Vipin Kumar. Multilevel algorithms for multi-constraint graph partitioning. In Proceedings of the 1998 ACM/IEEE Conference on Supercomputing, SC ’98, pages 1–13, Washington, DC, USA, 1998. IEEE Computer Society.
[13] George Karypis and Vipin Kumar. Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput., 48(1):96–129, January 1998.
[14] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291–307, Feb 1970.
[15] L. A. Sanchis. Multiple-way network partitioning. IEEE Transactions on Computers, 38(1):62–81, Jan 1989.
[16] Kirk Schloegel, George Karypis, and Vipin Kumar. Sourcebook of parallel computing. chapter Graph Partitioning for High-performance Scientific Simulations, pages 491–541. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003.
[17] Mukund Seshadri, Sridhar Machiraju, Ashwin Sridharan, Jean Bolot, Christos Faloutsos, and Jure Leskove. Mobile call graphs: Beyond power-law and lognormal distributions. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pages 596–604, New York, NY, USA, 2008. ACM.
[18] Isabelle Stanton and Gabriel Kliot. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’12, pages 1222–1230, New York, NY, USA, 2012. ACM.