Law Chi Hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 86-91). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Contents --- p.v / List of Figures --- p.viii / List of Tables --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.4 / Chapter 1.2 --- Thesis Organization --- p.7 / Chapter 2 --- Literature Review --- p.9 / Chapter 2.1 --- Logical Time --- p.9 / Chapter 2.1.1 --- Event Model --- p.9 / Chapter 2.1.2 --- Lamport's Logical Clock --- p.10 / Chapter 2.1.3 --- Mattern's Vector Time --- p.14 / Chapter 2.2 --- Snapshot Algorithms --- p.18 / Chapter 2.2.1 --- Preliminaries --- p.19 / Chapter 2.2.2 --- Chandy-Lamport --- p.22 / Chapter 2.2.3 --- Lai-Yang and Mattern --- p.24 / Chapter 2.2.4 --- Sato --- p.25 / Chapter 3 --- Ad-hoc Network System --- p.29 / Chapter 3.1 --- Event Model --- p.30 / Chapter 3.2 --- Snapshot Problem --- p.32 / Chapter 4 --- Time Approximation in Distributed Systems --- p.37 / Chapter 4.1 --- Definitions --- p.38 / Chapter 4.1.1 --- Preliminary --- p.38 / Chapter 4.1.2 --- Event Ordering --- p.39 / Chapter 4.1.3 --- Clock --- p.40 / Chapter 4.1.4 --- Time Approximation Levels --- p.41 / Chapter 4.1.5 --- Offline Algorithm --- p.41 / Chapter 4.2 --- Time Approximation in Static Network Systems --- p.42 / Chapter 4.2.1 --- Stable Snapshot --- p.43 / Chapter 4.2.2 --- Snapshot --- p.50 / Chapter 4.2.3 --- Latest Snapshot --- p.52 / Chapter 4.2.4 --- Time Approximation Levels --- p.54 / Chapter 4.3 --- Time Approximation in Ad-hoc Network Systems --- p.54 / Chapter 4.3.1 --- Snapshot --- p.56 / Chapter 4.3.2 --- Latest Snapshot --- p.61 / Chapter 4.3.3 --- Time Approximation Levels --- p.61 / Chapter 4.3.4 --- Bi-vector Clock --- p.63 / Chapter 4.3.5 --- Strong Snapshot Problem --- p.67 / Chapter 5 --- Snapshot Algorithm for Ad-hoc Network Systems --- p.69 / Chapter 5.1 --- Algorithm --- p.70 / Chapter 5.1.1 --- Notations --- p.70 / Chapter 5.1.2 --- Rules of Maintaining Si and Ti in Pi --- p.72 / Chapter 5.1.3 --- The Properties --- p.73 / Chapter 5.1.4 --- Algorithm --- p.78 / Chapter 5.2 --- Enhancements --- p.82 / Chapter 5.2.1 --- Reduction of Stored States and Exchanged Logs --- p.82 / Chapter 5.2.2 --- LCC Synchronization --- p.82 / Chapter 6 --- Conclusion --- p.84 / Bibliography --- p.86 / Publications --- p.91

