by Ho Kei Shiu Edward. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1992. / Includes bibliographical references (leaves 199-202). / Acknowledgement / Abstract / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Initial Motivations --- p.1 / Chapter 1.2 --- Objectives of Our Study --- p.2 / Chapter 1.3 --- Outline of the Thesis --- p.3 / Chapter Chapter 2 --- Basics of the Procedure Graph Theory --- p.6 / Chapter 2.1 --- Introducing Procedure Graph Theory --- p.6 / Chapter 2.1.1 --- "Nodes, Arcs and Pseudo-time Labels" --- p.7 / Chapter 2.2 --- Examples --- p.12 / Chapter 2.3 --- Exploring the Meanings of the Pseudo-time Labels --- p.13 / Chapter 2.4 --- Equivalence and Transformation --- p.16 / Chapter 2.4.1 --- Equivalence --- p.16 / Chapter 2.4.2 --- Transmission Track and Causality Preservation --- p.16 / Chapter 2.4.3 --- Transformation --- p.17 / Chapter 2.4.3.1 --- Serial-to-Parallel Transformations (SP) --- p.18 / Chapter 2.4.3.2 --- Parallel-to-Serial Transformations (PS) --- p.20 / Chapter 2.4.3.3 --- Store-Store Cancellations (SSC) --- p.21 / Chapter 2.4.3.4 --- Normalization of Pseudo-time Labels --- p.23 / Chapter 2.4.3.5 --- Boundary Conditions and Multi-level Pseudo-time Labels --- p.24 / Chapter 2.5 --- Procedure Graph Optimizations --- p.28 / Chapter 2.5.1 --- Representing Dependencies --- p.28 / Chapter 2.5.2 --- Eliminating Unnecessary Dependencies --- p.32 / Chapter 2.6 --- Simulation Program --- p.36 / Chapter 2.6.1 --- Preliminary Study Using the Simulation Program --- p.36 / Chapter 2.6.2 --- Economic Factors --- p.37 / Chapter 2.6.3 --- Combinatorial Explosion of Procedure Graphs --- p.38 / Chapter Chapter 3 --- Extending the Procedure Graph Theory --- p.45 / Chapter 3.1 --- The T-Operator and the F-Operator --- p.45 / Chapter 3.2 --- Modifying the Firing Rule --- p.46 / Chapter 3.3 --- Procedure Graph Representation for Different Branch Strategies --- p.49 / Chapter 3.3.1 --- Multiple-Path Execution --- p.49 / Chapter 3.3.2 --- Conditional Execution with Delayed Commitment of Results --- p.51 / Chapter 3.3.3 --- Speculative Execution with Register Backup and Branch Repair --- p.52 / Chapter 3.4 --- Procedure Graph Representation for a Stack --- p.56 / Chapter 3.5 --- Vector Forwarding --- p.58 / Chapter 3.5.1 --- An Example of Vector Chaining in Cray-1 --- p.58 / Chapter 3.5.2 --- "Vector SP, PS and SSC" --- p.59 / Chapter 3.5.3 --- A Note Concerning the Use of Algorithmic Time Labels --- p.61 / Chapter 3.5.4 --- Further Consideration of Vector Forwarding --- p.62 / Chapter Chapter 4 --- Hardware Realization of Procedure Graph Optimizations --- p.64 / Chapter 4.1 --- Node-Oriented Versus Arc-Oriented Representation --- p.64 / Chapter 4.2 --- Backward Pointers Versus Forward Pointers --- p.65 / Chapter 4.3 --- Backward Pointers as Hardware Tags --- p.69 / Chapter 4.4 --- Pointer Algebra --- p.72 / Chapter 4.4.1 --- Serial-to-Parallel Transformations --- p.72 / Chapter 4.4.2 --- Store-Store Cancellations --- p.73 / Chapter 4.4.3 --- Parallel-to-Serial Transformations --- p.74 / Chapter 4.5 --- Drawbacks of Using Backward Pointers --- p.75 / Chapter 4.6 --- Multiple Tags --- p.76 / Chapter Chapter 5 --- A Backward-Pointer Representation Scheme :The T-Architecture --- p.82 / Chapter 5.1 --- The T-Architecture --- p.82 / Chapter 5.2 --- Local Addressing Space Within the CPU --- p.83 / Chapter 5.3 --- Why Reservation Stations --- p.84 / Chapter 5.4 --- Memory Data Forwarding --- p.89 / Chapter 5.4.1 --- The Updating Buffer --- p.90 / Chapter 5.4.2 --- Ordering and Consistency --- p.96 / Chapter 5.4.2.1 --- Store After Store --- p.96 / Chapter 5.4.2.2 --- Store After Load --- p.97 / Chapter 5.5 --- Speculative Execution --- p.97 / Chapter 5.5.1 --- Procedural Dependencies --- p.97 / Chapter 5.5.2 --- Branch Instruction Format --- p.98 / Chapter 5.5.3 --- Branch Prediction --- p.99 / Chapter 5.5.4 --- Branch Instruction Unit --- p.99 / Chapter 5.5.5 --- Register Backups --- p.100 / Chapter 5.5.5.1 --- Branch is Correctly Predicted --- p.101 / Chapter 5.5.5.2 --- Branch Repair --- p.102 / Chapter 5.5.5.3 --- Example --- p.102 / Chapter 5.5.6 --- Total Ordering Memory Stores --- p.110 / Chapter 5.5.7 --- Simplifying the Checkpoint Repair Mechanism --- p.112 / Chapter 5.6 --- A Simulator for the T-Architecture --- p.113 / Chapter 5.6.1 --- Basic Configuration of the Simulator --- p.114 / Chapter 5.6.2 --- Parameters of the Simulator --- p.115 / Chapter 5.6.3 --- Benchmark Programs --- p.116 / Chapter 5.7 --- Experiments --- p.118 / Chapter 5.7.1 --- Experiment1 --- p.119 / Chapter 5.7.2 --- Experiment2 --- p.121 / Chapter 5.7.3 --- Experiment3 --- p.123 / Chapter 5.7.4 --- Experiment4 --- p.127 / Chapter Chapter 6 --- Predictive Procedure Graph Optimizations in the S-Prototype --- p.137 / Chapter 6.1 --- Keys to Higher Performance --- p.138 / Chapter 6.2 --- The Superscalar Approach --- p.139 / Chapter 6.3 --- Processor Architecture of the S-Prototype --- p.139 / Chapter 6.4 --- Design Strategies of the S-Prototype --- p.141 / Chapter 6.4.1 --- Fetching Multiple Instructions --- p.142 / Chapter 6.4.2 --- Handling Procedural Dependencies : Branching Instructions --- p.142 / Chapter 6.4.2.1 --- Branch Unit and Branch Predicting Buffer --- p.143 / Chapter 6.4.2.2 --- Branch Repairing - Recovering Machine State --- p.144 / Chapter 6.4.3 --- Extensive Tagging and Result Forwarding --- p.147 / Chapter 6.4.4 --- Static and Dynamic Data Dependencies --- p.148 / Chapter 6.4.4.1 --- Handling Static Dependencies by using the Multitag Pool --- p.149 / Chapter 6.4.4.2 --- Handling Dynamic Dependencies by using the Reservation Stations --- p.150 / Chapter 6.4.5 --- Extracting Parallelism --- p.152 / Chapter 6.4.5.1 --- Representing Data Dependency in the Multitag Pool --- p.153 / Chapter 6.4.5.2 --- Implementing Transformation Rules --- p.156 / Chapter 6.4.6 --- Out-of-order Issue and Execution --- p.157 / Chapter 6.4.7 --- Memory Accesses --- p.158 / Chapter 6.4.8 --- Bus Contention and Arbitration --- p.160 / Chapter Chapter 7 --- An Attempt To Simulate Procedure Graphs Using Graph Grammar --- p.161 / Chapter 7.1 --- Introducing Graph Grammar --- p.161 / Chapter 7.2 --- Basic Concepts in Sequential Graph Grammar --- p.161 / Chapter 7.2.1 --- Production Rules and Interface Graph --- p.162 / Chapter 7.2.2 --- Gluing Constructions and Pushouts --- p.162 / Chapter 7.2.3 --- Gluing Conditions --- p.163 / Chapter 7.3 --- Initial Considerations to Simulate Procedure Graphs --- p.165 / Chapter 7.4 --- Example --- p.165 / Chapter 7.5 --- Problems Encountered --- p.167 / Chapter 7.6 --- Some Insights into the Unsolved Problem --- p.168 / Chapter 7.7 --- "Parallelism, Concurrency and New Transformation Rules" --- p.171 / Chapter Chapter 8 --- Representing Causality Using Petri Nets --- p.175 / Chapter 8.1 --- Defining Petri Nets --- p.175 / Chapter 8.1.1 --- Petri Nets as a Tool for System Modeling --- p.176 / Chapter 8.1.2 --- The Characteristics of a Petri Net --- p.177 / Chapter 8.1.3 --- Useful Extensions --- p.178 / Chapter 8.2 --- Program Analysis and Modeling Computer Operations --- p.179 / Chapter 8.2.1 --- Representing Causality Relationships --- p.180 / Chapter 8.2.2 --- Representing the Total Ordering of Instructions in a Sequential Program --- p.184 / Chapter 8.3 --- Extending the Model --- p.186 / Chapter 8.4 --- Comparing Procedure Graphs and Petri Nets --- p.188 / Chapter Chapter 9 --- Conclusion and Future Research Directions --- p.190 / Chapter 9.1 --- Formalizing the Procedure Graph Theory --- p.190 / Chapter 9.2 --- Mathematical Properties of Procedure Graphs --- p.191 / Chapter 9.3 --- Register Abuses --- p.192 / Chapter 9.4 --- Hardware Representation of Procedure Graphs --- p.194 / Chapter 9.5 --- Tags Describing Tags --- p.196 / Chapter 9.6 --- Software Optimizations --- p.197 / Chapter 9.7 --- Simulation Programs --- p.198 / References --- p.199

