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

Receive updates for this collection

jViz.RNA 4.0 - Advanced integration methods, pseudoknot visualization, and online editing in the context of RNA secondary structure visualization

Author: 
Date created: 
2018-04-05
Abstract: 

RNA visualization software tools have traditionally presented a static visualization of RNA molecules with limited ability for users to interact with the resulting image once it is complete. Only a few tools allowed for dynamic structures; one such tool is jViz.RNA 2.0. Currently, jViz.RNA 2.0 employs a unique method for the creation of the RNA molecule layout by mapping the RNA nucleotides into vertexes in a graph, which we call the detailed graph, and then utilizes a Newtonian mechanics inspired system of forces to calculate a layout for the RNA molecule. The work presented here focuses on improvements to jViz.RNA 2.0 in four areas: First, the drawing of RNA secondary structures according to common drawing conventions employing a new underlying graph representation. Second, employing advanced numerical integration methods (the Backward Euler Method) to achieve dramatic run-time performance improvements utilizing the new graph implementation. Third, the ability to classify and visualize pseudoknots was added to jViz.RNA in order to extend the set of RNA structures that can be visualized. Finally, online base-pair removal and addition capabilities were incorporated into jViz.RNA in the interest of providing users with the capacity to modify, edit, and create RNA molecules from existing alternative representations (e.g. images or drawings). With regards to results, comparing the compressed graph and detailed graph implementations, it was found that the compressed graph produces results more consistent with RNA drawing conventions, and does so noticeably faster. Additionally, the advantages of the Backward Euler method as a more stable approach to mitigate interactions between users and the RNA model, allowing users to better and faster manipulate the RNA model, have been shown conclusively. The incorporation of pseudoknot visualization capacities demonstrated a new high degree of utility and flexibility since users are now able to visualize the majority, if not entirety, of biologically known RNAs, as well as modify the given pseudoknot representation. The implementation of online structure editing functionality allows users to construct related or theoretical molecules from existing ones, as well as construct arbitrary RNA structures from their primary nucleotide sequence.

Document type: 
Thesis
Senior supervisor: 
Kay Wiese
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Crowdsourced livecast systems: Measurement and enhancement

Author: 
Date created: 
2018-03-01
Abstract: 

Empowered by today's rich tools for media generation and collaborative production, multimedia service paradigm is shifting from the conventional single source, to multi-source, to many sources, and now towards crowdsource, where the available media sources for the content of interest become highly diverse and scalable. Such crowdsourced livecast systems as Twitch.tv, YouTube Gaming, and Periscope enable a new generation of user-generated livecast systems, attracting an increasing number of viewers all over the world. Yet the sources are managed by unprofessional broadcasters, and often have limited computation capacities and dynamic network conditions. They can even join or leave at will, or crash at any time. In this thesis, we first conduct a systematic study on the existing crowdsourced livecast systems. We outline the inside architecture using both the crawled data and the captured traffic data from local broadcasters/viewers. We then reveal that a significant portion of the unpopular and dynamic broadcasters are consuming considerable system resources. Because cloud computing provides resizable, reliable, and scalable bandwidth and computational resources, which naturally becomes an effective solution to leverage heterogeneous and dynamic workloads. Yet, it is a challenge to utilize the resources from the cloud cost-effectively. We thus propose a cloud-assisted design to smartly ingest the sources and cooperatively utilize the resources from dedicated servers and public clouds. In current crowdsourced livecast systems, crowdsourced gamecasting is the most popular application, in which gamers lively broadcast game playthroughs to fellow viewers using their desktop, laptop, even mobile devices. These gamers' patterns, which instantly pilot the corresponding gamecastings and viewers' fixations, have not been explored by previous studies. Since mobile gamers and eSports gamers occupy a large portion of content generators. In this thesis, we target on two typical crowdsourced gamecasting scenarios, i.e., mobile gamecasting and eSports gamecasting, respectively. We investigate the gamers' patterns to explore their effects on viewers and employ intelligent approaches, e.g., learning-based techniques, to capture the associations between gamers' patterns and viewers' experiences. Then, we employ such associations to optimize the streaming transcoding and distribution.

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

Generating natural language summary for image sets

Author: 
Date created: 
2018-05-31
Abstract: 

