CS Theses & Dissertations 2005

For 2005  graduation dates (in alphabetical order by last name):

APHIDS++: Evolution of a Programmable Hybrid Intrusion Detection System
Alam, Mohammed Shahidul
DOI : 10.14288/1.0051568
URI : http://hdl.handle.net/2429/16452
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Vuong

Shaping and Policy Search for Nearest-Neighbour Control Policies with Applications to Vehicle Steering
Alton, Kenneth
DOI : 10.14288/1.0051749
URI : http://hdl.handle.net/2429/16091
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. van de Panne

Role-Based Control of Shared Application Views
Berry, Lior
DOI : 10.14288/1.0051571
URI : http://hdl.handle.net/2429/16428
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Booth

Model Checking Sequential Consistency and Parameterized Protocols
Bingham, Jesse
DOI : 10.14288/1.0051397
URI : http://hdl.handle.net/2429/17340
Degree : Doctor of Philosophy - PhD
Graduation Date : 2005-11
Supervisors : Dr. Condon, Dr. Hu

Perhaps the most difficult aspect of designing a shared memory multiprocessor is the hardware protocol that facilitates the sharing of memory by multiple processors; these protocols are thus a natural target for formal verification. In this thesis we consider several problems relevant to model checking these protocols. The ultimate specification of a protocol is the memory model. Our more theoretical contributions relate to the problem of model checking a protocol for the well-known memory model sequential consistency (SC). We define a restricted version of SC called decisive SC (DSC), which rules out pathologies admitted by SC, and explore the complexities of its verification problems. Our key results are that DSC of a single behavior is NP-complete, DSC of a protocol is PSPACE-hard, a bounded variant DSQ is decidable in EXPSPACE, and full SC remains undecidable even when we require protocol behaviors to be prefix-closed. Also, we show that SC in conjunction with the ubiquitous property data independence imply DSC, which is strong evidence that restricting attention to DSC will never preclude any real protocol. Our second area of contribution considers parameterized model checking (PMC) of protocols. Here the goal is algorithmic proof over all of the infinite configurations of a protocol family parameterized by one or more quantities. We develop a technique to automatically abstract a family parameterized by the number of addresses and the number of data values, such that (a subset of) SC of the abstraction implies that of the family. We apply this method successfully to two nontrivial protocols, and suggest user-assisted solutions if the abstraction blows up or is too coarse for successful verification. We also contribute an approach for sound and complete processor-PMC of state assertions. The approach uses BDD-based symbolic model checking, and harnesses the theory of well-structured transition systems (WSTS). WSTS disallow conjunctive guards, which are found in many protocols. To extend applicability, we provide an automatic reduction for systems with conjunctive guards. Experiments show the efficacy of our conjunctive guard reduction, and that our approach scales better with the local state of each processor when compared with the classical WSTS algorithm.

Policy Driven Replication
Brodsky, Dmitry David
DOI : 10.14288/1.0051177
URI : http://hdl.handle.net/2429/17152
Degree : Doctor of Philosophy - PhD
Graduation Date : 2005-05
Supervisors : Dr. Feeley, Dr. Hutchinson

From the inception of digital storage, ensuring that data is not lost due to user error, malicious acts, and hardware failure has always been, and still remains, a challenging open problem. This problem is exacerbated by the exponential increase in storage capacity, the proliferation of new digital media, and our growing reliance on digital storage. Today, a typical user stores financial and medical records, music and movie libraries, photo albums, etc, the loss of some of which can be catastrophic. The advent of large robust networks has made it possible to replicate data on remote hosts to protect data from loss. Unfortunately, the growth of network bandwidth is far outstripped by both the growth of storage capacity and our ability to fill it. Thus, most replication systems that uniformly replicate all the data are incapable of protecting the ever increasing amount of data. One important observation is that not all data is created equal. Data such as commercial music and movie libraries can be, given time, rebuilt. Data such as personal, health, and financial records, are much more difficult to reconstruct. Since resources such as network bandwidth are limited, they should be used to protect the important data. In this thesis we propose a Policy Driven Replication (PDR) system that prioritizes data replication according to user-defined policies that specify what data is to be protected, from what failures, and to what extent. By prioritizing what data is replicated, the system conserves limited resources and protects high-priority data from high-probability failures. PDR is a userlevel process that hooks into the file system. It is notified of file creation and modification events, and replicates the data to the hosts specified in the file's policy. In addition, the replica nodes specified in the policy are monitored for liveliness to ensure the policy is followed. PDR provides a model to describe replica nodes and a generic plug-in interface that facilitates the creation of appropriate user interfaces to manage replication policies and to translate these policies into a set of replica nodes. Replica node selection is sensitive to the system topology so that hotspots and message storms are not created.