by He Zhaokui. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (leaves 81-82). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.5 / Chapter 2 --- Preliminaries --- p.8 / Chapter 2.1 --- The Laplacian of a compact manifold --- p.8 / Chapter 2.2 --- The Laplacian of a graph --- p.9 / Chapter 2.3 --- Some basic facts about the eigenvalues of a graph --- p.13 / Chapter 3 --- Bound of the first non-zero eigenvalue in terms of Cheeger constant --- p.18 / Chapter 3.1 --- The Cheeger constant --- p.18 / Chapter 3.2 --- The Cheeger inequality of a compact manifold --- p.19 / Chapter 3.3 --- The Cheeger inequality of a graph --- p.23 / Chapter 4 --- Diameters and eigenvalues --- p.27 / Chapter 4.1 --- Some facts --- p.27 / Chapter 4.2 --- Estimate the eigenvalues of graphs --- p.29 / Chapter 4.3 --- The heat kernel of compact manifolds --- p.34 / Chapter 4.4 --- Estimate the eigenvalues of manifolds --- p.35 / Chapter 5 --- Harnack inequality and eigenvalues on homogeneous graphs --- p.40 / Chapter 5.1 --- Preliminaries --- p.40 / Chapter 5.2 --- The Neumann eigenvalue of a subgraph --- p.41 / Chapter 5.3 --- The Harnack inequality --- p.44 / Chapter 5.4 --- A lower bound of the first non-zero eigenvalue --- p.52 / Chapter 6 --- Harnack inequality and eigenvalues on compact man- ifolds --- p.54 / Chapter 6.1 --- Gradient estimate --- p.54 / Chapter 6.2 --- Lower bounds for the first non-zero eigenvalue --- p.59 / Chapter 7 --- Heat kernel and eigenvalues of graphs --- p.63 / Chapter 7.1 --- The heat kernel of a graph --- p.54 / Chapter 7.2 --- Lower bounds for eigenvalues --- p.70 / Chapter 8 --- Estimate the eigenvalues of a compact manifold --- p.73 / Chapter 8.1 --- An isoperimetric constant --- p.75 / Chapter 8.2 --- A lower estimate for the (m + l)-st eigenvalue --- p.77

