Thesis (M. Phil.)--University of Hong Kong, 1999. / Includes bibliographical references (leaves 75-81).

Thesis (M. Phil.)--University of Hong Kong, 1999. / Includes bibliographical references (leaves 55-59).

Thesis (Ph. D.)--University of Hong Kong, 2010. / Includes bibliographical references (leaves 108-115). Also available in print.

Thesis (M. Phil.)--City University of Hong Kong, 2005. / "Submitted to Department of Computer Engineering and Information Technology in partial fulfillment of the requirements for the degree of Master of Philosophy." Includes bibliographical references (leaves 54-58).

The study of cycles in the context of economic time series has been active for many decades, if not centuries; however, it was only in recent decades that more formal approaches for identifying cycles have been developed. Litvine and Bismans (2015) proposed a new approach for dating cycles in financial time series, for purposes of optimising buysell strategies. In this approach, cycle dating is presented as an optimisation problem. They also introduced a method for optimising this problem, known as the hierarchical method (using full evaluation 2, or HR-FE2). However, this method may be impractical for large data sets as it may require unacceptably long computation time. In this study, new procedures that date cycles using the approach proposed by Litvine and Bismans (2015), were introduced, and were speciffically developed to be feasible for large time series data sets. These procedures are the stochastic generation and adaptation (SGA), buy-sell adapted Extrema importance identity sequence retrieval (BSA-EIISR) and buysell adapted bottom-up (BSA-BU) methods. An existing optimisation technique, known as particle swarm optimisation (PSO), was also employed. A statistical comparison was then made between these methods, including HR-FE2. This involved evaluating, on simulated data, the performance of the algorithms in terms of objective function value and computation time on different time series lengths, Hurst exponent, and number of buy-sell points. The SRace methodology (T. Zhang, Georgiopoulos, and Anagnostopoulos 2013) was then applied to these results in order to determine the most effcient methods. It was determined that, statistically, SGA, BSA-EIISR and BSA-BU are the most effcient methods. Number of buysell points was found to have the largest effect on relative performance of these methods. In some cases, the Hurst exponent also has a small effect on relative performance.

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

In this thesis, we make several significant achievements towards defining a medial axis based shape descriptor which is compact, yet discriminative. First, we propose a novel medial axis spectral shape descriptor called the medial axis spectrum for a 2D shape, which applies spectral analysis directly to the medial axis of a 2D shape. We extend the Laplace-Beltrami operator onto the medial axis of a 2D shape, and take the solution to an extended Laplacian eigenvalue problem defined on this axis as the medial axis spectrum. The medial axis spectrum of a 2D shape is certainly more efficient to compute than spectral analysis of a 2D region, since the efficiency of solving the Laplace eigenvalue problem strongly depends on the domain dimension. We show that the medial axis spectrum is invariant under uniform scaling and isometry of the medial axis. It could also overcome the medial axis noise problem automatically, due to the incorporation of the hyperbolic distance metric. We also demonstrate that the medial axis spectrum inherits several advantages in terms of discriminating power over existing methods. Second, we further generalize the medial axis spectrum to the description of medial axes of 3D shapes, which we call the medial axis spectrum for a 3D shape. We develop a newly defined Minkowski-Euclidean area ratio inspired by the Minkowski inner product to characterize the geometry of the medial axis surface of a 3D mesh. We then generalize the Laplace-Beltrami operator to the medial axis surface, and take the solution to an extended Laplacian eigenvalue problem defined on the surface as the medial axis spectrum. As the 2D case, the medial axis spectrum of a 3D shape is invariant under rigid transformation and isometry of the medial axis, and is robust to shape boundary noise as shown by our experiments. The medial axis spectrum is finally used for 3D shape retrieval, and its superiority over previous work is shown by extensive comparisons. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

by Lau Siu Chung. / "April 2000." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (p. 97-102). / 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. / Abstracts in English and Chinese.

