在給定圖類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

A new automatic compression scheme that adapts to any image set is presented in this thesis. The proposed scheme requires no a priori knowledge on the properties of the image set. This scheme is obtained using a unified graph-theoretical framework that allows for compression strategies to be compared both theoretically and experimentally. This strategy achieves optimal lossless compression by computing a minimum spanning tree of a graph constructed from the image set. For lossy compression, this scheme is near-optimal and a performance guarantee relative to the optimal one is provided. Experimental results demonstrate that this compression strategy compares favorably to the previously proposed strategies, with improvements up to 7% in the case of lossless compression and 72% in the case of lossy compression. This thesis also shows that the choice of underlying compression algorithm is important for compressing image sets using the proposed scheme. / x, 77 leaves ; 29 cm.

In this thesis we will describe the development of software functions that render graphical and textual information of G-Net(A software system for graph theory & algorithms) onto various raster output devices.Graphs are mathematical structures that are used to model very diverse systems such as networks, VLSI design, chemical compounds and many other systems where relations between objects play an important role. The study of graph theory problems requires many manipulative techniques. A software system (such as G-Net) that can automate these techniques will be a very good aid to graph theorists and professionals. The project G-Net, headed by Prof. Kunwarjit S. Bagga of the computer science department has the goal of developing a software system having three main functions. These are: learning basics of graph theory, drawing/manipulating graphs and executing graph algorithms.The thesis will begin with an introduction to graph theory followed by a brief description of the evolution of the G-Net system and its current status. To print on various printers, the G-Net system translates all the printable information into PostScript' files. A major part of this thesis concentrates on this translation. To begin with, the necessity of a standard format for the printable information is discussed. The choice of PostScript as a standard is then justified. Next,the design issues of translator and the translation algorithm are discussed in detail. The translation process for each category of printable information is explained. Issues of printing these PostScript files onto different printers are dealt with at the end. / Department of Computer Science