在給定圖類II的II收縮問題中，對于任意的輸入圖G和參數k，該問題詢問能否收縮G中的至多k條邊使得到的新圖屬于類II。此問題與諸多圖算法問題相關聯，且在之前的文獻中有較多研究成果。 / 在本文中我們將研究圖收縮問題對于不同的類II的參數化復雜度。我們首先給出完全圖收縮問題的FPT算法。并且相較于另兩個已知的FPT問題：弦圖删邊問題及弦圖增邊問題，我們證明弦圖收縮問題是W[2]難問題。我們還將說明當H為一個特定的圈、路、星圖時，無H收縮問題是W[2]難問題，并且給出對所有連通度至少為3的圖H，無H收縮問題之參數化復雜度的一個完備界定。此外，我們證明了任意的無完全圖收縮問題、完全二分圖收縮問題以及分裂圖收縮問題都是FPT時間可解決，并且這些問題都不大可能包含多項式核心。 / 除此之外，我們將研究諸如點染色問題及支配集問題等經典NP難問題在一類特殊參數化圖上的參數化復雜度。 / 我們相信本文對于圖收縮問題的研究有著重要的貢獻，同時文中的一些思想和方法也將有助于對此問題進一步的研究。 / The II-Contraction problem is to determine whether an input graph G can be modified into a graph belonging to a desired class II by contracting at most k edges. It is closely related to graph minors and graph modification problems, and has been studied in the literature for several classes II. / In this thesis, we study parameterized complexity of II-Contraction problems in terms of graph classes II. We present FPT algorithms for Clique Contraction, which is the dual of a well-known FPT problem: Maximum Clique Minor. In contrast to FPT of Chordal Deletion and Chordal Completion, we prove the W[2]-hardness of Chordal Contraction. We also show that H-Free Contraction is W[2]-hard whenever H is a fixed graph that is a cycle C₁ for l≥4, an odd path P₁ for l≥5, a star K₁,[subscript r] for r≥4 or a diamond, and completely characterize the parameterized complexity of H-Free Contraction for every fixed 3-connected H. Moreover, we prove that K[subscript t]-free Contraction for every fixed t≥3, Biclique Contraction and Split Contraction are FPT but have no polynomial kernels unless NP ⊆ coNP/poly. / Furthermore, we study the parameterized complexity of some NP-complete classical problems such as Vertex Coloring and Dominating Set on F↑ke graphs, which are graphs that can be made into F-graphs by contracting at most k edges. / We believe that the thesis has made an important contribution to the study of graph contraction problems, and our ideas and techniques will be useful to future studies of graph contraction problems. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Guo, Chengwei. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 109-117). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.3 / Chapter 1.1.1 --- Graph minors --- p.3 / Chapter 1.1.2 --- Graph modification problems --- p.4 / Chapter 1.1.3 --- Previous results for edge contraction --- p.5 / Chapter 1.2 --- Organization of the thesis --- p.6 / Chapter 2 --- Notation and definitions --- p.9 / Chapter 2.1 --- Basic notations on graphs --- p.9 / Chapter 2.2 --- Parameterized complexity --- p.12 / Chapter 3 --- FPT algorithms for -Contraction --- p.16 / Chapter 3.1 --- General results --- p.17 / Chapter 3.1.1 --- FPT algorithm for bounded-degree graphs --- p.17 / Chapter 3.1.2 --- Kernelization of special graph families --- p.18 / Chapter 3.1.3 --- Component theorem for H-Free Contraction . --- p.19 / Chapter 3.2 --- Contraction to clique-free graphs --- p.21 / Chapter 3.3 --- Contraction to cliques --- p.23 / Chapter 3.3.1 --- FPT algorithm for Clique Contraction --- p.24 / Chapter 3.3.2 --- Kernelization of Clique Contraction --- p.29 / Chapter 3.4 --- Contraction to bicliques --- p.32 / Chapter 3.4.1 --- Kernelization of Biclique Contraction --- p.33 / Chapter 3.5 --- Contraction to split graphs --- p.34 / Chapter 3.5.1 --- FPT algorithm for Split Contraction --- p.35 / Chapter 4 --- Hardness of H-Free Contraction --- p.40 / Chapter 4.1 --- Contraction to cycle-free graphs --- p.42 / Chapter 4.1.1 --- Cl-Free Contraction --- p.42 / Chapter 4.1.2 --- Chordal Contraction --- p.44 / Chapter 4.2 --- Contraction to path-free graphs --- p.45 / Chapter 4.2.1 --- Odd path --- p.45 / Chapter 4.2.2 --- Even path --- p.47 / Chapter 4.3 --- Contraction to star-free graphs --- p.49 / Chapter 4.4 --- Contraction to diamond-free graphs --- p.54 / Chapter 4.5 --- 3-connected H --- p.56 / Chapter 5 --- Incompressibility --- p.62 / Chapter 5.1 --- General techniques --- p.63 / Chapter 5.2 --- Incompressibility of clique-free contraction problems --- p.64 / Chapter 5.3 --- Incompressible of other -Contraction problems --- p.72 / Chapter 5.4 --- Conjecture for Clique Contraction --- p.77 / Chapter 6 --- Parameterized graph families --- p.81 / Chapter 6.1 --- Background and general results --- p.82 / Chapter 6.2 --- Clique ↑ ke graphs --- p.84 / Chapter 6.3 --- Other graph classes --- p.89 / Chapter 7 --- Concluding remarks --- p.93 / Chapter 7.1 --- Summary --- p.93 / Chapter 7.2 --- Open problems on edge contraction --- p.95 / Chapter 7.3 --- Related graph operations --- p.97 / Chapter 7.3.1 --- Vertex merging --- p.97 / Chapter 7.3.2 --- Neighborhood contraction --- p.99 / Chapter A --- Graph classes --- p.102 / Bibliography --- p.109

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1979. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Vita. / Bibliography: leaves 74-75. / Ph.D.