Multi-Image Matching using Invariant Features
Brown, Matthew
DOI : 10.14288/1.0051634
URI : http://hdl.handle.net/2429/17085
Degree : Doctor of Philosophy - PhD
Graduation Date : 2005-11
Supervisor : Dr. Lowe

This thesis concerns the problems of automatic image stitching and 3D modelling from multiple views. These are basic problems of computer vision, with applications in robotics, architecture, industrial inspection, surveillance, computer graphics and film. Recent work has brought increasing automation to these tasks, but despite a large amount of progress, state-of-the-art algorithms still require some form of user input or assumptions about the image sequence. For example, the best image stitchers currently require an ordered set of input images, or user input to identify the matching images, before automatic registration can proceed. In this work we show how such tasks can be performed automatically and without any user input at all. We formulate the multi-image matching problem as one of finding all matching images, subject to the constraint that they are consistent views from a perspective camera. We use invariant features as a mechanism for finding correspondences, and indexing techniques to efficiently find matches between multiple views. We then find all sets of geometrically consistent feature matches, using a probabilistic model for verification. This allows us to identify each object or scene in the dataset using only the structure already present in the data. The major contributions of this thesis are the development of a system that can automatically recognise and stitch 2D panoramas in unordered image datasets, and a new class of invariant features for this purpose.

Robust Visual Tracking for Multiple Targets
Cai, Yizheng
DOI : 10.14288/1.0051114
URI : http://hdl.handle.net/2429/16480
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Little

Schema Mapping and Query Translation in Heterogeneous Peer-to-Peer XML Databases
Chang, Elaine Qing
DOI : 10.14288/1.0051116
URI : http://hdl.handle.net/2429/16488
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Lakshmanan

Generalized Constraint-Based Inference
Chang, Le
DOI : 10.14288/1.0051112
URI : http://hdl.handle.net/2429/16241
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. Mackworth

Constrained Pursuit-Evasion Problems in the Plane
Cheung, Warren Alexander
DOI : 10.14288/1.0051143
URI : http://hdl.handle.net/2429/16494
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Evans

Presenting Crosscutting Structure with Active Models
Coelho, Wesley da Ponte
DOI : 10.14288/1.0051739
URI : http://hdl.handle.net/2429/16504
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Murphy

Point-Based Level Sets and Progess Towrards Unorganised Particle Based Fluids
Corbett, Richard
DOI : 10.14288/1.0051324
URI : http://hdl.handle.net/2429/16508
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Bridson

Shielding Against Conditioning Side Effects in Graphical Models
Crowley, Mark
DOI : 10.14288/1.0103860
URI : http://hdl.handle.net/2429/16514
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Poole

Project history as a group memory:  Learning from the past
Cubranic, Davor
DOI : 10.14288/1.0051638
URI : http://hdl.handle.net/2429/17301
Degree : Doctor of Philosophy - PhD
Graduation Date : 2005-05
Supervisors : Dr. Booth, Dr. Murphy