Wu Yuen-Ting. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 88-90). / Abstracts in English and Chinese. / Chapter 1. --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Research Objective --- p.4 / Chapter 1.3 --- Contribution --- p.5 / Chapter 1.4 --- Structure of this thesis --- p.6 / Chapter 2. --- Literature Review --- p.7 / Chapter 2.1 --- Genetic Algorithms --- p.7 / Chapter 2.1.1 --- Pre-processing step --- p.8 / Chapter 2.1.2 --- Generation of initial population --- p.10 / Chapter 2.1.3 --- Crossover --- p.11 / Chapter 2.1.4 --- Mutation --- p.12 / Chapter 2.1.5 --- Selection --- p.12 / Chapter 2.1.6 --- Results of GA on Container Loading Algorithm --- p.13 / Chapter 2.2 --- Layering Approach --- p.13 / Chapter 2.3 --- Mixed Integer Programming --- p.14 / Chapter 2.4 --- Tabu Search Algorithm --- p.15 / Chapter 2.5 --- Other approaches --- p.16 / Chapter 2.5.1 --- Block arrangement --- p.17 / Chapter 2.5.2 --- Multi-Directional Building Growing algorithm --- p.17 / Chapter 2.6 --- Comparisons of different container loading algorithms --- p.18 / Chapter 3. --- Principle of LFF Algorithm --- p.8 / Chapter 3.1 --- Definition of Flexibility --- p.8 / Chapter 3.2 --- The Less Flexibility First Principle (LFFP) --- p.23 / Chapter 3.3 --- The 2D LFF Algorithm --- p.25 / Chapter 3.3.1 --- Generation of Corner-Occupying Packing Move (COPM) --- p.26 / Chapter 3.3.2 --- Pseudo-packing and the Greedy Approach --- p.27 / Chapter 3.3.3 --- Real-packing --- p.30 / Chapter 3.4 --- Achievement of 2D LFF --- p.31 / Chapter 4. --- Error Bound Analysis on 2D LFF --- p.21 / Chapter 4.1 --- Definition of Error Bound --- p.21 / Chapter 4.2 --- Cause and Analysis on Unsatisfactory Results by LFF --- p.33 / Chapter 4.3 --- Formal Proof on Error Bound --- p.39 / Chapter 5. --- LFF for Container Loading Problem --- p.33 / Chapter 5.1 --- Problem Formulation and Term Definitions --- p.48 / Chapter 5.2 --- Possible Problems to be solved --- p.53 / Chapter 5.3 --- Implementation in Container Loading --- p.54 / Chapter 5.3.1 --- The Basic Algorithm --- p.56 / Chapter 5.4 --- A Sample Packing Scenario --- p.62 / Chapter 5.4.1 --- Generation of COPM list --- p.63 / Chapter 5.4.2 --- Pseudo-packing and the greedy approach --- p.66 / Chapter 5.4.3 --- Update of corner list --- p.69 / Chapter 5.4.4 --- Real-Packing --- p.70 / Chapter 5.5 --- Ratio Approach: A Modification to LFF --- p.70 / Chapter 5.6 --- LFF with Tightness Measure: CPU time Cut-down --- p.75 / Chapter 5.7 --- Experimental Results --- p.77 / Chapter 5.7.1 --- Comparison between LFF and LFFR --- p.77 / Chapter 5.7.2 --- "Comparison between LFFR, LFFT and other algorithms" --- p.78 / Chapter 5.7.3 --- Computational Time for different algorithms --- p.81 / Chapter 5.7.4 --- Conclusion of the experimental results --- p.83 / Chapter 6. --- Conclusion --- p.85 / Bibiography --- p.88

Cheng Tung Yin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 136-141). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.1.1 --- Information Retrieval --- p.1 / Chapter 1.1.2 --- Search Engines --- p.2 / Chapter 1.1.3 --- Data Merging --- p.3 / Chapter 1.2 --- Meta-search Engines --- p.3 / Chapter 1.2.1 --- Framework and Techniques Employed --- p.3 / Chapter 1.2.2 --- Advantages of meta-searching --- p.8 / Chapter 1.3 --- Contribution of the Thesis --- p.10 / Chapter 1.4 --- Organization of the Thesis --- p.12 / Chapter 2 --- Literature Review --- p.14 / Chapter 2.1 --- Preliminaries --- p.14 / Chapter 2.2 --- Fusion Methods --- p.15 / Chapter 2.2.1 --- Fusion methods based on a document's score --- p.15 / Chapter 2.2.2 --- Fusion methods based on a document's ranking position --- p.23 / Chapter 2.2.3 --- Fusion methods based on a document's URL title and snippets --- p.30 / Chapter 2.2.4 --- Fusion methods based on a document's entire content --- p.40 / Chapter 2.3 --- Comparison of the Fusion Methods --- p.42 / Chapter 2.4 --- Relevance Feedback --- p.46 / Chapter 3 --- Research Methodology --- p.48 / Chapter 3.1 --- Investigation of the features of the retrieved results from the search engines --- p.48 / Chapter 3.2 --- Types of relationships --- p.53 / Chapter 3.3 --- Order of Strength of the Relationships --- p.64 / Chapter 3.3.1 --- Derivation of the weight for each kind of relationship (criterion) --- p.68 / Chapter 3.4 --- Observation of the relationships between retrieved objects and the effects of these relationships on the relevance of objects --- p.69 / Chapter 3.4.1 --- Observation on the relationships existed in items that are irrelevant and relevant to the query --- p.68 / Chapter 3.5 --- Proposed re-ranking algorithms --- p.89 / Chapter 3.5.1 --- Original re-ranking algorithm (before modification) --- p.91 / Chapter 3.5.2 --- Modified re-ranking algorithm (after modification) --- p.95 / Chapter 4 --- Evaluation Methodology and Experimental Results --- p.101 / Chapter 4.1 --- Objective --- p.101 / Chapter 4.2 --- Experimental Design and Setup --- p.101 / Chapter 4.2.1 --- Preparation of data --- p.101 / Chapter 4.3 --- Evaluation Methodology --- p.104 / Chapter 4.3.1 --- Evaluation of the relevance of a document to the corresponding query --- p.104 / Chapter 4.3.2 --- Performance Measures of the Evaluation --- p.105 / Chapter 4.4 --- Experimental Results and Interpretation --- p.106 / Chapter 4.4.1 --- Precision --- p.107 / Chapter 4.4.2 --- Recall --- p.107 / Chapter 4.4.3 --- F-measure --- p.108 / Chapter 4.4.4 --- Overall evaluation results for the ten queries for each evaluation tool --- p.110 / Chapter 4.4.5 --- Discussion --- p.123 / Chapter 4.5 --- Degree of difference between the performance of systems --- p.124 / Chapter 4.5.1 --- Analysis using One-Way ANOVA --- p.124 / Chapter 4.5.2 --- Analysis using paired samples T-test --- p.126 / Chapter 5 --- Conclusion --- p.131 / Chapter 5.1 --- "Implications, Limitations, and Future Work" --- p.131 / Chapter 5.2 --- Conclusions --- p.133 / Bibliography --- p.134 / Chapter A --- Paired samples T-test for F-measures of systems retrieving all media's items --- p.140