Thesis. 1975. Ph.D.--Massachusetts Institute of Technology. Dept. of Mathematics. / Vita. / Includes bibliographical references. / Ph.D.

In this dissertation, we present three results related to combinatorial algorithms in graph theory and scheduling, both of which are important subjects in the area of discrete mathematics and theoretical computer science. In graph theory, a graph is a set of vertices and edges, where each edge is a pair of vertices. A coloring of a graph is a function that assigns each vertex a color such that no two adjacent vertices share the same color. The first two results are related to coloring graphs belonging to specific classes. In scheduling problems, we are interested in how to efficiently schedule a set of jobs on machines. The last result is related to a scheduling problem in an environment where there is uncertainty on the number of machines. The first result of this thesis is a polynomial time algorithm that determines if an input graph containing no induced seven-vertex path is 3-colorable. This affirmatively answers a question posed by Randerath, Schiermeyer and Tewes in 2002. Our algorithm also solves the list-coloring version of the 3-coloring problem, where every vertex is assigned a list of colors that is a subset of {1, 2, 3}, and gives an explicit coloring if one exists. This is joint work with Flavia Bonomo, Maria Chundnovsky, Peter Maceli, Oliver Schaudt, and Maya Stein. A graph is H-free if it has no induced subgraph isomorphic to H. In the second part of this thesis, we characterize all graphs $H$ for which there are only finitely many minimal non-three-colorable H-free graphs. This solves a problem posed by Golovach et al. We also characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability. This is joint work with Maria Chudnovsky, Jan Goedgebeur and Oliver Schaudt. The last result of this thesis deals with a scheduling problem addressing the uncertainty regarding the machines. We study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. In order to evaluate algorithms in such an environment, we introduce the idea of an alpha-robust algorithm, one which is guaranteed to return a schedule on any number m of machines that is within an alpha factor of the optimal schedule on m machines, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a (5/3+epsilon)-robust algorithm for scheduling on parallel machines to minimize makespan, and show a lower bound of 4/3. For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. This is joint work with Clifford Stein.