New members of software development teams must come up-to-speed on a large amount of information before becoming productive, even if they have previous software development experience. Often, this knowledge is gained through mentoring: an experienced colleague monitors the newcomer's progress on his or her first assigned tasks, and provides feedback and advice. The mentor is the person the newcomer turns to for help when stuck; these interactions are typically informal and lightweight, such as quick questions asked over the cubicle divider or at the water cooler. However, these light-weight channels are not always available in virtual teams, where the members of the team are not collocated. Moreover, workers are less likely to help their non-collocated colleagues, making it even harder for a newcomer to come up to speed on a project. The thesis of this dissertation is based on the idea that the collection of all artifacts created in the course of development of a software system implicitly forms a group memory—a repository of information that a work group can use to benefit from its past experience to respond more effectively to the present needs. I call this implicitly-formed group memory a project memory and make three claims: (1) that newcomer software developers can use information from the project memory about past modifications completed on the project to help them effectively perform modification tasks to the system; (2) that the project memory can be built largely automatically, requiring minimal adjustments in work practices of software developers; and (3) that the automatically-built group memory can recommend artifacts useful to the current modification task. To validate the claims of this thesis, I have developed a project memory model and associated tool, called Hipikat, that recommends relevant artifacts from the memory during a software modification task. This dissertation describes the memory model, the implementation of Hipikat, and its use in a series of case studies to validate the thesis claims.

The Ethnographically Informed Participatory Design of a PDA Application to Support Communication
Davies, Alison Rhian
DOI : 10.14288/1.0051557
URI : http://hdl.handle.net/2429/16317
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. McGrenere

Towards Adaptive Rendering of Smooth Primitives on GPUs
Fung, Jennifer
DOI : 10.14288/1.0051168
URI : http://hdl.handle.net/2429/16742
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Heidrich

Augmenting Reality, Naturally
Gordon (Skrypnyk), Iryna
DOI : 10.14288/1.0051554
URI : http://hdl.handle.net/2429/16178
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. Lowe

SCTP-Based Middleware for MPI
Kamal, Humaira
DOI : 10.14288/1.0051330
URI : http://hdl.handle.net/2429/16605
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Wagner

Communication in Intermittently-Connected Networks
Kempe, Gregory Jonathan
DOI : 10.14288/1.0051741
URI : http://hdl.handle.net/2429/16606
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Hutchinson

A Framework for Multiparty Communication Types
Keppitiyagama, Chamath Indika
DOI : 10.14288/1.0051286
URI : http://hdl.handle.net/2429/17099
Degree : Doctor of Philosophy - PhD
Graduation Date : 2005-11
Supervisor : Dr. Hutchinson

There are large number of communication paradigms such as multicast and anycast that are useful for distributed applications. The spectrum of such communication paradigms is larger than immediately apparent from the names used to identify these communication paradigms. None of these communication paradigms are universally available in the global Internet. To use these paradigms in applications programmers have to compose them using point-to-point communication or use third party modules that do so. Application level overlay networks have been used to implement some of these communication paradigms. These works indicate the vast design space behind the implementation of each of these multiparty communication paradigms over the wide area Internet. Application programmers should be able to make use of communication paradigms independent of their implementations and the implementors of communication paradigms should be able to explore the design space of implementing them. The lack of three components inhibits achieving these goals; a naming system that can accommodate current and future communication paradigms, a common application programmer's interface (API), and a system to deploy the implementations of communication paradigms. This dissertation describes a framework named MayaJala, based on the novel notion of multiparty communication types, that addresses these issues; multiparty communication types are the precisely defined counterparts of multiparty communication paradigms. MayaJala consists of two main components; a communication type system and a middleware system. The multiparty communication type system provides a mechanism to precisely identify communication paradigms. It also provides the ability to explore useful properties such as the equivalence of two communication types and conformance of one communication type to another. This allows applications to use different implementations of conforming communication types and not just different implementations of a single communication type. The multiparty communication type system also yields a common and simple interface sufficient for all the communication types. The middleware allows dynamic deployment of implementations transparent to the applications and also provides common functionality required by these implementations. The middleware provides support to implement communication types using application-level overlay networks. The middleware, together with the idea of multiparty communication types, facilitates the deployment of implementations of communication types without any coordination of the processes that participate in a session. This work shows that it is possible to provide a naming system, and a simple and common API for multiparty communication paradigms without restricting or standardizing the set of such communication paradigms. This is achieved through the notion of multiparty communication types. This work also shows that multiparty communication types can be deployed without any coordination from the processes participating in a session. MayaJala provides these facilities with a minimum overhead to the applications that use it.

Approximation Algorithms for Guarding 1.5 Dimensional Terrains
King, James Alexander
DOI : 10.14288/1.0051328
URI : http://hdl.handle.net/2429/16609
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Evans