在此論文中，我們為一系列應用與數據庫系統的問題設計有理論保證的數據結構與/或算法。這些問題可以分為兩類。第一類是一些計算機科學中的經典問題：近似最近鄰居(approximatenearest neighbor)問題、近似最近點對(approximate closest pair )問題、skyline問題(亦稱maxima問題)和二維正交區域聚合(2d orthogonalrange aggregation)問題。第二類則是在此論文中提出的新問題：歷史分位數(historical quantile)問題、k-跳步最短路徑(k-skipshortest path)問題、XML文檔中的最近關鍵字(nearest keyword)問題、最連通節點(most connected vertex )問題和先入先出索引(FIFOindexing)問題。對於每一個問題，或者我們給出最壞情況亦高效的(worst-case efficient)解決方案；或者當最壞情況性能的意義不大時，我們證明方法的實例最優性(instance optimality)。 / In this thesis, we propose data structures and/or algorithms with theoretical guarantees for solving a series of problems that find applications in database systems. These problems can be classified into two categories. The first one contains several classic problems in computer science, including the approximate nearest neighbor problem, the approximate closest pair problem, the skyline problem (a.k.a. the maxima problem), and 2d orthogonal range search. The second category, on the other hand, consists of problems that are newly introduced by this thesis: the historical quantile problem, the k-skip shortest path problem, the nearest keyword problem on XML documents, the most connected vertex problem, and the FIFO indexing problem. For each problem, we establish either the worstcase efficiency of our solutions, or their instance optimality when worst-case performance is not interesting. / Detailed summary in vernacular field only. / Sheng, Cheng. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 277-298). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Computation models --- p.1 / Chapter 1.2 --- Thesis contributions and organization --- p.2 / Chapter 2 --- Nearest Neighbors and Closest Pairs --- p.7 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Problem settings --- p.10 / Chapter 2.3 --- The preliminaries --- p.11 / Chapter 2.3.1 --- Rigorous-LSH and ball cover --- p.12 / Chapter 2.3.2 --- Adhoc-LSH --- p.13 / Chapter 2.3.3 --- Details of hash functions --- p.15 / Chapter 2.4 --- LSB-tree --- p.16 / Chapter 2.4.1 --- Building a LSB-tree --- p.16 / Chapter 2.4.2 --- Nearest neighbor algorithm --- p.18 / Chapter 2.5 --- Theoretical analysis --- p.21 / Chapter 2.5.1 --- Quality guarantee --- p.21 / Chapter 2.5.2 --- Space and query time --- p.25 / Chapter 2.5.3 --- Comparison with rigorous-LSH --- p.25 / Chapter 2.6 --- Extensions --- p.26 / Chapter 2.7 --- Closest pair search --- p.30 / Chapter 2.7.1 --- Ball pair search --- p.30 / Chapter 2.7.2 --- Solving the closest pair problem --- p.34 / Chapter 2.8 --- Related work --- p.38 / Chapter 2.9 --- Experiments --- p.41 / Chapter 2.9.1 --- Data and queries --- p.41 / Chapter 2.9.2 --- Competitors for nearest neighbor search --- p.42 / Chapter 2.9.3 --- Competitors for closest pair search --- p.43 / Chapter 2.9.4 --- Computing environments and assessment metrics --- p.44 / Chapter 2.9.5 --- Behavior of LSH implementations --- p.45 / Chapter 2.9.6 --- Comparison of NN solutions --- p.48 / Chapter 2.9.7 --- Comparison of CP solutions --- p.51 / Chapter 2.10 --- Chapter summary --- p.54 / Chapter 3 --- The Skyline Problem and Its Variants --- p.57 / Chapter 3.1 --- Introduction --- p.57 / Chapter 3.1.1 --- Previous results --- p.58 / Chapter 3.1.2 --- Our results --- p.60 / Chapter 3.2 --- Preliminaries --- p.63 / Chapter 3.3 --- Our skyline algorithm --- p.66 / Chapter 3.3.1 --- 3d --- p.67 / Chapter 3.3.2 --- 4d --- p.69 / Chapter 3.3.3 --- Higher dimensionalities --- p.70 / Chapter 3.3.4 --- Eliminating the general-position assumption --- p.74 / Chapter 3.4 --- Variants of the skyline problem --- p.74 / Chapter 3.5 --- Low-cardinality domains --- p.77 / Chapter 3.6 --- Non-fixed dimensionality --- p.80 / Chapter 3.6.1 --- An improved algorithm in internal memory --- p.80 / Chapter 3.6.2 --- Externalizing the algorithm --- p.82 / Chapter 3.7 --- Chapter summary --- p.83 / Chapter 4 --- Orthogonal Range Aggregation --- p.85 / Chapter 4.1 --- Introduction --- p.85 / Chapter 4.1.1 --- Applications --- p.86 / Chapter 4.1.2 --- Computation model --- p.87 / Chapter 4.1.3 --- Previous results --- p.87 / Chapter 4.1.4 --- Our results --- p.88 / Chapter 4.2 --- Preliminaries --- p.91 / Chapter 4.3 --- Bundled compressed B-tree --- p.93 / Chapter 4.4 --- Three-sided window-max --- p.95 / Chapter 4.4.1 --- The first structure --- p.96 / Chapter 4.4.2 --- The improved structure --- p.97 / Chapter 4.5 --- Segment-intersection-max --- p.101 / Chapter 4.6 --- Stabbing-max --- p.103 / Chapter 4.6.1 --- Ray-segment-max --- p.103 / Chapter 4.6.2 --- Stabbing-max --- p.106 / Chapter 4.7 --- Rectangle-intersection-sum --- p.106 / Chapter 5 --- Persistent Quantiles --- p.109 / Chapter 5.1 --- Introduction --- p.109 / Chapter 5.1.1 --- Problem definition --- p.111 / Chapter 5.1.2 --- Previous work --- p.112 / Chapter 5.1.3 --- Our main results --- p.113 / Chapter 5.2 --- Space lower bounds for historical quantile search --- p.114 / Chapter 5.3 --- A structure for historical quantile search --- p.119 / Chapter 5.3.1 --- Persistence technique --- p.119 / Chapter 5.3.2 --- High-level rationales and challenges --- p.121 / Chapter 5.3.3 --- The structure and its query algorithm --- p.122 / Chapter 5.3.4 --- Construction algorithm --- p.127 / Chapter 5.3.5 --- Complexity analysis --- p.130 / Chapter 5.3.6 --- An alternative simple solution --- p.132 / Chapter 5.4 --- Experiments --- p.133 / Chapter 5.4.1 --- Competitors and metrics --- p.133 / Chapter 5.4.2 --- Performance characteristics --- p.133 / Chapter 5.4.3 --- Performance on real data --- p.136 / Chapter 5.5 --- Chapter summary --- p.138 / Chapter 6 --- k-Skip Shortest Paths --- p.141 / Chapter 6.1 --- Introduction --- p.141 / Chapter 6.2 --- Related work --- p.144 / Chapter 6.2.1 --- Dijkstra and reach --- p.144 / Chapter 6.2.2 --- More results on SP computation --- p.148 / Chapter 6.3 --- k-skip Shortest Paths --- p.150 / Chapter 6.4 --- k-skip graph --- p.152 / Chapter 6.4.1 --- Size of k-skip cover --- p.152 / Chapter 6.4.2 --- Computing a k-skip cover --- p.154 / Chapter 6.4.3 --- Computing a k-skip graph --- p.156 / Chapter 6.5 --- Query algorithm --- p.158 / Chapter 6.5.1 --- High-level description --- p.158 / Chapter 6.5.2 --- Reach* --- p.160 / Chapter 6.5.3 --- Zoom-in --- p.163 / Chapter 6.6 --- Experiments --- p.164 / Chapter 6.7 --- Chapter summary --- p.168 / Chapter 7 --- Nearest Keyword Queries on XML Documents --- p.171 / Chapter 7.1 --- Introduction --- p.171 / Chapter 7.1.1 --- Motivation --- p.171 / Chapter 7.1.2 --- Contributions --- p.174 / Chapter 7.2 --- Preliminaries --- p.175 / Chapter 7.3 --- Nearest keyword search --- p.178 / Chapter 7.3.1 --- Overview --- p.178 / Chapter 7.3.2 --- TVP characteristics --- p.180 / Chapter 7.3.3 --- Finding the minimum TVP --- p.183 / Chapter 7.4 --- Nearest keyword search as an operator --- p.186 / Chapter 7.4.1 --- XPath evaluation --- p.186 / Chapter 7.4.2 --- Finding approximate group steiner trees --- p.192 / Chapter 7.5 --- Related work --- p.193 / Chapter 7.6 --- Experiments --- p.196 / Chapter 7.7 --- Chapter summary --- p.202 / Chapter 8 --- FIFO Indexes for Decomposable Problems --- p.203 / Chapter 8.1 --- Introduction --- p.203 / Chapter 8.1.1 --- FIFO update scheme and its applications --- p.203 / Chapter 8.1.2 --- Technical motivations --- p.204 / Chapter 8.1.3 --- Problems, computation models, and basic notations --- p.205 / Chapter 8.1.4 --- Previous results --- p.207 / Chapter 8.1.5 --- Our results --- p.210 / Chapter 8.2 --- Making a static structure FIFO --- p.213 / Chapter 8.2.1 --- The RAM model --- p.214 / Chapter 8.2.2 --- The EM model --- p.220 / Chapter 8.3 --- Solving concrete problems --- p.221 / Chapter 8.4 --- Chapter summary --- p.225 / Chapter 9 --- The Most Connected Vertex Problem --- p.227 / Chapter 9.1 --- Introduction --- p.227 / Chapter 9.1.1 --- Motivation --- p.227 / Chapter 9.1.2 --- Our main results --- p.230 / Chapter 9.2 --- Problem and Related Work --- p.232 / Chapter 9.3 --- Preliminaries --- p.235 / Chapter 9.4 --- Exact algorithms --- p.239 / Chapter 9.5 --- Theoretical analysis of the exact algorithms --- p.244 / Chapter 9.5.1 --- The randomized algorithm class --- p.244 / Chapter 9.5.2 --- The deterministic algorithm class --- p.251 / Chapter 9.6 --- Approximate algorithms and their analysis --- p.254 / Chapter 9.6.1 --- 1-MCV --- p.254 / Chapter 9.6.2 --- k-MCV --- p.259 / Chapter 9.7 --- Experiments --- p.262 / Chapter 9.7.1 --- Datasets --- p.262 / Chapter 9.7.2 --- Methods --- p.264 / Chapter 9.7.3 --- How pessimistic is the worst case? --- p.265 / Chapter 9.7.4 --- Performance of random-probe algorithms --- p.266 / Chapter 9.7.5 --- Performance of deterministic-probe algorithms --- p.268 / Chapter 9.7.6 --- Performance of AMCV --- p.269 / Chapter 9.8 --- Chapter summary --- p.274 / Bibliography --- p.277