We address the problem of summarizing an image set with a natural language caption. We present PlacesCap, a new dataset for image set summarization. Our dataset consists of 11,661 image sets with a total of 116,113 images, where each set is summarized by a 3 sentence caption. We propose novel pooling operators for permutation invariant sets of feature maps, and empirically evaluate image set summarization models based on those operators. We also conduct experiments of image set classification and show competitive performance for the proposed set pooling operators.

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

Online density bursting subgraph detection from temporal graphs

Author: 
Date created: 
2018-05-07
Abstract: 

Given a temporal weighted graph that consists of a potentially endless stream of updates, we are interested in finding density bursting subgraphs (DBS), where a DBS is a subgraph that accumulates its density at the fastest speed. Online DBS detection enjoys many novel applications. At the same time, it is challenging since the time duration of a DBS can be arbitrarily long but a limited size storage can buffer only up to a certain number of updates. To tackle this problem, we observe the critical decomposability of DBSs and show that a DBS with a large time duration can be decomposed into a set of indecomposable DBSs with equal or larger burstiness. We further prove that the time duration of an indecomposable DBS is upper bounded and propose an efficient method TopkDBSOL to detect indecomposable DBSs in an online manner. Extensive experiments demonstrate the effectiveness, efficiency, and scalability of TopkDBSOL in detecting significant DBSs from temporal graphs.

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

Exploring behavioral data in online social media with focus on user connectivity and mobility

Author: 
Date created: 
2018-04-23
Abstract: 

With the booming development of online social media in recent years, massive and variety of behavioral data, such as social interactions data and user's E-travel sharing data, are generated by the users throughout the world everyday. Exploring and analyzing such data helps to understand users' preferences, unearth the contained tremendous knowledge, and identify new problems and business opportunities, thus is beneficial for social media users, service providers, etc. In this thesis, we are specifically interested in the user connectivity/interaction behaviors, e.g., friendship creation, and the mobility behaviors, e.g., check-in sequence at Point-of-Interest (POIs), that involve rich semantic information on nodes and edges of the social networks, and study three practical problems in different applications. We first analyze users' social connectivity behaviors from a new angle and study a problem of mining non-homophily social ties, aiming at discovering interesting but unexpected group-level social ties that do not follow the homophily phenomenon. We propose a novel ranking metric to identify such social ties and develop an efficient mining algorithm specifically for the new metric. In our second work, we explore users' check-in sequences or travel routes, and study a problem of personalized trip recommendation meets real-world constraints, by considering personalized rating on POIs and multiple constraints such as the time budget, the time window for the POI availability, the uncertainty of traveling time between POIs. We develop two efficient optimal solutions and two heuristic solutions for finding "good trips" with a significantly better runtime. Finally, in consideration of the sparsity of users' historical rating data and people's dynamically changed mind over time, we further study an on-demand route search problem with personalized diversity requirement on POIs, where users can specify their preferred features for the route and a personalized quantity (number of POIs) and variety (the coverage of the specified features) trade-offs. We propose to model users' personalized route diversity requirement by submodular functions that support the diminishing marginal utility property. We design generic and elegant optimal algorithm as well as heuristic algorithms. Comprehensive empirical evaluations on real life data sets demonstrate the effectiveness and efficiency of our methods.

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

Enabling autonomous mobile robots in dynamic environments with computer vision

Date created: 
2018-04-19
Abstract: 

Autonomous mobile robots are becoming more prevalent in our society as they become more useful. Often the environments we would like to see robots working in will be dynamic, with objects like people moving throughout. This thesis explores methods to make autonomous mobile robots more effective in the presence of dynamic objects. Specifically, two applications are developed on top of existing computer vision techniques where robots interact directly with moving objects. The first application involves multiple robots collaboratively sensing and following an arbitrary moving object. This is the first demonstration of its kind where robots jointly localize themselves and an object of interest while planning motion that is sympathetic to the vision system. Live robot experiments are conducted demonstrating the efficacy of the proposed system. The second application is a novel human-robot interaction system based on face engagement applied to an unmanned aerial vehicle (UAV). A unique use of facial recognition software enables an uninstrumented user to command a UAV with only their face. A series of experiments demonstrate the effectiveness of the interaction system for sending UAVs on a variety of flight trajectories.

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

Structured label inference for visual understanding

Author: 
Date created: 
2018-04-18
Abstract: 

