Computing Science - Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

Minor-embedding planar graphs in grid graphs

Author: 
Date created: 
2016-05-17
Abstract: 

A recent development in solving challenging combinatorial optimization problems is the introduction of hardware that performs optimization by quantum annealing. Exploiting this hardware to solve a problem requires first solving a graph minor-embedding problem, which is also apparently intractable. Motivated by this application, we consider the special case of finding a minor-embedding of a planar graph in a grid graph. We introduce two algorithmic approaches to the problem, based on planarity-testing techniques. For one approach, we provide an implementation and an experimental evaluation demonstrating its potential.

Document type: 
Thesis
Senior supervisor: 
David Mitchell
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

A Formal Semantic Framework for Maritime Situation Analysis

Date created: 
2016-04-18
Abstract: 

Situation analysis is a process of examining a situation to provide and maintain a state of situation awareness which is critical for dynamic decision-making in responding to real-world situations. Limited surveillance resources constrain maritime domain awareness and compromise safety and security coverage at all times. This calls for innovative intelligent systems for interactive situation analysis to assist marine authorities in their routine surveillance operations. In this research, we use the Abstract State Machine method to formally model and design a precise yet concise situation analysis framework. The backbone of our model is an existing abstract framework. We expand and enrich it by capturing detailed requirements and specifying the precise behavior of its components to process, analyze, and fuse large volumes of marine traffic data received from various sources. To this end, we propose a time series structure for rendering vessel trajectories from real-time data.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Uwe Glässer
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

On the importance of decoding in semi-supervised learning

Date created: 
2016-04-01
Abstract: 

In many natural language processing (NLP) tasks a large amount of unlabelled data is available while labelled data is hard to attain. Bootstrapping techniques have been shown to be very successful on a variety of NLP tasks using only a small amount of supervision. In this research we have studied different bootstrapping techniques that separate the training step of the algorithm from the decoding step which produces the argmax label on test data. We then explore generative models trained in the conventional way using the EM algorithm but we use an initialization step and a decoding techniques similar to the Yarowsky bootstrapping algorithm. The new approach is tested on the named entity classification and word sense disambiguation tasks and has shown significant improvement over previous generative models.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Anoop Sarkar
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

A Hierarchical Deep Temporal Model for Group Activity Recognition

Date created: 
2016-04-12
Abstract: 

In group activity recognition, the temporal dynamics of the whole activity can be inferredbased on the dynamics of the individual people representing the activity. We build a deepmodel to capture these dynamics based on LSTM (long-short term memory) models. Tomake use of these observations, we present a 2-stage deep temporal model for the groupactivity recognition problem. In our model, a LSTM model is designed to represent actiondynamics of individual people in a sequence and another LSTM model is designed to aggregatehuman-level information for whole activity understanding. We evaluate our modelover two datasets: the collective activity dataset and a new volleyball dataset. Experimentalresults demonstrate that our proposed model improves group activity recognitionperformance as compared to baseline methods.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Greg Mori
Mehrsan Javan
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Matrix Partitions of Graphs: Algorithms and Complexity

Date created: 
2016-03-23
Abstract: 

Recently, there has been much interest in studying certain graph partitions that generalize graph colourings and homomorphisms. They are described by a pattern, usually viewed asa symmetric $\{0, 1, *\}$-matrix $M$. Existing results focus on recognition algorithms and characterization theorems for graphsthat admit such $M$-partitions, or $M$-partitions in which vertices of the input graph $G$have lists of admissible parts. For (homomorphism) problems with costs, researchers havealso investigated the approximability of the problem.In this thesis, we study the complexity of these matrix partition problems.First, we investigate the complexity of counting $M$-partitions. The complexity of counting problemsfor graph colourings and graph homomorphisms has been previously classified, and most turned out to be $\sharpP$-complete, with only trivial exceptions.By contrast, we exhibit many $M$-partition problems with interesting non-trivial counting algorithms; moreover these algorithms appear to depend on highly combinatorial tools. In fact, our tools are sufficient to classify the complexity of counting$M$-partitions for all matrices $M$ of size less than four.Then, we turn our attention to the homomorphism problems with costs.Previous results include partial classification of approximation complexityfor doubly convex bipartite graphs.We complete these results and extend them to all digraphs.We prove that if $H$ is a co-circular arc bigraph,then the minimum cost graph homomorphism problem to $H$ admits a polynomial time constant ratio approximation algorithm.This solves a problem posed in an earlier paper. Our algorithm is obtained by derandomizinga two-phase randomized procedure. In the final third of the thesis, we present a partial dichotomy forthe complexity of exact minimization of homomorphism costs,when the cost function is a constant across the vertices of the input graph. We show that the dichotomy is complete when the target graph is a tree.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Pavol Hell
Joseph G. Peters
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Deep structured models for group activity recognition

Author: 
Date created: 
2015-12-18
Abstract: 

This work presents a deep neural-network-based hierarchical graphical model for individual and group activity recognition in surveillance scenes. As the first step, deep networks are used to recognize activities of individual people in a scene. Then, a neural network-based hierarchical graphical model refines the predicted labels for each activity by considering dependencies between different classes. Similar to the inference mechanism in a probabilistic graphical model, the refinement step mimics a message-passing encoded into a deep neural network architecture. We show that this approach can be effective in group activity recognition and the deep graphical model improving recognition rates over baseline methods.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Greg Mori
Arash Vahdat
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Community Detection in Networks using PageRank Contributions

Author: 
Date created: 
2016-03-08
Abstract: 

