Typescript (photocopy). / Digitized by Kansas Correctional Industries / Department: Computer Science.

重覆數據删除技術是一個消除冗餘數據存儲塊的技術。尤其是，在儲存數兆位元組的虛擬機器影像時，它已被證明可以減少使用磁碟空間。但是，在會經常加入和讀取虛擬機器影像的雲端平台，部署重覆數據删除技術仍然存在挑戰。我們提出了一個在內核運行的重覆數據删除檔案系統LiveDFS，它可以在一個在低成本硬件配置的開源雲端平台中作為儲存虛擬機器影像的後端。LiveDFS有幾個新穎的特點。具體來說，LiveDFS中最重要的特點是在考慮檔案系統佈局時，它利用空間局部性放置重覆數據删除中繼資料。LiveDFS是POSIX兼容的Linux內核檔案系統。我們透過使用42個不同Linux發行版的虛擬機器影像，在實驗平台測試了LiveDFS的讀取和寫入性能。我們的工作證明了在低成本硬件配置的雲端平台部署LiveDFS的可行性。 / Deduplication is a technique that eliminates the storage of redundant data blocks. In particular, it has been shown to effectively reduce the disk space for storing multi-gigabyte virtual machine (VM) images. However, there remain challenging deployment issues of enabling deduplication in a cloud platform, where VM images are regularly inserted and retrieved. We propose a kernel-space deduplication file systems called LiveDFS, which can serve as a VM image storage backend in an open-source cloud platform that is built on low-cost commodity hardware configurations. LiveDFS is built on several novel design features. Specifically, the main feature of LiveDFS is to exploit spatial locality of placing deduplication metadata on disk with respect to the underlying file system layout. LiveDFS is POSIX-compliant and is implemented as Linux kernel-space file systems. We conduct testbed experiments of the read/write performance of LiveDFS using a dataset of 42 VM images of different Linux distributions. Our work justifies the feasibility of deploying LiveDFS in a cloud platform under commodity settings. / Detailed summary in vernacular field only. / Ng, Chun Ho. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 39-42). / Abstracts also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- LiveDFS Design --- p.5 / Chapter 2.1 --- File System Layout --- p.5 / Chapter 2.2 --- Deduplication Primitives --- p.6 / Chapter 2.3 --- Deduplication Process --- p.8 / Chapter 2.3.1 --- Fingerprint Store --- p.9 / Chapter 2.3.2 --- Fingerprint Filter --- p.11 / Chapter 2.4 --- Prefetching of Fingerprint Stores --- p.14 / Chapter 2.5 --- Journaling --- p.15 / Chapter 2.6 --- Ext4 File System --- p.17 / Chapter 3 --- Implementation Details --- p.18 / Chapter 3.1 --- Choice of Hash Function --- p.18 / Chapter 3.2 --- OpenStack Deployment --- p.19 / Chapter 4 --- Experiments --- p.21 / Chapter 4.1 --- I/O Throughput --- p.21 / Chapter 4.2 --- OpenStack Deployment --- p.26 / Chapter 5 --- Related Work --- p.34 / Chapter 6 --- Conclusions and Future Work --- p.37 / Bibliography --- p.39

In the second part, we further investigate algebraic structure of relational databases. The decomposition theory for relational databases is based on data dependencies. Nevertheless, the set-theoretic representations of data dependencies in terms of the attributes of relation schemes are incompatible with partial ordering operations. This brings a gap between the database decomposition theory and our theory. We identify the unique component constraint as a necessary condition for binary decomposition of a relation, i.e. there is a unique component for every join key value in the bipartite graph. We generalize the running intersection property as the partial ordering counterpart under the unique component constraint. It follows that we characterize the multivalued and acyclic join dependencies in terms of commutativity and unique component constraint. This shows the decompositions specified by these dependencies are special cases of our theory. Furthermore, we propose a lossless decomposition method for the class of data dependencies that is based on commutativity, and demonstrate that existing relational operations are sufficient for this method. / Relational information systems, systems that can be represented by tables of finite states, are widely used in many areas such as logic circuits, finite state machines, and relational databases. Decomposition is a natural method to remove redundancy of complex systems. It divides a system into a network of simpler components. In order to preserve the original functionalities of the system, any valid decomposition has to be lossless. This work is divided into two parts. In the first part, we develop a mathematical model for lossless decompositions of relational information systems. Commutative partitions play an important role in decompositions. The commutativity is essentially a general algebraic formulation of independency of two partitions. We express the interdependency of two commutative partitions by a bipartite graph, and classify the hierarchical independency structures by the topological property of bipartite graphs. In particular, we show that two partitions are decomposable, the strongest kind of independency, if and only if the associated bipartite graph is uniform. Moreover, we adopt Shannon's entropy to quantify the amount of information contained in each partition, and formulate information-lossless decompositions by entropy equalities. Under the assumption of running intersection property, we show that the general formulation of information-lossless decompositions of relational information systems is given by the entropy inclusion-exclusion equality. We also present the applications of these formulations to the above engineering systems to manifest the information-lossless decomposition processes. / Lo, Ying Hang. / Adviser: Tony T. Lee. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3606. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 159-163). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