Visual data such as images and videos contain a rich source of structured semantic labels as well as a wide range of interacting components. Visual content could be assigned with fine-grained labels describing major components, coarse-grained labels depicting high level abstractions, or a set of labels revealing attributes. Such categorization over different, interacting layers of labels evinces the potential for a graph-based encoding of label information. In this thesis, we exploit this rich structure for performing graph-based inference in label space for a number of tasks: multi-label image and video classification and action detection in untrimmed videos. We consider the use of the Bidirectional Inference Neural Network (BINN) and Structured Inference Neural Network (SINN) for performing graph-based inference in label space and propose a Long Short-Term Memory (LSTM) based extension for exploiting activity progression on untrimmed videos. The methods were evaluated on (i) the Animal with Attributes (AwA), Scene Understanding (SUN) and NUS-WIDE datasets for multi-label image classification, (ii) the first two releases of the YouTube-8M large scale dataset for multi-label video classification, and (iii) the THUMOS’14 and MultiTHUMOS video datasets for action detection. Our results demonstrate the effectiveness of structured label inference in these challenging tasks, achieving significant improvements against baselines.

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

Robust real-time hands-and-face detection for human robot interaction

Date created: 
2018-04-27
Abstract: 

With recent advances, robots have become more affordable and intelligent, which expands their application domain and number of consumers. Having robots around us in our daily lives creates a demand for an interaction system for communicating humans' intentions and commands to robots. We are interested in interactions that are easy, intuitive, and do not require the human to use any additional equipment. We present a robust real-time system for visual detection of hands and faces in RGB and gray-scale images based on a Deep Convolutional Neural Network. This system is designed to meet the requirements of a hands-free interface to UAVs described below that could be used for communicating to other robots equipped with a monocular camera using only hands and face gestures without any extra instruments. This work is accompanied by a novel hands-and-faces detection dataset gathered and labelled from a wide variety of sources including our own Human-UAV interaction videos, and several third-party datasets. By training our model on all these data, we obtain qualitatively good detection results in terms of both accuracy and speed on a commodity GPU. The same detector gives state-of-the-art accuracy and speed in a hand-detection benchmark and competitive results in a face detection benchmark. To demonstrate its effectiveness for Human-Robot Interaction we describe its use as the input to a novel, simple but practical gestural Human-UAV interface for static gesture detection based on hand position relative to the face. A small vocabulary of hand gestures is used to demonstrate our end-to-end pipeline for un-instrumented human-UAV interaction useful for entertainment or industrial applications. All software, training and test data produced for this thesis is released as an Open Source contribution.

Document type: 
Thesis
File(s): 
A demonstration of our system for un-instrumented Human-UAV interaction
Senior supervisor: 
Richard Vaughan
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

On some nonlinear assignment problems

Author: 
Date created: 
2018-02-27
Abstract: 

Linear assignment problem (commonly referred to as just assignment problem) is a fundamental problem in combinatorial optimization. The goal is to assign n workers to do n jobs so that the linear sum of corresponding costs is minimized. The linear assignment problem is thoroughly studied and has a O(n^3) solution with Hungarian algorithm. Nevertheless, a wide range of applications involving assignments are naturally modeled with more complex objective functions (for example quadratic sum as in quadratic assignment problem), and are much more computationally challenging. In this thesis we discuss our results on the bilinear assignment problem, which generalizes the quadratic assignment problem, and is also motivated by several unique applications. The focus is on computational complexity, solvable special cases, approximations, linearizations as well as local search algorithms and other heuristic approaches for the problem. We also present our results on few applied projects, where modelling the underlying problem as a nonlinear assignment was instrumental.

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

Model trees for identifying exceptional players in the NHL and NBA draft

Author: 
Date created: 
2018-04-10
Abstract: 

Drafting players is crucial for a team’s success. We describe a data-driven interpretable approach for assessing prospects in the National Hockey League and National Basketball Association. Previous approaches have built a predictive model based on player features, or derived performance predictions from comparable players. Our work develops model tree learning, which incorporates strengths of both model-based and cohort-based approaches. A model tree partitions the feature space according to the values or learned thresholds of features. Each leaf node in the tree defines a group of players, with its own regression model. Compared to a single model, the model tree forms an ensemble that increases predictive power. Compared to cohort-based approaches, the groups of comparables are discovered from the data, without requiring a similarity metric. The model tree shows better predictive performance than the actual draft order from team's decision. It can also be used to highlight strongest points of players.

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