Ph.D. / In this thesis we undertake a study of formal three-dimensional representational and acceptor methods. In lieu hereof then, we give a short overview of such strategies existing in the literature. Graph and graph grammar theory present us with a powerful two dimensional representational method, and we propose to extend these concepts to the three-dimensional case. We therefore give a short discussion on the theory of graphs and graph grammars. As point of departure, we review the concepts of a structure parameter and structure graph (SG) introduced by us in [BEH,93] and show that these concepts enable us to describe objects in three-dimensional space. We propose various modified graph grammar extensions that generates structure graphs, referred to as Structure Graph Grammar extensions (SGG's) by combining context provisions with the rewriting rules of the various grammar systems. This proposed methodology of ours culminates in the combination of production rule bounded contexts and globally specified contexts, thus defining Structure Graph Grammar extension 7 (SGG-7). We show the applicative value of the three dimensional generative abilities of SGG's by considering the generation of various chemical structural formulae. Brandenburg and Skodinis mentions in [BS,95] that there is a shortcoming in the theory of graph grammars in the sense that in general, there exists no accepting device for graph grammar systems. The following quote from [BS,95,p.336] illustrates this point: "There are no graph automata, which fit to the major classes of graph languages. This is a gap in the theory of graph languages." Regarding the class of languages generated by SGG-7, we propose to fill this gap by introducing an Structure Graph Automaton (SGA) to accept this class of languages.

M.Sc. (Computer Science) / The purpose of this disssertation is to study methods to represent structures in three-dimensions. Due to the fact that chemical molecules are mostly complex three-dimensional structures, we used chemical molecules as our application domain. A literature study of current chemical information systems was undertaken. The whole spectrum of information systems was covered because almost all of these systems represent chemical molecules in one way or another. Various methods of three-dimensional structure representation were found in our literature study. All of these methods were discussed in the context of its own application domain. Structure graph grammars were examined and explained in detail. A small object-based system with structure graph grammars as the underlying principle was developed. We speculated on the use of such "intelligent" graph grammars in structure interpretation and identification. Further research in this area was also identified.

Besides finding changing areas based on the number of node and edge evolutions, a more interesting problem is to analyze the impact of these evolutions to graphs and find the regions that exhibit significant changes when these evolutions happen. The more different the relationship between nodes in a certain region is, the more significant this region is. This problem is challenging since it is hard to define the range of changing regions that is closely related to actual evolutions. We formalize the problem by using a similarity measure based on neighborhood random walks, and design an efficient algorithm which is able to identify the significant changing regions without recomputing all similarities. Meaningful examples in experiments demonstrate the effectiveness of our algorithms. / Graph patterns are able to represent the complex structural relations among objects in many applications in various domains. Managing and mining graph data, on which we study in this thesis, are no doubt among the most important tasks. We focus on two challenging problems, namely, graph summarization and graph change detection. / In the area of summarizing a collection of graphs, we study the problem of summarizing frequent subgraphs, since it is not much necessary to summarize a collection of random graphs. The bottleneck for exploring and understanding frequent subgraphs is that they are numerous. A summary can be a solution to this issue, so the goal of frequent subgraph summarization is to minimize the restoration errors of the structure and the frequency information. The unique challenge in frequent subgraph summarization comes from the fact that a subgraph can have multiple embeddings in a summarization template graph. We handle this issue by introducing a partial order between edges to allow accurate structure and frequency estimation based on an independence probabilistic model. The proposed algorithm discovers k summarization templates in a top-down fashion to control the restoration error of frequencies within sigma. There is no restoration error of structures. Experiments on both real and synthetic graph datasets show that our framework can control the frequency restoration error within 10% by a compact summarization model. / The objective of graph change detection is to discover the changing areas on graphs when they evolves at a high speed. The most changing areas are those areas having the highest number of evolutions (additions/deletions) of nodes and edges, which is called burst areas. We study on finding the most burst areas in a stream of fast graph evolutions. We propose to use Haar wavelet tree to monitor the upper bound of the number of evolutions. Our approach monitors all potential changing areas of different sizes and computes incrementally the number of evolutions in those areas. The top-k burst areas are returned as soon as they are detected. Our solution is capable of handling a large amount of evolutions in a short time, which is consistent to the experimental results. / The objective of graph summarization is to obtain a concise representation of a single large graph or a collection of graphs, which is interpretable and suitable for analysis. A good summary can reveal the hidden relationships between nodes in a graph. The key issue of summarizing a single graph is how to construct a high-quality and representative summary, which is in the form of a super-graph. We propose an entropy-based unified model for measuring the homogeneity of the super-graph. The best summary in terms of homogeneity could be too large to explore. By using the unified model, we relax three summarization criteria to obtain an approximate homogeneous summary of appropriate size. We propose both agglomerative and divisive algorithms for approximate summarization, as well as pruning techniques and heuristics for both algorithms to save computation cost. Experimental results confirm that our approaches can efficiently generate high-quality summaries. / Liu, Zheng. / Advisers: Wai Lam; Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 73-06, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 133-141). / 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, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