Based on the fixed block size FWS algorithm, we further proposed a fast full-pel variable block size motion estimation algorithm called Fast Walsh Search in Variable Block Size (FWS-VBS). As in FWS, FWS-VBS employs the PSAD as the error measure to identify likely mismatches. Mismatches are rejected by thresholding method and the thresholds are determined adaptively to cater for different activity levels in each block. Early termination techniques are employed to further reduce the number of candidates and modes to be searched of each block. FWS-VBS performs equally well to the exhaustive full search algorithm in the reference H.264/AVC encoder and requires only about 10% of the computation time. / Furthermore, we modified our proposed segmentation algorithm to handle video sequences that are already encoded in the H.264 format. Since the video is compressed, no spatial information is available. Instead, quantized transform coefficients of the residual frame are used to approximate spatial information and improve segmentation result. The computation time of the segmentation process is merely about 16ms per frame for CIF frame size video, allowing the algorithm to be applied in real-time applications such as video surveillance and conferencing. / In the first part of our research, we proposed a block matching algorithm called Fast Walsh Search (FWS) for video motion estimation. FWS employs two new error measures defined in Walsh Hadamard domain, which are partial sum-of-absolute difference (PSAD) and sum-of-absolute difference of DC coefficients (SADDCC). The algorithm first rejects most mismatched candidates using PSAD which is a coarse measure requiring little computation. Because of the energy packing ability of Walsh Hadamard transform (WHT) and the utilization of fast WHT computation algorithm, mismatched candidates are identified and rejected efficiently. Then the proposed algorithm identifies the matched candidate from the remaining candidates using SADDCC which is a more accurate measure and can reuse computation performed for PSAD. Experimental results show that FWS can give good visual quality to most of video scene with a reasonable amount of computation. / In the second part of our research, we developed a real-time video object segmentation algorithm. The motion information is obtained by FWS-VBS to minimize the computation time while maintaining an adequate accuracy. The algorithm makes use of the motion information to identify background motion model and moving objects. In order to preserve spatial and temporal continuity of objects, Markov random field (MRF) is used to model the foreground field. The block-based foreground object mask is obtained by minimizing the energy function of the MRF. The resulting object mask is then post-processed to generate a smooth object mask. Experimental results show that the proposed algorithm can effectively extract moving objects from different kind of sequences, at a speed of less than 100ms per frame for CIF frame size video. / Motion estimation is an important part in many video processing applications, such as video compression, object segmentation, and scene analysis. In all video compression applications, motion information is used to reduce temporal redundancy between frames, thus significantly reduce the required bitrate for transmission and storage of compressed video. In addition, in object-based video coding, video object can be automatically identified by its motion against the background. / Mak, Chun Man. / "June 2008." / Adviser: Wai-Kuen Cham. / Source: Dissertation Abstracts International, Volume: 70-03, Section: B, page: 1849. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references. / 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.