No description available.

Wang, Dingyan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 97-110). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgement --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Motivations --- p.6 / Chapter 1.3 --- Contributions --- p.9 / Chapter 1.4 --- Organizations of This Thesis --- p.11 / Chapter 2 --- Background --- p.14 / Chapter 2.1 --- Label Propagation Learning Framework --- p.14 / Chapter 2.1.1 --- Graph-based Semi-supervised Learning --- p.14 / Chapter 2.1.2 --- Green's Function Learning Framework --- p.16 / Chapter 2.2 --- Recommendation Methods --- p.19 / Chapter 2.2.1 --- Traditional Memory-based Methods --- p.19 / Chapter 2.2.2 --- Traditional Model-based Methods --- p.20 / Chapter 2.2.3 --- Label Propagation Recommendation Models --- p.22 / Chapter 2.2.4 --- Latent Feature Recommendation Models . --- p.24 / Chapter 2.2.5 --- Social Recommendation Models --- p.25 / Chapter 2.2.6 --- Tag-based Recommendation Models --- p.25 / Chapter 3 --- Recommendation with Latent Features --- p.28 / Chapter 3.1 --- Motivation and Contributions --- p.28 / Chapter 3.2 --- Item Graph --- p.30 / Chapter 3.2.1 --- Item Graph Definition --- p.30 / Chapter 3.2.2 --- Item Graph Construction --- p.31 / Chapter 3.3 --- Label Propagation Recommendation Model with Latent Features --- p.33 / Chapter 3.3.1 --- Latent Feature Analysis --- p.33 / Chapter 3.3.2 --- Probabilistic Matrix Factorization --- p.35 / Chapter 3.3.3 --- Similarity Consistency Between Global and Local Views (SCGL) --- p.39 / Chapter 3.3.4 --- Item-based Green's Function Recommendation Based on SCGL --- p.41 / Chapter 3.4 --- Experiments --- p.41 / Chapter 3.4.1 --- Dataset --- p.43 / Chapter 3.4.2 --- Baseline Methods --- p.43 / Chapter 3.4.3 --- Metrics --- p.45 / Chapter 3.4.4 --- Experimental Procedure --- p.45 / Chapter 3.4.5 --- Impact of Weight Parameter u --- p.46 / Chapter 3.4.6 --- Performance Comparison --- p.48 / Chapter 3.5 --- Summary --- p.50 / Chapter 4 --- Recommendation with Social Network --- p.51 / Chapter 4.1 --- Limitation and Contributions --- p.51 / Chapter 4.2 --- A Social Recommendation Framework --- p.55 / Chapter 4.2.1 --- Social Network --- p.55 / Chapter 4.2.2 --- User Graph --- p.57 / Chapter 4.2.3 --- Social-User Graph --- p.59 / Chapter 4.3 --- Experimental Analysis --- p.60 / Chapter 4.3.1 --- Dataset --- p.61 / Chapter 4.3.2 --- Metrics --- p.63 / Chapter 4.3.3 --- Experiment Setting --- p.64 / Chapter 4.3.4 --- Impact of Control Parameter u --- p.65 / Chapter 4.3.5 --- Performance Comparison --- p.67 / Chapter 4.4 --- Summary --- p.69 / Chapter 5 --- Recommendation with Tags --- p.71 / Chapter 5.1 --- Limitation and Contributions --- p.71 / Chapter 5.2 --- Tag-Based User Modeling --- p.75 / Chapter 5.2.1 --- Tag Preference --- p.75 / Chapter 5.2.2 --- Tag Relevance --- p.78 / Chapter 5.2.3 --- User Interest Similarity --- p.80 / Chapter 5.3 --- Tag-Based Label Propagation Recommendation --- p.83 / Chapter 5.4 --- Experimental Analysis --- p.84 / Chapter 5.4.1 --- Douban Dataset --- p.85 / Chapter 5.4.2 --- Experiment Setting --- p.86 / Chapter 5.4.3 --- Metrics --- p.87 / Chapter 5.4.4 --- Impact of Tag and Rating --- p.88 / Chapter 5.4.5 --- Performance Comparison --- p.90 / Chapter 5.5 --- Summary --- p.92 / Chapter 6 --- Conclusions and Future Work --- p.94 / Chapter 6.0.1 --- Conclusions --- p.94 / Chapter 6.0.2 --- Future Work --- p.96 / Bibliography --- p.97

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