by Huidong Jin. / "August 2002." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (p. 193-204). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

by Qiuyue Wang. / "July 2002." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (p. 74-82). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web.

by Kuok, Chan Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 74-77). / Abstract --- p.i / Acknowledgments --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Data Mining --- p.2 / Chapter 1.2 --- Association Rule Mining --- p.3 / Chapter 2 --- Background --- p.6 / Chapter 2.1 --- Framework of Association Rule Mining --- p.6 / Chapter 2.1.1 --- Large Itemsets --- p.6 / Chapter 2.1.2 --- Association Rules --- p.8 / Chapter 2.2 --- Association Rule Algorithms For Binary Attributes --- p.11 / Chapter 2.2.1 --- AIS --- p.12 / Chapter 2.2.2 --- SETM --- p.13 / Chapter 2.2.3 --- "Apriori, AprioriTid and AprioriHybrid" --- p.15 / Chapter 2.2.4 --- PARTITION --- p.18 / Chapter 2.3 --- Association Rule Algorithms For Numeric Attributes --- p.20 / Chapter 2.3.1 --- Quantitative Association Rules --- p.20 / Chapter 2.3.2 --- Optimized Association Rules --- p.23 / Chapter 3 --- Problem Definition --- p.25 / Chapter 3.1 --- Handling Quantitative Attributes --- p.25 / Chapter 3.1.1 --- Discrete intervals --- p.26 / Chapter 3.1.2 --- Overlapped intervals --- p.27 / Chapter 3.1.3 --- Fuzzy sets --- p.28 / Chapter 3.2 --- Fuzzy association rule --- p.31 / Chapter 3.3 --- Significance factor --- p.32 / Chapter 3.4 --- Certainty factor --- p.36 / Chapter 3.4.1 --- Using significance --- p.37 / Chapter 3.4.2 --- Using correlation --- p.38 / Chapter 3.4.3 --- Significance vs. Correlation --- p.42 / Chapter 4 --- Steps For Mining Fuzzy Association Rules --- p.43 / Chapter 4.1 --- Candidate itemsets generation --- p.44 / Chapter 4.1.1 --- Candidate 1-Itemsets --- p.45 / Chapter 4.1.2 --- Candidate k-Itemsets (k > 1) --- p.47 / Chapter 4.2 --- Large itemsets generation --- p.48 / Chapter 4.3 --- Fuzzy association rules generation --- p.49 / Chapter 5 --- Experimental Results --- p.51 / Chapter 5.1 --- Experiment One --- p.51 / Chapter 5.2 --- Experiment Two --- p.53 / Chapter 5.3 --- Experiment Three --- p.54 / Chapter 5.4 --- Experiment Four --- p.56 / Chapter 5.5 --- Experiment Five --- p.58 / Chapter 5.5.1 --- Number of Itemsets --- p.58 / Chapter 5.5.2 --- Number of Rules --- p.60 / Chapter 5.6 --- Experiment Six --- p.61 / Chapter 5.6.1 --- Varying Significance Threshold --- p.62 / Chapter 5.6.2 --- Varying Membership Threshold --- p.62 / Chapter 5.6.3 --- Varying Confidence Threshold --- p.63 / Chapter 6 --- Discussions --- p.65 / Chapter 6.1 --- User guidance --- p.65 / Chapter 6.2 --- Rule understanding --- p.67 / Chapter 6.3 --- Number of rules --- p.68 / Chapter 7 --- Conclusions and Future Works --- p.70 / Bibliography --- p.74