Another important contribution of this thesis is that we propose another novel and highly robust estimator: Kernel Density Estimation Sample Consensus (KDESAC) which employs Random Sample Consensus algorithm combined with Kernel Density Estimation (KDE). The main advantage of KDESAC is that no prior information and no scale estimators are required in the estimation of the parameters. The computational load of KDESAC is much lower than the robust algorithms which estimate the scale in every sample loop. The experiments on synthetic data show that the proposed method is more robust to the heavily corrupted data than other algorithms. KDESAC can tolerate more than 80% outliers and multiple structures. Although Adaptive Scale Sample Consensus (ASSC) can obtain such good performance as KDESAC, ASSC is much slower than KDESAC. KDESAC is also applied to SFM problem and multi-motion estimation with real data. The experiments demonstrate that KDESAC is robust and efficient. / Structure from motion (SFM), the problem of estimating 3D structure from 2D images hereof, is one of the most popular and well studied problems within computer vision. This thesis is a study within the area of SFM. The main objective of this work is to improve the robustness of the SFM algorithm so as to make it capable of tolerating a great number of outliers in the correspondences. For improving the robustness, a stereo image sequence is processed, so the random sampling algorithms can be employed in the structure and motion estimation. With this strategy, we employ Random Sample Consensus (RANSAC) in motion and structure estimation to exclude outliers. Since the RANSAC method needs the prior information about the scale of the inliers, we proposed an auto-scale RANSAC algorithm which determines the inliers by analyzing the probability density of the residuals. The experimental results demonstrate that SFM by the proposed auto-scale RANSAC is more robust and accurate than that by RANSAC. / Chan Tai. / "September 2006." / Adviser: Yun Hui Liu. / Source: Dissertation Abstracts International, Volume: 68-03, Section: B, page: 1716. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (p. 113-120). / 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 Soung-Yue Liew. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 55-57). / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- The Basic Principles of Routing Algorithms --- p.10 / Chapter 2.1 --- The principles of sequential algorithms --- p.11 / Chapter 2.1.1 --- Edge-coloring of bipartite graph with maximum degree two --- p.11 / Chapter 2.1.2 --- Edge-coloring of bipartite graph with maximum degree M --- p.14 / Chapter 2.2 --- Looping algorithm --- p.17 / Chapter 2.2.1 --- Paull's Matrix --- p.17 / Chapter 2.2.2 --- Chain to be rearranged in Paull's Matrix --- p.18 / Chapter 2.3 --- The principles of parallel algorithms --- p.19 / Chapter 2.3.1 --- Edge-coloring of bipartite graph with maximum degree two --- p.20 / Chapter 2.3.2 --- Edge-coloring of bipartite graph with maximum degree 2m --- p.22 / Chapter 3 --- Parallel routing algorithm in Benes-Clos networks --- p.25 / Chapter 3.1 --- Routing properties of Benes networks --- p.25 / Chapter 3.1.1 --- Three-stage structure and routing constraints --- p.26 / Chapter 3.1.2 --- Algebraic interpretation of connection set up problem --- p.29 / Chapter 3.1.3 --- Equivalent classes --- p.31 / Chapter 3.2 --- Parallel routing algorithm --- p.32 / Chapter 3.2.1 --- Basic principles --- p.32 / Chapter 3.2.2 --- Initialization --- p.34 / Chapter 3.2.3 --- Algorithm --- p.36 / Chapter 3.2.4 --- Set up the states and determine π for next stage --- p.37 / Chapter 3.2.5 --- Simulation results --- p.40 / Chapter 3.2.6 --- Time complexity --- p.41 / Chapter 3.3 --- Contention resolution --- p.41 / Chapter 3.4 --- Algorithms applied to Clos network with 2m central switches --- p.43 / Chapter 3.5 --- Parallel algorithms in rearrangeability --- p.47 / Chapter 4 --- Conclusions --- p.52

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