The modern science of networks has made significant contributions to our understanding of complex real world systems. One of the most relevant features of graphs representing the real world networks is their community structure. Therefore, a large body of work in industry and academia has been devoted to identifying community structure in complex networks. In this thesis, we design PC-KM, a variation of $k$-means clustering using PageRank contributions to detect communities in networks. In order to scale to large size networks, we propose another method PPC-KM, which uses random projections to reduce dimensionality while preserving features required for community detection. We also present a fuzzy version of PPC-KM to consider the overlapping communities in networks. We evaluate our algorithms on several datasets. The results show that our methods detect communities with high performance on real world networks.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Andrei Bulatov
Jian Pei
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Performance and energy efficiency of virtual machine based clouds

Author: 
Date created: 
2016-01-05
Abstract: 

Combining high-speed network accesses and powerful computer virtualization, cloud computing provides an elastic and cost-effective service paradigm for the development of resource-hungry new applications as well as the expansion of a broad spectrum of existing applications. Virtualization has become wide spread in modern computers and operating systems; the extensive use of virtual machines (VMs) in a networked cloud environment, however, comes with unprecedented overhead. In this thesis we study the impact of virtualization overhead on real-world systems. First, we present a study on the performance of modern virtualization solutions under DoS attacks. We experiment with the full spectrum of modern virtualization techniques, from paravirtualization, hardware virtualization, to container virtualization, with a comprehensive set of benchmarks. Our results reveal severe vulnerability of modern virtualization. Further, this thesis presents an empirical study on the power consumption of typical virtualization packages while performing network tasks. We find that both Hardware Virtualization and Paravirtualization add considerable energy overhead, affecting both sending and receiving, and a busy virtualized web-server may consume 40% more energy than its non-virtualized counterparts. Next, we focused on cloud network performance instability in the public cloud. Through measurement of real world cloud platforms, we find that network performance degradation and variation phenomena can be prevalent and significant with both TCP and UDP traffic, even within the same data center, and even with a lightly utilized network. Our in-depth measurement and detailed system analysis reveal that the performance variation and degradation are mainly due to the requirements of the CPU in both computation and network communication. Finally, we study the use of virtual machine based clouds to provide infrastructure to support cloud gaming. For each issue we further suggest solutions to resolve performance issues associated with virtualized environments, both at the hypervisor level and, inside a VM, at the operating system level. Our implementation on both large public clouds and our cloud testbed have demonstrated their practicality as well as their effectiveness in improving and stabilizing the energy consumption and performance of virtual machine based clouds.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Jiangchuan Liu
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Boosted Object Detection Based on Local Features

Author: 
Date created: 
2016-04-07
Abstract: 

Object detection is to find and localize objects of a specific class in images or videos. This task is the foundation of image and video understanding, thus it becomes one of the most popular topics in the area of computer vision and pattern recognition. Object detection is not only essential for the study of computer vision, pattern recognition and image processing, but also valuable in the applications of public safety, entertainment and business. In this research, we aim to solve this problem in two focused areas: the local feature design, and the boosting learning. Our research on local features could be summarized into a hierarchical structure with 3 levels. The features in different levels capture different object characteristic information. In the lower level, we investigate how to design effective binary features, which perform quite well for the object categories with small intra-class variations. In the middle level, we consider integrating the gradient information and structural information together. This results in more discriminative gradient features. In the higher level, we discuss how to construct the co-occurrence features. Using such features, we may get a classifier with high accuracy for general object detection.After the feature extraction, boosted classifiers are learned for the final decision. We work on two aspects to improve the effectiveness of boosting learning. Firstly, we improve the discriminative ability of the weak classifiers by the proposed basis mapping. We show that learning in the mapped space is more effective compared to learning in the original space. In addition, we explore the efficiency-accuracy trade-off problem in boosting learning. The Generalization and Efficiency Balance (GEB) framework, and the hierarchical weak classifier are designed for this target. As a result, the resulting boosted classifiers not only achieve high accuracy, but also have good generalization and efficiency. The performance of the proposed local features and boosting algorithms are evaluated using the benchmark datasets of faces, pedestrians, and general objects. The experimental results show that our work achieves better accuracy compared to the methods using traditional features and machine learning algorithms.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ze-Nian Li
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Dissertation) Ph.D.

Sensitive disclosures under differential privacy guarantees

Author: 
Date created: 
2016-01-15
Abstract: 

Most syntactic methods consider non-independent reasoning (NIR) as a privacy violation and smooth the distribution of published data to avoid sensitive NIR, where NIR allows the information about one record in the data could be learned from the information of other records in the data. The drawback of this approach is that it limits the utility of learning statistical relationships. The differential privacy criterion considers NIR as a non-privacy violation, therefore, enables learning statistical relationships, but at the cost of potential disclosures through NIR. In this thesis, we investigate the extent to which private information of an individual may be disclosed through NIR by query answers that satisfy differential privacy. We first define what a disclosure of NIR means by randomized query answers, then present a formal analysis on such disclosures by differentially private query answers. Our analysis on real life data sets demonstrates that while disclosures of NIR can be eliminated by adopting a more restricted setting of differential privacy, such settings adversely affects the utility of query answers for data analysis, and this conflict can not be easily resolved because both disclosures and utility depend on the accuracy of noisy query answers. This study suggests that under the assumption that the disclosure through NIR is a privacy concern, differential privacy is not suitable because it does not provide both privacy and utility. The question is whether it is possible to (1) allow learning statistical relationships, yet (2) prevent sensitive NIR about an individual. In the second part of the thesis, we present a data perturbation and sampling method to achieve both (1) and (2). The enabling mechanism is a new privacy criterion that distinguishes the two types of NIR in (1) and (2) with the help of the law of large numbers. In particular, the record sampling effectively prevents the sensitive disclosure in (2) while having less effect on the statistical learning in (1). The data perturbation and sampling method are evaluated in real life data sets in terms of both sensitive disclosures and utility. Empirical results confirm that disclosures can be prevented with minor loss of utility.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ke Wang
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.