图结构能够描述数据对象之间的复杂关系，因而被广泛应用于多种领域。随着相关应用领域的发展，图数据库的规模变得庞大且仍在不断增长。这给研究者在图查询和图挖掘方面带来新的挑战。本文主要研究以下三个问题：如何确定两个图的顶点对应关系，使得其中一个图的子结构匹配到另一个图的相似子结构；如何从含有多个小图的数据库中，找到与查询图相似的图；如何在由不同类别的图组成的数据库中，选取特征子图并对图进行分类。 / 在本文中，对于第一个问题，我们提出了新的两段式图匹配算法。在第一阶段，我们采用了一个新的启发式策略，能够先选取锚顶点并向外扩展，进而快速得到初始匹配。在第二阶段，我们设计了新的算法对初始匹配加以改进，并且证明了新的匹配优于初始匹配。这个两段式图匹配算法能够快速有效地获得两个图的高质量匹配。为解决第二个问题，我们首先定义一个新的度量以衡量两图间的距离。它基于两图间的最大公共子图，能够很好地捕捉两个图的相同及不同之处。由于最大公共子图的计算是NP完全问题，为了快速回答top-k相似图查询，我们提出了一个高效算法，能够极大地减少最大公共子图的计算次数。这个算法根据距离度量的三种下界进行剪枝以筛选掉不合格的图。其中，前两种下界的计算基于两图的结构信息，第三种下界可由距离度量的三角不等式性质推出。我们还设计了三种不同的索引结构来支持剪枝，它们能够在剪枝效果和索引时间方面达到不同程度的平衡。关于第三个问题，我们发现了目前广泛使用的特征判别函数的两个主要缺陷，并据此提出了一个新的多样性特征判别函数。它不仅能衡量特征的判别性，而且能衡量特征的多样性。我们从多个方面分析了这个函数的性质，发现它能更好地区分不同类别的图。基于这个函数，我们设计了新的特征选取算法，获得很高的分类精度。 / Graph has powerful ability to model complex structural relationships among data objects and has been widely used in various applications. Along with the development of the application domains, graph databases become large and are growing rapidly in size. This brings researchers new challenges on graph query and mining, among which we mainly focus on investigating the following three problems: how to find the correspondence between the nodes of two large graphs so that some substructures in one graph are mapped to similar substructures in the other; another problem is how to retrieve similar graphs for a query graph from a graph database consisting of a large number of graphs; and the last problem is how to extract subgraph features to build an automated classification model for a graph database containing graphs which belong to different classes. / In this thesis, for the first problem, we propose a novel two-step approach which can efficiently match two large graphs over thousands of nodes with high matching quality. In the first stage, we design an anchor-selection/expansion scheme to construct a good initial matching heuristically. In the second stage, we propose a new approach to refine the initial matching and give the optimality of our refinement algorithm. Our approach can produce an approximate matching result with high quality and efficiency. To address the second problem, we introduce a new graph distance measure based on the maximum common subgraphs (MCS) of two graphs which can thoroughly capture the common as well as different structures of two graphs. Since computing the MCS of two graphs is NP-complete, to answer the top-k graph similarity query efficiently, we propose a fast algorithm which can significantly reduce the number of MCS computations. This algorithm prunes the unqualified graphs based on three lower bounds in which the first two are derived based on the structures of two graphs and the third is obtained based on the triangle property of the distance measure. Three index schemes are designed with different tradeoffs between pruning power and construction cost to assist the query processing. For the third problem, we identify two main issues of the current widely-used discriminative score for feature selection, and introduce a new diversified discriminative score to explore the additional value of the diversity together with the discriminativity. We analyze the properties of the newly-proposed diversified discriminative score from several perspectives and demonstrate that this score can make positive/negative graphs more separable. New algorithms are also proposed to select features based on the new score and they are shown to have high classification accuracy. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Zhu, Yuanyuan. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 137-146). / Abstract also in Chinese. / Abstract --- p.i / Abstract in Chinese --- p.iii / Acknowledgments --- p.iv / Contents --- p.vi / List of Tables --- p.x / List of Figures --- p.xi / Notations --- p.1 / Chapter 1. --- Introduction --- p.1 / Chapter 1.1. --- Motivation --- p.2 / Chapter 1.1.1. --- Large Graph Matching --- p.3 / Chapter 1.1.2. --- Top-k Graph Similarity Query --- p.4 / Chapter 1.1.3. --- Diversified Discriminative Feature Selection --- p.6 / Chapter 1.2. --- Contribution --- p.7 / Chapter 2. --- Preliminaries --- p.10 / Chapter 3. --- Related Work --- p.16 / Chapter 3.1. --- Graph Matching --- p.16 / Chapter 3.1.1. --- Exact Graph Matching --- p.16 / Chapter 3.1.2. --- Approximate Graph Matching --- p.17 / Chapter 3.2. --- Graph Similarity Query --- p.19 / Chapter 3.3. --- Graph Classification --- p.20 / Chapter 4. --- Large Graph Matching --- p.23 / Chapter 4.1. --- Problem Statement --- p.23 / Chapter 4.2. --- An Overview: Construction and Refinement --- p.24 / Chapter 4.3. --- Matching Construction --- p.26 / Chapter 4.3.1. --- Global and Local Node Similarity --- p.26 / Chapter 4.3.2. --- Anchor Selection and Expansion --- p.33 / Chapter 4.3.3. --- Discussion on τ for Anchor Selection --- p.36 / Chapter 4.4. --- Matching Refinement --- p.39 / Chapter 4.4.1. --- Vertex Cover Based Refinement --- p.39 / Chapter 4.4.2. --- Refinement and Its Optimality --- p.41 / Chapter 4.4.3. --- Randomly Refinement Excluding C - F₁ --- p.46 / Chapter 4.4.4. --- Randomly Refinement Including C - F₁ --- p.51 / Chapter 4.5. --- Labeled Graph Handling --- p.54 / Chapter 4.6. --- Experiments --- p.56 / Chapter 4.6.1. --- Comparison with the Approximate Algorithms --- p.59 / Chapter 4.6.2. --- Comparison with the Exact Algorithm --- p.63 / Chapter 4.6.3. --- Parameter and Scalability Testing --- p.65 / Chapter 4.6.4. --- Sensitivity of Randomness (PN) --- p.69 / Chapter 4.6.5. --- Effectiveness of Label Distribution --- p.70 / Chapter 4.7. --- Summary --- p.72 / Chapter 5. --- Top-k Graph Similarity Query --- p.73 / Chapter 5.1. --- Problem Statement --- p.73 / Chapter 5.2. --- The Framework --- p.78 / Chapter 5.3. --- Pruning without Indexing --- p.80 / Chapter 5.3.1. --- Edge Frequency Based Lower Bound --- p.80 / Chapter 5.3.2. --- Adjacency List Based Lower Bound --- p.82 / Chapter 5.3.3. --- Query Processing --- p.84 / Chapter 5.4. --- Pruning with Indexing --- p.85 / Chapter 5.4.1. --- The Triangle Property of Graph Distance --- p.86 / Chapter 5.4.2. --- Query Processing --- p.88 / Chapter 5.4.3. --- Indexing --- p.92 / Chapter 5.4.4. --- Discussion on the Generality of Our Framework --- p.94 / Chapter 5.5. --- Experiments --- p.94 / Chapter 5.5.1. --- Similarity Measures Evaluation --- p.96 / Chapter 5.5.2. --- Query Performance Evaluation --- p.98 / Chapter 5.5.3. --- Indexing Cost Evaluation --- p.102 / Chapter 5.6. --- Summary --- p.103 / Chapter 6. --- Diversified Discriminative Feature Selection --- p.105 / Chapter 6.1. --- Problem Statement --- p.105 / Chapter 6.2. --- Discriminative Score --- p.108 / Chapter 6.2.1. --- The Single Feature Discriminative Score --- p.109 / Chapter 6.2.2. --- A New Diversified Discriminative Score --- p.110 / Chapter 6.3. --- Property Statistics of Discriminative Score --- p.113 / Chapter 6.4. --- The Algorithms --- p.117 / Chapter 6.5. --- Ensemble D&D --- p.121 / Chapter 6.6. --- Experiments --- p.123 / Chapter 6.6.1. --- D&D Performance Analysis --- p.126 / Chapter 6.6.2. --- Comparison with Existing Algorithms --- p.127 / Chapter 6.6.3. --- Performance on Patterns Mined by GAIA --- p.129 / Chapter 6.7. --- Summary --- p.131 / Chapter 7. --- Conclusion and FutureWork --- p.132 / Chapter 7.1. --- Conclusion --- p.132 / Chapter 7.2. --- Future work --- p.134 / Bibliography --- p.136