Su Yat Fan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 91-95). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Our Objective --- p.4 / Chapter 1.3 --- The Organization of the Thesis --- p.5 / Chapter 2 --- Related Works --- p.7 / Chapter 2.1 --- Semi-structured Data --- p.7 / Chapter 2.1.1 --- What are Semi-structured Data? --- p.8 / Chapter 2.1.2 --- Examples of Semi-structured Data --- p.9 / Chapter 2.2 --- Object Exchange Model --- p.10 / Chapter 2.3 --- Regular Path Expressions --- p.12 / Chapter 2.4 --- Graph Schemas --- p.13 / Chapter 2.4.1 --- Accurate Graph Schemas: DataGuides --- p.15 / Chapter 2.4.2 --- Approximate Graph Schemas --- p.17 / Chapter 2.4.3 --- Conceptual Graphs (CG) --- p.19 / Chapter 2.5 --- Chapter Summary --- p.25 / Chapter 3 --- Query Evaluation and Characteristics of Conceptual Graphs --- p.27 / Chapter 3.1 --- Generation of Data Graphs --- p.28 / Chapter 3.2 --- Conceptual Graphs with Respect to Different Types of Data Graphs --- p.29 / Chapter 3.2.1 --- Experimental Setup --- p.29 / Chapter 3.2.2 --- Experimental Results --- p.30 / Chapter 3.3 --- Query Evaluation --- p.34 / Chapter 3.4 --- The Effect of Traversal Orders over Conceptual Graphs --- p.39 / Chapter 3.4.1 --- Experimental Setup --- p.39 / Chapter 3.4.2 --- Experimental Results --- p.40 / Chapter 3.5 --- Chapter Summary --- p.46 / Chapter 4 --- Problems in Conceptual Graphs --- p.47 / Chapter 4.1 --- False Paths in Conceptual Graphs --- p.50 / Chapter 4.2 --- Utility Function --- p.51 / Chapter 4.3 --- Information Incompleteness in the Construction Process --- p.53 / Chapter 4.4 --- Chapter Summary --- p.54 / Chapter 5 --- Refinement of the Utility Function --- p.55 / Chapter 5.1 --- """Attributes Or Roles"" Instead of ""Attributes and Roles""" --- p.56 / Chapter 5.2 --- Roles --- p.57 / Chapter 5.2.1 --- The New Utility Function with Only Roles Involved --- p.57 / Chapter 5.2.2 --- Query Evaluation Using Roles Only --- p.58 / Chapter 5.3 --- Attributes --- p.63 / Chapter 5.3.1 --- The New Utility Function Based on Attributes Only --- p.63 / Chapter 5.3.2 --- Query Evaluation Using Attributes Only --- p.64 / Chapter 5.4 --- A Reliability Test for Attribute-only Utility Function --- p.66 / Chapter 5.5 --- Chapter Summary --- p.70 / Chapter 6 --- New Operators for Conceptual Graph Construction --- p.74 / Chapter 6.1 --- The Original Algorithm --- p.74 / Chapter 6.2 --- Revised Algorithm with New Operators --- p.75 / Chapter 6.3 --- Query Evaluation of the Revised Algorithm --- p.79 / Chapter 6.3.1 --- Experimental Setup --- p.79 / Chapter 6.3.2 --- Evaluation Results --- p.80 / Chapter 6.4 --- Chapter Summary --- p.85 / Chapter 7 --- Conclusions --- p.87 / Chapter 7.1 --- Future Work --- p.89 / Bibliography --- p.91

No description available.

Database outsourcing is an emerging paradigm for data management in which data are stored in third-party servers. With the advance of cloud computing, database outsourcing has become popular and highly adopted. However, as a result, many technology challenges have arisen. / In this thesis, we study two problems with respect to the challenges, and propose solutions for each problem with the consideration of access patterns. The first problem is raised from theviewpoint of service providers. We study the problem of data allocation in scalable distributed database systems for achieving the high availability feature of cloud services. We propose a data allocation algorithm, which makes use of time series models from previous access patterns to perform load forecasting and reallocate data fragments to balance the workload within the system. Simulation results show that, with accurate forecasting, the proposed algorithm gives a better performance than general threshold-based algorithms. / The second problem addresses the clients' concern that service providers may not be trustworthy. We first illustrate how service providers can infer sensitive information through query access patterns even when data are encrypted. Then, we propose techniques that break down large queries and randomize query access patterns such that service providers cannot infer sensitive information with a high degree of certainty. Experiments on benchmark data show that a high level of access privacy can be achieved by the proposed techniques with a reasonable overhead. / 數據庫外包是近年新興的一種數據管理服務，其特點是數據儲存於第三方的伺服器內。隨著雲端科技的發展，數據庫外包服務日趨普及，同時亦產生不少技術問題。 / 本文著重探討兩個問題。首先，從服務供應商的角度研究可擴展的分布式數據庫系統如何分配數據來提供高可用性的雲端服務。鑑於用戶訪問模式會隨著時間轉變，我們提出以時間序列模型預測負荷的算法重新分配數據，以平衡系統的工作量。通過模擬實驗可知在準確的負荷預測下，我們提出的算法比基於闆值的算法有更好的表現。 / 第二個探討的問題是如何保障用戶私隱，避免洩露給服務供應商。文中列舉了數據加密的情況下，服務供應商如何通過分析用戶訪問模式獲取資料，進而提出相應的保障技術。透過用戶訪問模式的隨機化，能使服務供應商無法準確比對用戶的資料。基準數據實驗指出此項技術可有效保護私隱，而且不會對訪問速度造成太大影響。 / Li, Shun Pun. / Thesis M.Phil. Chinese University of Hong Kong 2015. / Includes bibliographical references (leaves 86-93). / Abstracts also in Chinese. / Title from PDF title page (viewed on 11, October, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.

Digitized by Kansas Correctional Industries