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

Receive updates for this collection

Undefined Behaviour in Mutation Testing

Date created: 
2016-09-13
Abstract: 

Mutation testing is used to evaluate the quality of a test suite by measuring how well the test suite detects systematically seeded faults (mutants). However, in the C programming language, the created mutants may introduce undefined behaviour. Such a mutant has no meaning and thus cannot meaningfully be reported as either detected or undetected by mutation testing. This introduces two problems. First, it increases the number of mutants that must be considered for mutation testing. Second, it creates a potential for bias in the mutation score when mutants with undefined behavior count toward the number of detected or undetected mutants. This thesis makes contributions toward identifying the ways in which traditional mutation testing mechanisms may lead to undefined behavior. It furthermore introduces automated analyses for statically detecting mutants that cause undefined behavior so that they can be filtered out ahead of time. A proof of concept implementation using Clang and LLVM validates that these techniques work for real world programs in the C programming language.

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

Planarity Based Algorithms for Minor Embedding in Grid Graphs

Date created: 
2016-07-20
Abstract: 

We present heuristic algorithms for minor embedding planar graphs in grids. Our work is motivated by the development of quantum computing hardware that performs quantum annealing. This hardware can be used to solve hard combinatorial problems, but requires the graph of each problem instance to be minor embedded in a graph that models the hardware. Hence, there is a need for practical minor embedding algorithms. We restrict our attention to planar graphs, and thus are able to make use of existing graph drawing methods. We present two algorithms for minor embedding planar graphs in grid graphs, and provide an experimental evaluation of one.

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

Learning 3D scene synthesis from RGB-D Images

Date created: 
2016-06-14
Abstract: 

We present a data-driven method for synthesizing 3D indoor scenes by inserting objects progressively into an initial, possibly, empty scene. Instead of relying on few hundreds of handcrafted 3D scenes, we take advantage of existing large-scale annotated RGB-D datasets, to form the prior knowledge for our synthesis task. Our object insertion scheme follows a cooccurrence model and an arrangement model, both learned from the SUN RGB_D dataset. Compared to previous works on probabilistic learning for object placement, we make two contributions. First, we learn various classes of higher-order object-object relations which effectively enable considering objects in semantically formed groups rather than by individuals. Second, while our algorithm inserts objects one at a time, it attains holistic plausibility of the whole current scene while offering controllability through progressive synthesis. We conducted several user studies to demonstrate the effectiveness of our synthesis method.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Hao Zhang
Ping Tan
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Object-Color Description Under Varying Illumination

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

Given a fixed and uniform illumination, metameric objects appear as the same color. However, when the illumination is altered, two metameric reflecting objects under the first illuminant may no longer produce the same color signal under the second. This situation is called metamer mismatching. Metamer mismatching poses several challenges for the camera and display industries as well as color-based computer vision technology.In light of metamer mismatching, the present study criticizes the conventional approaches to color description when the illuminant alters, and then lays a foundation to robustly describe object colors under varying illumination conditions. Later, the degree of metamer mismatching is used as a measure of the quality of lights. We demonstrate that although the common color spaces such as CIELAB and related spaces in the literature may work well for a fixed illuminant, they can lead to poor results when the illuminant is changed. In view of these problems, new descriptors for hue, lightness and chroma are presented that are based on properties of a Gaussian-like spectrum metameric to the given color tristimulus coordinates. Experiments show that the new Gaussian-based appearance descriptors correlate with different descriptors as well as the CIECAM02 appearance model does on average. Furthermore, the Gaussian-based descriptors are significantly more stable than the descriptors defined in the CIECAM02 appearance model.Afterwards, the problem of predicting how the color signal arising in response to light reflected from the surface of an object is likely to change when the lighting alters is investigated. A new method, called the Gaussian Metamer (GM) method is proposed for predicting what a color signal observed from a surface under a first light is likely to be when the same surface is lit instead by a second light. Due to metamer mismatching, there is not a unique answer for this problem. Our approach is to use one of the possible metamers that is likely to do well on average. The results outperform other state-of-the-art prediction methods.

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

On Crowdsourced Live Video Streaming with Heterogeneous Broadcasters and Viewers

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

Recent years have witnessed the booming popularity of Crowdsourced Live Streaming (CLS) platforms, through which numerous amateur broadcasters lively stream their video contents to viewers around the world. The heterogeneous quality and format of source stream however require massive computational resource to transcode it into multiple industrial standard quality versions to serve viewers with distinct configurations. In this thesis, we analyze the large dataset we captured from the popular CLS platform Twitch TV. We then present a generic framework utilizing the powerful and elastic cloud computing services for crowdsourced live streaming with heterogeneous broadcasters and viewers. We jointly consider the viewer satisfaction and the service availability/pricing of geo-distributed cloud resources for transcoding. We first develop an optimal scheduler for allocating cloud instances with no regional constraints, and then extend the solution to accommodate regional constraints. However, given the considerable cost of cloud services, and the fact that the CLS platform charges nothing from viewers as a free system in nature, cloud-based transcoding solutions can only provide limited service, resulting in the current real-world situation. On the other hand, we witness huge computational resource among the massive fellow viewers in CLS systems that could potentially be used for transcoding. Inspired by the paradigm of Fog Computing, we propose CrowdTranscoding, a novel framework for CLS systems to smartly offload the transcoding assignment to the edge of network. We evaluate both of our novel frameworks with extensive trace-driven simulations and PlanetLab-based experiments, under diverse parameter settings. The superiority of our designs has been confirmed, while the experiment results also offer some further practical hints towards real-world migration.

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