由于现今在各个领域涌现的图数据规模都愈加庞大，在这些大规模图数据上进行任何一种简单的查询都成为一件有富有挑战性的工作。在本文中，我们着重在大规模图上研究三个具有广泛应用的查询：最短路查询，权重限制查询和最近k关键字查询。具体来说， 最短路查询是一个计算两点间最短距离的基本查询。而权重限制查询判断两点间是否存在一条沿路边权都满足用指定条件的可行路径。对于一个查询节点，最近k关键字查询返回k个距离最近的带有指定关键字的节点。在面对一个拥有超过一亿节点的图时，我们需要为这些查询开发有效的索引和查询优化算法。 / 在本文中，对于最短路查询，我们提出了两个基于地标嵌入的算法，一个是有误差控制的地标嵌入算法，另一个则是本地化地标嵌入算法。前者通过对地标的筛选和组织，能对估计的最短距离给予一定的误差保证； 而后者提出的本地化机制能够在不增加预处理复杂度和在线查询复杂度的情况下大幅度提高估计的精准度。对于权重限制查询，我们先提出一个能够保证常数查询时间的内存算法。除此之外，为了提高算法对大规模数据的处理能力，我们使用编码技术设计了一个有效的外存算法。对于最近k关键字查询，我们先在一个特殊的图，即一颗树上，开发一个有效算法来在常数时间内回答最近k关键字查询， 并由此得出一个图上的近似算法；此外我们还通过一个全局存储的技术来进一步减少索引大小和缩短查询时间。我们在真实和模拟的数据上做了大量的实验，实验结果证明我们的算法在大图上对上述三个查询都具有高效性能。 / Due to the massive size of graphs from various domains nowadays, even simple graph queries become challenging tasks. In this thesis, three queries with a wide range of applications are investigated on large graphs. One is shortest distance query, a fundamental query which computes the shortest distance between two nodes. Another query, weight constraint reachability (WCR), checks if there is a feasible path between two nodes where edge weights along the path satisfy a side constraint. And the third one, a top-k nearest keywords (k-NK) query, reports, for a query node, the k nearest nodes bearing some user-specified keywords. When confronting with a large-scale graph with over tens of millions of nodes, we need to develop efficient indexing and query optimization techniques for these queries. / In this thesis, for a shortest distance query, we devise two landmark embedding schemes, an error bounded landmark scheme and a local landmark scheme, where the former can guarantee an error bound for estimated distance, and the latter can significantly improve the distance estimation accuracy without increasing the offline embedding or the online query complexity. For a WCR query, we propose a memorybased approach which promises a constant query time. Besides, in order to increase its scalability, we devise an I/O-efficient approach for answering a WCR query on massive graphs. For a k-NK query, we start with a special case when the graph is a tree, based on which we present our algorithm for approximate k-NK query on a graph. A global storage technique is devised to further reduce the index size and the query time. We did extensive experiments on the three queries respectively to show the effectiveness and efficiency of our methods. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Qiao, Miao. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 141-151). / Abstract also in Chinese. / Abstract --- p.i / Abstract in Chinese --- p.ii / Acknowledgements --- p.iii / Contents --- p.v / Chapter 1. --- Introduction --- p.1 / Chapter 1.1. --- Motivation --- p.1 / Chapter 1.1.1. --- Shortest Distance Query --- p.1 / Chapter 1.1.2. --- Weight Constraint Reachability Query --- p.4 / Chapter 1.1.3. --- Top-k Nearest Keyword Query --- p.7 / Chapter 1.2. --- Contributions --- p.9 / Chapter 1.3. --- Roadmap --- p.11 / Chapter 2. --- RelatedWork --- p.12 / Chapter 2.1. --- Shortest Distance Query --- p.12 / Chapter 2.2. --- Reachability Query --- p.14 / Chapter 2.3. --- Keyword Related Query --- p.15 / Chapter 3. --- Querying Shortest Distance --- p.17 / Chapter 3.1. --- Landmark Embedding --- p.17 / Chapter 3.2. --- Error Bounded Landmark Scheme --- p.18 / Chapter 3.2.1. --- Problem Statement --- p.18 / Chapter 3.2.2. --- Proposed Algorithm --- p.18 / Chapter 3.2.3. --- Graph Partitioning-based Heuristic --- p.22 / Chapter 3.2.4. --- Experiments --- p.27 / Chapter 3.3. --- Query-Dependent Local Landmark Scheme --- p.34 / Chapter 3.3.1. --- Problem Statement --- p.34 / Chapter 3.3.2. --- Shortest Path Tree Based Local Landmark --- p.37 / Chapter 3.3.3. --- Optimization Techniques --- p.41 / Chapter 3.3.4. --- Local Landmark Scheme on Relational Database --- p.48 / Chapter 3.3.5. --- Experiment --- p.56 / Chapter 3.4. --- Summary --- p.64 / Chapter 4. --- QueryingWeight Constraint Reachability --- p.65 / Chapter 4.1. --- Problem Definition --- p.65 / Chapter 4.1.1. --- Edge Weight Constraint --- p.65 / Chapter 4.1.2. --- Node Weight Constraint --- p.66 / Chapter 4.1.3. --- Two Basic Solutions --- p.67 / Chapter 4.2. --- An Efficient Memory Algorithm --- p.68 / Chapter 4.2.1. --- Properties of WCR --- p.68 / Chapter 4.2.2. --- Novel Edge Based Indexing --- p.70 / Chapter 4.2.3. --- Extension to Other Constraint Formats --- p.76 / Chapter 4.3. --- An I/O-Efficient Index --- p.77 / Chapter 4.3.1. --- Vertex Coding --- p.78 / Chapter 4.3.2. --- MST Re-balancing --- p.80 / Chapter 4.3.3. --- Disk-Based Index Construction --- p.84 / Chapter 4.3.4. --- Query Processing --- p.85 / Chapter 4.4. --- Experiments --- p.87 / Chapter 4.5. --- Summary --- p.101 / Chapter 5. --- Querying Top K-Nearest Keyword --- p.102 / Chapter 5.1. --- Problem Definition --- p.102 / Chapter 5.2. --- Existing Solutions --- p.103 / Chapter 5.2.1. --- Approximate k-NK on a Graph --- p.104 / Chapter 5.2.2. --- Exact 1-NK on a Tree --- p.106 / Chapter 5.3. --- Solution Overview --- p.108 / Chapter 5.4. --- K-NK on a Tree for a Small K --- p.110 / Chapter 5.4.1. --- Query Processing --- p.110 / Chapter 5.4.2. --- Construction of Entry Edge Partition --- p.115 / Chapter 5.4.3. --- Construction of Candidate List --- p.118 / Chapter 5.5. --- K-NK on a Tree for a Large K --- p.120 / Chapter 5.5.1. --- A Basic Pivot Approach --- p.121 / Chapter 5.5.2. --- Pivot Approach with Tree Balancing --- p.122 / Chapter 5.5.3. --- Index Construction --- p.125 / Chapter 5.6. --- Approximate K-NK on a Graph --- p.128 / Chapter 5.7. --- Experiments --- p.133 / Chapter 5.8. --- Summary --- p.138 / Chapter 6. --- Conclusions and Future Work --- p.139 / Bibliography --- p.140