by Wai-Hung Kwok. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Preliminaries - Routing in Classical Circuit Switching Clos Net- work --- p.9 / Chapter 2.1 --- Formulation of route assignment as bipartite multigraph coloring problem --- p.10 / Chapter 2.1.1 --- Definitions --- p.10 / Chapter 2.1.2 --- Problem formulation --- p.11 / Chapter 2.2 --- Edge-coloring of bipartite graph --- p.12 / Chapter 2.3 --- Routing algorithm - Paull's matrix --- p.15 / Chapter 3 --- Principle of Routing Algorithm --- p.18 / Chapter 3.1 --- Definitions --- p.18 / Chapter 3.1.1 --- Bandwidth quantization --- p.18 / Chapter 3.1.2 --- Connection splitting --- p.20 / Chapter 3.2 --- Non-blocking conditions --- p.20 / Chapter 3.2.1 --- Rearrangeably non-blocking condition --- p.21 / Chapter 3.2.2 --- Strictly non-blocking condition --- p.22 / Chapter 3.3 --- Formulation of route assignment as weighted bipartite multigraph coloring problem --- p.23 / Chapter 3.4 --- Edge-coloring of weighted bipartite multigraph with edge splitting --- p.25 / Chapter 3.4.1 --- Procedures --- p.25 / Chapter 3.4.2 --- Example --- p.27 / Chapter 3.4.3 --- Validity of the color rearrangement procedure --- p.29 / Chapter 4 --- Routing Algorithm --- p.32 / Chapter 4.1 --- Capacity allocation matrix --- p.32 / Chapter 4.2 --- Connection setup --- p.34 / Chapter 4.2.1 --- Non-splitting stage --- p.35 / Chapter 4.2.2 --- Splitting stage --- p.36 / Chapter 4.2.3 --- Recursive rearrangement stage --- p.37 / Chapter 4.3 --- Connection release --- p.40 / Chapter 4.4 --- Realization of route assignment in packet level --- p.42 / Chapter 5 --- Performance Studies --- p.45 / Chapter 5.1 --- External blocking probability --- p.45 / Chapter 5.1.1 --- Reduced load approximation --- p.46 / Chapter 5.1.2 --- Comparison of external blocking probabilities --- p.48 / Chapter 5.2 --- Connection splitting probability --- p.50 / Chapter 5.3 --- Recursive rearrangement probability --- p.50 / Chapter 6 --- Conclusions --- p.52