Priority Progress Decoding
Kirsh, Lowell
DOI : 10.14288/1.0051175
URI : http://hdl.handle.net/2429/16944
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Krasic

Exorcising N^2 Stigmata in Sequential Monte Carlo
Klaas, Michael William
DOI : 10.14288/1.0051326
URI : http://hdl.handle.net/2429/16586
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. de Freitas

Empirically Evaluating Multiagent Reinforcement Learning Algorithms in Repeated Games
Lipson, Asher Grant
DOI : 10.14288/1.0051748
URI : http://hdl.handle.net/2429/16633
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisors : Dr. Leyton-Brown, Dr. de Freitas

BitVampire: A Cost-Effective Architecture for On-Demand Media Streaming in Heterogeneous P2P Networks
Liu, Xin
DOI : 10.14288/1.0051740
URI : http://hdl.handle.net/2429/16631
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Vuong

The Technological Assault on Anonymity
Lockton, Vance Michael
DOI : 10.14288/1.0051199
URI : http://hdl.handle.net/2429/16636
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Rosenberg

Proximity:  A Scalable P2P Architecture for Latency Sensitive Massively Multiplayer Online Games
Malik, Kamran Shaukat
DOI : 10.14288/1.0051311
URI : http://hdl.handle.net/2429/16641
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Vuong

Multiobjective Graph Clustering with Variable Neighbourhood Descent
Naverniouk, Igor
DOI : 10.14288/1.0051567
URI : http://hdl.handle.net/2429/16364
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. Hoos

A Representational Basis for Human-Computer Interaction
Po, Barry Alan
DOI : 10.14288/1.0052126
URI : http://hdl.handle.net/2429/17007
Degree : Doctor of Philosophy - PhD
Graduation Date : 2005-05
Supervisor : Dr. Booth

Mental representations form a useful theoretical framework for understanding the integration, separation and mediation of visual perception and motor action from a computational perspective. In the study of human-computer interaction (HCI), knowledge of mental representations could be used to improve the design and evaluation of graphical user interfaces (GUIs) and interactive systems. This thesis presents a representational approach to the study of user performance and shows how the use of mental representations for perception and action complements existing information processing frameworks in HCI. Three major representational theories are highlighted as evidence supporting this approach: (1) the phenomenon of stimulus-response compatibility is examined in relation to directional cursor cues for GUI interaction with mice, pointers, and pens; (2) the functional specialization of the upper and lower visual fields is explored with respect to mouse and touchscreen item selection; (3) the two-visual systems hypothesis is studied in the context of distal pointing and visual feedback for large-screen interaction. User interface design guidelines based on each of these representational themes are provided and the broader implications of a representational approach to HCI are discussed with reference to the design and evaluation of interfaces for time- and safety-critical systems, interaction with computer graphics, information visualization, and computer-supported cooperative work.

AlphaBetaService - An Asynchronous Parallel Tree Search Sercie for ChessGrid
Pramanik, Sukanta
DOI : 10.14288/1.0051308
URI : http://hdl.handle.net/2429/16669
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Vuong

From the Jungle to the Garden:  Growing Trees for Markov Chain Monte Carlo Inference in Undirected Graphical Models
Rivasseau, Jean-Noel
DOI : 10.14288/1.0051746
URI : http://hdl.handle.net/2429/16689
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. de Freitas

Detecting common secondary structure elements in RNA sequences
Shah, Sohrab P.
DOI : 10.14288/1.0051575
URI : http://hdl.handle.net/2429/16465
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. Condon

A Trust-based Model for Collaborative Intrusion Response
Singh, Kapil Kumar
DOI : 10.14288/1.0051329
URI : http://hdl.handle.net/2429/16690
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Hutchinson

Skrypnyk, Iryna – see Gordon, Iryna

Partitioned Rendering Infrastructure for Stable Accordion Navigation
Slack, James Gerald
DOI : 10.14288/1.0051327
URI : http://hdl.handle.net/2429/16474
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. Munzner

ODMAS: Object Discovery through Motion, Appearance and Shape
Southey, Tristram
DOI : 10.14288/1.0051717
URI : http://hdl.handle.net/2429/16723
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Little