For a weighted graph with n vertices and m edges, the Minimum k-Way Cut problem is to find a partition of the vertices into k sets that minimizes the total weight of edges crossing the sets. We obtain several important structural properties of minimum multiway cuts and use them to design efficient algorithms for several multiway partition problems. We design the first algorithm for finding minimum 3-way cuts in hypergraphs, which runs in O(dmn 3) time, where d is the sum of the degrees of all the vertices. We also give an O(n 4k--lg k) algorithm for finding all minimum k-way cuts in graphs. Our algorithm is based on a divide-and-conquer method and improves all well-known existing algorithms along this divide-and-conquer method. As for approximation algorithms, we determine the tight approximation ratio of a general greedy splitting algorithm (finding a minimum k-way cut by iteratively increasing a constant number of components). Our result implies that the approximation ratio of the algorithm that iteratively increases h -- 1 components is 2 -- h/k + O(h2 /k2), which settles a well-known open problem. / For an unweighted graph and a given subset T ⊂ V of k terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of l edges (respectively, non-terminal vertices), whose removal from G separates each terminal from all the others. We show that Edge Multiterminal Cut is polynomial-time solvable for 1 = O(log n) by presenting an O(2lkT(n, m)) algorithm, where T(n, m) is the running time of finding a maximum flow in unweighted graphs. We also give three algorithms for Vertex Multiterminal Cut that run in O(k lT(n, m)), O( l!2 2l T(n, m)) and O(lk 4lT( n, m)) time respectively. Furthermore, we obtain faster algorithms for small k: Edge 3-Terminal Cut can be solved in O(1.415lT(n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059 lT(n, m)), O(2.772 lT(n, m)), O(3.349 lT(n, m)) and O(3.857 lT(n, m)) times respectively. Our results on Multiterminal Cut can be used to obtain faster algorithms for Multicut. / In this thesis, we study algorithmic issues for three closely related partition problems in graphs: k-Way Cut (k-Cut), Multiterminal Cut, and Multicut. These three problems attempt to separate a graph, by edge or vertex deletion, into several components with certain properties. The k-Way Cut (k-Cut) problem is to separate the graph into k components, the Multiterminal Cut problem is to separate a subset of vertices away from each other, and the Multicut problem is to separate some given pairs of vertices. These three problems have many applications in parallel and distributed computing, VLSI system design, clustering problems, communications network and many others. / Xiao, Mingyu. / Adviser: Andrew C. Yao. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3617. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 85-92). / 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 Kwong, Wang-Wai Renfrew. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (leaves 102-105). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgments --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Data Mining Tasks --- p.1 / Chapter 1.1.1 --- Characterization --- p.2 / Chapter 1.1.2 --- Discrimination --- p.2 / Chapter 1.1.3 --- Classification --- p.2 / Chapter 1.1.4 --- Clustering --- p.3 / Chapter 1.1.5 --- Prediction --- p.3 / Chapter 1.1.6 --- Description --- p.3 / Chapter 1.1.7 --- Association Rule Mining --- p.4 / Chapter 1.2 --- Motivation --- p.4 / Chapter 1.2.1 --- Motivation for Mining Multi-level Association Rules Using Data Cubes --- p.4 / Chapter 1.2.2 --- Motivation for Mining N-most Interesting Itemsets --- p.8 / Chapter 1.3 --- Outline of the Thesis --- p.10 / Chapter 2 --- Survey on Previous Work --- p.11 / Chapter 2.1 --- Data Warehousing --- p.11 / Chapter 2.1.1 --- Data Cube --- p.12 / Chapter 2.2 --- Data Mining --- p.13 / Chapter 2.2.1 --- Association Rules --- p.14 / Chapter 2.2.2 --- Multi-level Association Rules --- p.15 / Chapter 2.2.3 --- Multi-Dimensional Association Rules Using Data Cubes --- p.16 / Chapter 2.2.4 --- Apriori Algorithm --- p.19 / Chapter 3 --- Mining Multi-level Association Rules Using Data Cubes --- p.22 / Chapter 3.1 --- Use of Multi-level Concept --- p.22 / Chapter 3.1.1 --- Multi-level Concept --- p.22 / Chapter 3.1.2 --- Criteria of Using Multi-level Concept --- p.23 / Chapter 3.1.3 --- Use of Multi-level Concept in Association Rules --- p.24 / Chapter 3.2 --- Use of Data Cube --- p.25 / Chapter 3.2.1 --- Data Cube --- p.25 / Chapter 3.2.2 --- Mining Multi-level Association Rules Using Data Cubes --- p.26 / Chapter 3.2.3 --- Definition --- p.28 / Chapter 3.3 --- Method for Mining Multi-level Association Rules Using Data Cubes --- p.31 / Chapter 3.3.1 --- Algorithm --- p.33 / Chapter 3.3.2 --- Example --- p.35 / Chapter 3.4 --- Experiment --- p.44 / Chapter 3.4.1 --- Simulation of Data Cube by Array --- p.44 / Chapter 3.4.2 --- Simulation of Data Cube by B+ Tree --- p.48 / Chapter 3.5 --- Discussion --- p.54 / Chapter 4 --- Mining the N-most Interesting Itemsets --- p.56 / Chapter 4.1 --- Mining the N-most Interesting Itemsets --- p.56 / Chapter 4.1.1 --- Criteria of Mining the N-most Interesting itemsets --- p.56 / Chapter 4.1.2 --- Definition --- p.58 / Chapter 4.1.3 --- Property --- p.59 / Chapter 4.2 --- Method for Mining N-most Interesting Itemsets --- p.60 / Chapter 4.2.1 --- Algorithm --- p.60 / Chapter 4.2.2 --- Example --- p.76 / Chapter 4.3 --- Experiment --- p.81 / Chapter 4.3.1 --- Synthetic Data --- p.81 / Chapter 4.3.2 --- Real Data --- p.85 / Chapter 4.4 --- Discussion --- p.98 / Chapter 5 --- Conclusion --- p.100 / Bibliography --- p.101 / Appendix --- p.106 / Chapter A --- Programs for Mining the N-most Interesting Itemset --- p.106 / Chapter A.1 --- Programs --- p.106 / Chapter A.2 --- Data Structures --- p.108 / Chapter A.3 --- Global Variables --- p.109 / Chapter A.4 --- Functions --- p.110 / Chapter A.5 --- Result Format --- p.113 / Chapter B --- Programs for Mining the Multi-level Association Rules Using Data Cube --- p.114 / Chapter B.1 --- Programs --- p.114 / Chapter B.2 --- Data Structure --- p.118 / Chapter B.3 --- Variables --- p.118 / Chapter B.4 --- Functions --- p.119