Lai Kwok-yin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 125-130). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Automatic Textual Document Categorization --- p.1 / Chapter 1.2 --- Meta-Learning Approach For Text Categorization --- p.3 / Chapter 1.3 --- Contributions --- p.6 / Chapter 1.4 --- Organization of the Thesis --- p.7 / Chapter 2 --- Related Work --- p.9 / Chapter 2.1 --- Existing Automatic Document Categorization Approaches --- p.9 / Chapter 2.2 --- Existing Meta-Learning Approaches For Information Retrieval --- p.14 / Chapter 2.3 --- Our Meta-Learning Approaches --- p.20 / Chapter 3 --- Document Pre-Processing --- p.22 / Chapter 3.1 --- Document Representation --- p.22 / Chapter 3.2 --- Classification Scheme Learning Strategy --- p.25 / Chapter 4 --- Linear Combination Approach --- p.30 / Chapter 4.1 --- Overview --- p.30 / Chapter 4.2 --- Linear Combination Approach - The Algorithm --- p.33 / Chapter 4.2.1 --- Equal Weighting Strategy --- p.34 / Chapter 4.2.2 --- Weighting Strategy Based On Utility Measure --- p.34 / Chapter 4.2.3 --- Weighting Strategy Based On Document Rank --- p.35 / Chapter 4.3 --- Comparisons of Linear Combination Approach and Existing Meta-Learning Methods --- p.36 / Chapter 4.3.1 --- LC versus Simple Majority Voting --- p.36 / Chapter 4.3.2 --- LC versus BORG --- p.38 / Chapter 4.3.3 --- LC versus Restricted Linear Combination Method --- p.38 / Chapter 5 --- The New Meta-Learning Model - MUDOF --- p.40 / Chapter 5.1 --- Overview --- p.41 / Chapter 5.2 --- Document Feature Characteristics --- p.42 / Chapter 5.3 --- Classification Errors --- p.44 / Chapter 5.4 --- Linear Regression Model --- p.45 / Chapter 5.5 --- The MUDOF Algorithm --- p.47 / Chapter 6 --- Incorporating MUDOF into Linear Combination approach --- p.52 / Chapter 6.1 --- Background --- p.52 / Chapter 6.2 --- Overview of MUDOF2 --- p.54 / Chapter 6.3 --- Major Components of the MUDOF2 --- p.57 / Chapter 6.4 --- The MUDOF2 Algorithm --- p.59 / Chapter 7 --- Experimental Setup --- p.66 / Chapter 7.1 --- Document Collection --- p.66 / Chapter 7.2 --- Evaluation Metric --- p.68 / Chapter 7.3 --- Component Classification Algorithms --- p.71 / Chapter 7.4 --- Categorical Document Feature Characteristics for MUDOF and MUDOF2 --- p.72 / Chapter 8 --- Experimental Results and Analysis --- p.74 / Chapter 8.1 --- Performance of Linear Combination Approach --- p.74 / Chapter 8.2 --- Performance of the MUDOF Approach --- p.78 / Chapter 8.3 --- Performance of MUDOF2 Approach --- p.87 / Chapter 9 --- Conclusions and Future Work --- p.96 / Chapter 9.1 --- Conclusions --- p.96 / Chapter 9.2 --- Future Work --- p.98 / Chapter A --- Details of Experimental Results for Reuters-21578 corpus --- p.99 / Chapter B --- Details of Experimental Results for OHSUMED corpus --- p.114 / Bibliography --- p.125