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

Receive updates for this collection

Hybrid Multicast-Unicast Video Streaming over Heterogeneous Cellular Networks

Date created: 
2016-12-19
Abstract: 

The demand for multimedia streaming over mobile networks has been steadily increasing in the past several years. For instance, it has become common for mobile users to stream full TV episodes, sports events, and movies while on the go. Unfortunately, this growth in demand has strained the wireless networks despite the significant increase in their capacities with recent generations. It has also caused a significant increase in the energy consumption at mobile terminals. To overcome these challenges, we first present a novel hybrid unicast and multicast streaming algorithm to minimize the overall energy consumption of mobile terminals as well as the traffic load within cellular networks. Next, we introduce the idea of dynamically configuring cells in mobile networks to form single frequency networks based on the video popularity and user distribution in each cell. We formulate the transmission scheduling problem in such complex networks, and we then present optimal and heuristic solutions to maximize the number of served multimedia streams. Through detailed packet-level simulations, we assess the performance of the aforementioned algorithms with respect to the average service ratio, energy saving, video quality, frame loss rate, initial buffering time, rate of re-buffering events, and bandwidth overhead. Finally, we extend our research to formulate the transmission scheduling problem for adaptive streaming in the emerging heterogeneous cellular networks. We propose an algorithm for the cells in a heterogeneous network to self organize their radio resource allocations in order to minimize the inter-cell interference and increase the average data rate received by mobile terminals. Then we evaluate its performance through extensive simulations of various heterogeneous configurations.

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

Upgrading Bayesian Network Scores for Multi-Relational Data

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

A model selection score measures how well a model fits a dataset. We describe a new method for extending, or upgrading, a Bayesian network (BN) score designed for single-table i.i.d. data to multi-relational datasets (databases). A multi-relational BN model provides an integrated statistical analysis of the interdependent data tables in a database. We focus on log-linear model selection scores. Our key theoretical desideratum is preserving consistency: if a model selection score is statistically consistent for single-table data, then the upgraded score should be statistically consistent for relational data as well. It is difficult if not impossible to define an upgrade method for log-linear model scores that preserves consistency, if the upgraded score is a function of a single model only. We therefore develop a novel approach where an upgraded model score is a {\em gain function} that compares two models: a current vs. an alternative BN structure. Our main theorem establishes that model search based on our upgraded gain function preserves consistency. Empirical evaluation on six benchmark relational databases shows that our upgraded scores select an informative BN structure that strikes a balance between overly sparse and overly dense graph structures.

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

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.