Graph-structured data is enjoying an increasing popularity among Web technology and new data management and archiving techniques. Numerous applications work with graphs and need to query reachability among nodes in graphs. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O ( / Cheng, Jiefeng. / "August 2007." / Adviser: Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1097. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 134-141). / 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. / Abstract in English and Chinese. / School code: 1307.

In this dissertation, we develop frequent free tree mining systems, F3TM and CFFTree, to systematically discover the complete set of (closed) frequent free trees from a graph database. Graph indexing, another problem addressed in this dissertation, is of special interest both in academia and in industrial applications. The solutions, (Tree+Delta ) and SimTree, propose a free tree featured index, which is built on frequent free tree patterns discovered through a structural mining process. This mining-based indexing methodology leads to the development of a compact but effective graph index structure that is orders of magnitude smaller in size but an order of magnitude faster in performance than traditional approaches. / Scalable structural pattern mining and graph database management tools become increasingly crucial to applications with complex data in domains ranging from software engineering to computational biology. Due to their high complexity, it is often difficult, if not impossible, for human beings to manually analyze any reasonably large collection of graphs. In this dissertation, we investigate two fundamental problems in large scale graph databases: Given a graph database what are the hidden free tree patterns and how can we find them? And how can we index graphs based on free tree patterns and perform similarity search in large graph databases? / The developed concepts, theories, and systems hence increase our understanding of data mining principles in structural pattern discovery, interpretation and search. The formulation of a general free tree featured graph information system through this study could provide fundamental supports to graph-intensive applications. / Zhao, Peixiang. / "August 2007." / Adviser: Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1127. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 136-145). / 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. / Abstract in English and Chinese. / School code: 1307.