Probabilistic Constraint Nets:  A Formal Famework for the Modeling and Verification of Probabilistic Hybrid Systems
St. Aubin, Robert Jr.
DOI : 10.14288/1.0051506
URI : http://hdl.handle.net/2429/17183
Degree : Doctor of Philosophy - PhD
Graduation Date : 2005-11
Supervisor : Dr. Mackworth

The development of autonomous agents, such as mobile robots or software agents has generated considerable research in recent years. Robotic systems, which are usually built from a mixture of continuous (analog) and discrete (digital) components, are often referred to as hybrid dynamical systems. The modeling and analysis of hybrid dynamical systems is becoming more and more important as such systems are now widely used to reason about complex physical systems. Ying Zhang and Alan Mackworth developed a semantic model for dynamical systems, called Constraint Nets (CN) [ZM95a]. CN introduces an abstraction and unitary framework to model hybrid systems. Furthermore, specification and verification methods were introduced for deterministic system. Traditional approaches to real-time hybrid systems usually define behaviors purely in terms of determinism or sometimes non-determinism. The CN framework was developed to model and verify deterministic systems, with the capability to model non-determinism. However, real-time dynamical systems very often behave unpredictably and thus exhibit (structured) uncertainty. It is therefore important to be able to model and analyze real-time probabilistic systems. Hence, a formal framework to model systems with unpredictable behaviors is essential. We extend the work previously done on Constraint Nets by developing a new framework that we call "Probabilistic Constraint Nets" (PCN). The PCN framework allows for the modeling and simulation of any dynamical system, whether it is deterministic, non-deterministic or probabilistic. We introduce formal syntax and semantics for the framework that ensure the correctness of the models. We also provide a graphical representation that simplifies the task of modeling complex systems. Moreover, we show that our framework is a generalization of many commonly used frameworks such as Markov processes and Markov Decision Processes (MDP). This allows the user to take advantage of a unified framework encompassing most popular modeling paradigms. We have also developed two specification languages (average-time timed V-automata and PATTL) along with verification algorithms that allow us specify some behavioural constraints on the system and enables us to proceed to on average and to probabilistic verification of these requirements. Finally, we also provide, for a subclass of PCN models algorithms for control synthesis. Moreover, we investigate the use of stochastic and robust control for handling the control synthesis task within PCN. With such control synthesis techniques, a designer can automatically construct an optimal controller for his system, hence greatly facilitating his task.

Efficient Content Locating in Dynamic Peer-to-Peer Networks
Wang, Jun
DOI : 10.14288/1.0051498
URI : http://hdl.handle.net/2429/16797
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Vuong

Template-Based Action Recognition:  Classifying Hockey Players' Movement
Wu, Xiaojing
DOI : 10.14288/1.0051499
URI : http://hdl.handle.net/2429/16909
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisors : Dr. Little, Dr. Lowe

Implementation and Analysis of Surfing Pipelines
Yang, Suwen
DOI : 10.14288/1.0051631
URI : http://hdl.handle.net/2429/16912
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Greenstreet

Using AspectJ to Build a Software Product Line for Mobile Devices
Young, Trevor
DOI : 10.14288/1.0051632
URI : http://hdl.handle.net/2429/16920
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Murphy

Efficient Algorithm for RNA Pseudoknotted Secondary Structure Prediction Given a Pseudoknot Free Structure
Zhao, Yinglei (Shelly)
DOI : 10.14288/1.0051636
URI : http://hdl.handle.net/2429/17000
Degree : Master of Science - MSc
Graduation Date : 2005-11
Supervisor : Dr. Condon

Query Answering Using Views for XML
Zhao, Zheng (Jessica)
DOI : 10.14288/1.0051566
URI : http://hdl.handle.net/2429/16451
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisor : Dr. Lakshmanan

Photometric Stereo vis Locality Sensitive High-Dimension Hashing
Zhong, Lin
DOI : 10.14288/1.0051569
URI : http://hdl.handle.net/2429/16440
Degree : Master of Science - MSc
Graduation Date : 2005-05
Supervisors : Dr. Woodham, Dr. Little