請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46243
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 劉邦鋒(Pangfeng Liu) | |
dc.contributor.author | Yi-Chien Chung | en |
dc.contributor.author | 鍾以千 | zh_TW |
dc.date.accessioned | 2021-06-15T04:59:38Z | - |
dc.date.available | 2012-07-30 | |
dc.date.copyright | 2010-07-30 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-07-28 | |
dc.identifier.citation | [1] B. Pawlowski, C. Juszczak, P. Staubach, C. Simith, D. Lebel, and D. Hitz. Nfs: Design and implementation. In Proc. Usenix Summer Technical Conf., 1994.
[2] M. Satyanarayanan, J.J. LKistler, P. Kumar, M.E. Okasaki, E.H. Siegel, and D.C. Steere. Coda: A highly available file system for distributed workstation environments. IEEE Trans. Computers, 39(4), 1990. [3] Powering Cloud Storage. Parascale cloud storage, 2009. [4] Amazon. S3: Simple storage service, 2010. [5] Nirvanix. Cloud storage solutions for the enterprise, 2010. [6] Google. Gdrive on-line data storage, 2010. [7] S. Ghemawat, H. Gobioff, and S. T. Leung. The google file system. In SOSP ’03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 29–43, New York, NY, USA, 2003. ACM Press. [8] C. Baru, R. Moore, A. Rajasekar, and M. Wan. The sdsc storage resource broker. In In Proceedings of CASCON, 1998. [9] B. Cohen. Incentives build robustness in bittorrent, 2003. [10] I. T. Foster. Globus toolkit version 4: Software for service-oriented systems. In Hai Jin, Daniel A. Reed, andWenbin Jiang, editors, NPC, volume 3779 of Lecture Notes in Computer Science, pages 2–13. Springer, 2005. [11] D. Roselli, J. R. Lorch, and T. E. Anderson. A comparison of file system workloads. In Proc. Ann. Usenix Technical Conference, June 2000. [12] Y. Perl and S. R. Schach. Max-min tree partitioning. J. ACM, 28(1):5–15, 1981. [13] G. N. Frederickson. Optimal algorithms for tree partitioning. In SODA ’91: Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pages 168–177, Philadelphia, PA, USA, 1991. Society for Industrial and Applied Mathematics. [14] D. S. Johnson and K. A. Niemi. On knapsacks, partitions, and a new dynamic programming technique for trees. Mathematics of Operations Research, 8(1):1–14, 1983. [15] R. I. Becker, S. R. Schach, and Y. Perl. A shifting algorithm for min-max tree partitioning. J. ACM, 29(1):58–67, 1982. [16] C. C. Kanne and G. Moerkotte. A linear time algorithm for optimal tree sibling partitioning and approximation algorithms in natix. In VLDB ’06: Proceedings of the 32nd international conference on Very large data bases, pages 91–102. VLDB Endowment, 2006. [17] M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990. [18] A. Hamacher, W. Hochst‥attler, and C. Moll. Tree partitioning under constraints – clustering for vehicle routing problems. In Proceedings of the 5th Twente workshop on on Graphs and combinatorial optimization, pages 55–69, Amsterdam, The Netherlands, The Netherlands, 2000. Elsevier Science Publishers B. V. [19] J. A. Lukes. Efficient algorithm for the partitioning of trees. IBM Journal of Research and Development, pages 217–224, 1974. [20] H. Schipper and M. H. Overmars. Dynamic partition trees. In Proc. 2nd Scandavian Workshop on Algorithms Theory, pages 404–417. Springer-Verlag, 1990. [21] Y. Chrysanthou andM. Slater. Computing dynamic changes to bsp trees. Computer Graphics Forum, 11(3):321–332, 1992. [22] C. Walshaw, M. Cross, and M. G. Everett. Dynamic load-balancing for parallel adaptive unstructured meshes. In SIAM Conf. on Parallel Proc. for Sci. Comp., 1997. [23] C. Walshaw, M. Cross, and M. G. Everett. Parallel dynamic graph partitioning for adaptive unstructured meshes. Journal of Parallel and Distributed Computing, 47(2):102 – 108, 1997. [24] C.Walshaw and M. Cross. Parallel optimisation algorithms for multilevel mesh partitioning. Parallel Computing, 26(12):1635 – 1660, 2000. Graph Partitioning and Parallel Computing. [25] C.Walshaw, M. Cross, and K. McManus. Multiphase mesh partitioning. Applied Mathematical Modelling, 25(2):123 – 140, 2000. Dynamic load balancing of mesh-based applications on parallel. [26] S. A. Weil, K. T. Pollack, S. A. Brandt, and E. L. Miller. Dynamic metadata management for petabyte-scale file systems. In SC ’04: Proceedings of the 2004 ACM/IEEE conference on Supercomputing, page 4, Washington, DC, USA, 2004. IEEE Computer Society. [27] D. A. Wood, S. J. Eggers, G. Gibson, M. D. Hill, and J. M. Pendleton. An in-cache address translation mechanism. In ISCA ’86: Proceedings of the 13th annual international symposium on Computer architecture, pages 358–365, Los Alamitos, CA, USA, 1986. IEEE Computer Society Press. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46243 | - |
dc.description.abstract | 本篇論文描述了一個在詮釋資料的樹狀結構上有效的分割演算法。在檔案系統、點對點的系統及格網系統上詮釋資料的查詢是相當重要的操作。在資源可以被充分運用之前,其相關的詮釋資料,如資源的位置及存取的權限,必須會先被讀取。於是有效的讀取資源的詮釋資料在整個系統的存取效率將會相當重要。
為了要改善詮釋資料查詢的效率,我們可以用多台分散式的詮釋資料伺服器。這篇論文專注在如何切割一個階層式詮釋資料架構而使得負載均勻的分佈在每台詮釋資料伺服器。我們令查詢中伺服器的轉換數為我們的成本,且提出了一個動態規劃的方式將樹狀詮釋資料分割成數個詮釋資料伺服器,使得所有詮釋資料伺服器中的最大成本達到最小化。此外,我們提出了一些優化技巧能夠降低動態規劃演算法的時間複雜度。我們也考慮了當詮釋資料的查詢數目發生動態的改變之情況。在我們大量的實驗結果說明了在最佳化之後的程序在執行時間上相當有效率,而且有效的使工作量不均達到最小化。 | zh_TW |
dc.description.abstract | This dissertation describes an efficient partitioning algorithm for metadata trees. Metadata querying is an important operation in file systems, peer-to-peer systems, and grid information systems. Before a resource can be utilized, the related metadata, such as the resource's location and permission to access it, must be obtained. Consequently, efficient retrieval of a resource's metadata is very important to the overall access efficiency of a system.
To improve the efficiency of metadata querying we can use multiple distributed metadata servers. This dissertation focuses on how to partition a hierarchical metadata structure so that the query workload is distributed evenly among multiple metadata servers. We take the number of transitions from one server to another as the cost of a query, and propose a dynamic programming approach that partitions the metadata tree so that the maximum cost to each server is minimized. In addition, we propose optimization techniques that reduce the time complexity of the dynamic programming procedure. We also consider the case where the metadata request pattern is dynamically changing. The results of extensive experiments demonstrate that applying the procedure after optimization is efficient in terms of the run time, and effective in minimizing the workload imbalance. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T04:59:38Z (GMT). No. of bitstreams: 1 ntu-99-R97922061-1.pdf: 519697 bytes, checksum: 175c95099e3513b396b90541ba2c532b (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | Certification i
Acknowledgement ii Chinese Abstract iii Abstract iv 1 Introduction 1 2 Related Work 3 3 System Model 5 3.1 Query Answering Trees ............................... 7 4 Dynamic Programming 10 4.1 Cost function....................................10 4.2 One Jump Edge...................................11 4.3 Two Jump Edges..................................12 4.4 Zero Jump Edges..................................13 4.5 Final Solution....................................14 4.6 General Trees....................................14 4.7 Time Complexity..................................14 4.8 Binary Search....................................15 4.9 Server Number Upper Bound............................ 16 4.9.1 Optimization on Two Coordinates.....................16 4.9.2 Optimization................................19 5 Dynamic Partitioning 21 5.1 Adjusting Algorithm................................22 6 Performance Evaluation 25 6.1 Static Partitioning..................................25 6.2 Dynamic Partitioning................................29 7 Conclusion and Future Work 30 Bibliography 31 | |
dc.language.iso | en | |
dc.title | 大型分散式儲存系統之詮釋資料動態切割方法 | zh_TW |
dc.title | Dynamic Metadata Partitioning for Large-Scale Distributed Storage Systems | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 吳真貞(Jan-Jan Wu) | |
dc.contributor.oralexamcommittee | 王大為(Da-wei Wang) | |
dc.subject.keyword | 詮釋資料切割,分散式系統,大型資料儲存,動態切割,負載平衡, | zh_TW |
dc.subject.keyword | metadata partitioning,distributed file system,large-scale data storage,dynamic partitioning,load balancing, | en |
dc.relation.page | 33 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-07-29 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 507.52 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。