Maritime domain awareness: Engineering analytic frameworks

Date created: 
2016-04-18
Abstract: 

Maritime Domain Awareness is critical for protecting sea lanes, ports, harbors, offshore structures like oil and gas rigs and other types of critical infrastructure against common threats and illegal activities. Limited surveillance resources constrain maritime domain awareness and compromise full safety and security coverage at all times. This situation calls for innovative intelligent systems for interactive situation analysis and decision support to assist marine authorities in their routine surveillance operations. The main contribution of this thesis is the formal engineering of robust methodical frameworks for the development of intelligent algorithms, systems, and services for real-time situation analysis, anomaly detection, and decision support; particularly for the maritime domain. Best engineering practice calls for a system to be modeled prior to construction, so one can rigorously inspect and reason about the key system properties, making sure these are both well understood and properly established. We therefore use Abstract State Machine as a Formal Method for engineering these frameworks to address the main aspects of maritime domain awareness including situation analysis and anomaly detection as well as decision support and emergency response. To be more specific, we propose a novel situation analysis approach to analyze marine traffic data and differentiate various scenarios of vessel engagement for the purpose of detecting anomalies of interest for marine vessels that operate over some period of time in relative proximity to each other. We consider such scenarios as probabilistic processes and analyze complex vessel trajectories using machine learning to model common patterns. Specifically, we represent patterns as left-to-right Hidden Markov Models and classify them using Support Vector Machines. To differentiate suspicious activities from unobjectionable behavior, we explore fusion of data and information, including kinematic features, geospatial features, contextual information and maritime domain knowledge. Our experimental evaluation shows the effectiveness of the proposed approach using comprehensive real-world vessel tracking data from coastal waters of North America.

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

Mining Identification Rules for Classifying Mobile Application Traffic

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

Classifying mobile application traffics is important in many network management tasks. Existing works rely on human expertise and reverse engineering to build classification rules. The huge number of mobile applications make it ineffective and even infeasible to do reverse engineering on every mobile application. In this thesis, we design a novel structure of app identification rules. Two algorithms are developed to mine the rules from HTTP header fields without any other external input. In addition, we also explore the function and effects of different HTTP header fields in the identification task. An extensive empirical study on real data verifies the effectiveness of our algorithms.

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

Methods for the Detection of Single Nucleotide Variants and Indels from Cell-Free DNA

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

Successful development and application of precision oncology approaches require robust elucidation of the genomic landscape of a patient's cancer and the ability to monitor therapy-induced genomic changes in the tumour in an inexpensive and minimally invasive manner. Thanks to recent advances in sequencing technologies, "liquid biopsy", the sampling of patient's bodily fluids such as blood, is considered as one of the most promising approaches to achieve this goal. In many cancer patients, especially those with advanced metastatic disease, deep sequencing of cell-free DNA (cfDNA) obtained from patient's blood yields a mixture of reads originating from the normal DNA and from multiple tumour subclones - called circulating tumour DNA (ctDNA). The ctDNA/cfDNA ratio and the proportion of ctDNA originating from specific tumour subclones depend on multiple factors, making comprehensive detection of mutations difficult, especially at early stages of cancer. We introduce SiNVICT, a computational method for analysis of cfDNA sequencing data.

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

Mobile Based OLAP Using Parallel Processing and Multithreading

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

This work is committed to discovering the influence of parallel mechanism on I/O heavy applications such as OLAP operations on remote data set running on a resource constrained client. In this research, we have chosen an Android based smartphone as our client. We have implemented a mobile phone based client-centric OLAP application utilizing the potentiality of parallel processing mechanism of Android. We are dividing user request and associated caching tasks into smaller units and distributing them to multiple threads to execute concurrently. While serving user's requested query data, we are downloading and caching (hash based pre-emptive caching) extra sub-cube data in the background by employing multiple threads running in parallel. This yields better performance for succeeding cross-tab or drill-down actions. We have captured test results by varying number of threads and amount of data size associated with each thread. Result shows that parallel approach has striking performance improvement over sequential approach.

Document type: 
Graduating extended essay / Research project
File(s): 
Senior supervisor: 
Wo-shun Luk
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Project) M.Sc.

Towards Better User Preference Learning for Recommender Systems

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

In recent years, recommender systems have become widely utilized by businesses across industries. Given a set of users, items, and observed user-item interactions, these systems learn user preferences by collective intelligence, and deliver proper items under various contexts to improve user engagements and merchant profits. Collaborative Filtering is the most popular method for recommender systems. The principal idea of Collaborative Filtering is that users might be interested in the items that are preferred by users with similar preferences. Therefore, learning user preferences is the core technique of Collaborative Filtering. In this thesis, we study new methods to help us better understand user preferences from three perspectives. We first dive into each rating that users give on the items, and study the reasons behind the ratings by analyzing user reviews. We propose a unified model that combines the advantages of aspect-based opinion mining and collaborative filtering, which could extract latent aspects and sentiments from reviews and learn users' preferences of different aspects of items collectively. In our next work, we study the problem from each user's perspective, and propose a general and flexible model that embraces several popular models as special cases. The new model achieves better top-N recommendation results on several popular data sets. Finally, we study how to utilize the general structure of the user-item matrix to better apply collaborative filtering methods. We propose a co-clustering based method that first partitions the users and items into several overlapping and focused subgroups, and then applies collaborative filtering methods within each subgroup. The final recommendations for users are aggregated from the results from the subgroups they are involved in. Experimental results show that this method could produce better recommendations than other co-clustering methods and methods that directly apply collaborative filtering on the original user-item matrix.

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