CS Theses & Dissertations 2003

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

Animating and lighting grass in real-time
Bakay, Brook Maurice
URI : http://hdl.handle.net/2429/14034
Degree : Master of Science - MSc
Graduation Date : 2003-05

Algorithms for predicting the Secondary Structure of pairs and combinatorial sets of nucleic acid strands
Andronescu, Mirela
URI : http://hdl.handle.net/2429/14551
Degree : Master of Science - MSc
Graduation Date : 2003-11

All the distant horizon edgest of a terrain
Archambault, Daniel William
URI : http://hdl.handle.net/2429/14403
Degree : Master of Science - MSc
Graduation Date : 2003-11

Design pattern rationale graphs: linking design to source
Baniassad, Elisa Ladan Anahita
URI : http://hdl.handle.net/2429/14804
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-05

As source code evolves, the reasoning behind certain design decisions is lost, often leading to violations of design goals during program maintenance. This kind of code decay is often caused by changes made by developers who are not adequately aware of the rationale behind the source code. Becoming aware of rationale is difficult for many reasons, including the mismatch between design and source code. The thesis of this research is that a mechanism for tracing design goals through existing documentation to source would enable software developers to have more complete knowledge of design goals relevant to a system, and more confidence in terms of how design goals relate to the source. The technique should be applicable within the context of one software evolution task. To validate the claims of this thesis, we have developed the Design Pattern Rationale Graph (DPRG) approach and associated tool. This dissertation describes this mechanism, and its use in the validation of the thesis claims. A DPRG is a graph formed from the text of design pattern documentation that is linked to a code base. The DPRG allows developers to view design pattern information related to design goals separately, and trace those goals through to their corresponding locations in a code base. The DPRG approach is lightweight: The time and effort required to apply the approach fits within the context of a single task. We demonstrate the validity of the thesis claims by applying the DPRG in several case studies and one experiment. These studies address each claim separately, and do so on a wide range of systems and tasks.

On-line EM and quasi-Bayes or: how I learned to story worry and love stochastic approximation
Bao, Kejie (Betty)
URI : http://hdl.handle.net/2429/14569
Degree : Master of Science - MSc
Graduation Date : 2003-11

Growth Processes on formulas and reversible circuits
Brodsky, Alex
URI : http://hdl.handle.net/2429/15050
Degree : Doctor of Philosophy – PhD
Graduation Date : 2003-11

Among their many uses, growth processes have been used for constructing reliable networks from unreliable components (Moore and Shannon, 1956) and deriving complexity bounds of various families of functions (Valiant, 1984). Hence, analyzing such processes is an important and challenging problem. In this thesis we parameterize a growth process by its initial conditions and characterize it by the existence and shape of a limiting probability distribution that describes the likelihood of it realizing a particular Boolean function. We identify the limiting distributions of several classes of growth processes on formulas, and derive conditions under which results such as Valiant's hold. We consider growth processes that use linear, self-dual, and monotone connectives, completely characterizing those processes that use linear or monotone connectives. In the latter case, we derive a novel technique that combines spectral analysis (Savicky, 1990) with probabilistic arguments; the technique is also applicable to growth processes that use other connectives. Our characterizations also yields bounds on the convergence of these growth processes. Unfortunately, a comparable definition and characterization of growth processes on general circuits is impractical due to the dependencies between the probabilities associated with various circuit components. However, reversible circuits (Toffoli, 1980) are inherently more structured than general circuits. To study growth processes beyond the formula setting, we propose and characterize growth processes on reversible circuits. Intriguingly, aspects of the characterizations that proved difficult in the former setting—such as proving that the limiting distribution is uniform—turn out to be relatively easy in the latter. In fact, the limiting distribution of a growth process on reversible circuits is characterized completely by its support—the set of functions that the process can generate. Consequently, we also provide bounds on the convergence of these growth processes. Finally, the regular structure of reversible circuits provides ample motivation for considering the reversible circuit complexity of finite Boolean functions—an important issue, since the precursor to such applications as quantum computation is reversible computation. We derive relationships between reversible circuits and other models of computation such as permutation branching programs (Barrington, 1985), based on a new measure that we call bandwidth. By leveraging these relationships, we exhibit a natural gap between two families of reversible circuits that correspond to width-4 and width-5 permutation branching programs. Based on the same measure, we define a hierarchy of families of reversible circuits that corresponds to the SC class hierarchy—a natural circuit-based definition of the class SC. Lastly, we provide constructions for several common Boolean functions and derive sufficient conditions under which a Boolean function has a polynomial-size realization.

RACIER - A hierarchical approach for content internetworking through interdomain routing
Cai, Xiaojuan
URI : http://hdl.handle.net/2429/13944
Degree : Master of Science - MSc
Graduation Date : 2002-11

Unsupervised Statistical Models for General Object Recognition
Carbonetto, Peter Salvatore
URI : http://hdl.handle.net/2429/14543
Degree : Master of Science - MSc
Graduation Date : 2003-11

Predicting users' next access to the web server
Chakoula, Oxana
URI : http://hdl.handle.net/2429/13948
Degree : Master of Science - MSc
Graduation Date : 2003-05

Efficient self-timed interfaces for crossing clock domains
Chakraborty, Ajanta
URI : http://hdl.handle.net/2429/14589
Degree : Master of Science - MSc
Graduation Date : 2003-11

Comparative sequence analysis Prediction of consensus Xist RNA secondary structure
Chan, Viann
URI : http://hdl.handle.net/2429/14473
Degree : Master of Science - MSc
Graduation Date : 2003-11

Classifying Inter-Realm Communication
Chapman, Ryan Doneric
URI : http://hdl.handle.net/2429/16769
Degree : Master of Science - MSc
Graduation Date : 2003-05

1,001,001 Faces: A Configural Face Navigation interface
Chen, Tzu-Pei Grace
URI : http://hdl.handle.net/2429/14355
Degree : Master of Science - MSc
Graduation Date : 2003-11

Improving evolvability of operating systems with AspectC
Coady, Monica (Yvonne)
URI : http://hdl.handle.net/2429/15090
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-11

Operating system code is complex. But, while substantial complexity is inherent to this domain, other complexity is caused by modularity problems. The implementation of certain key system concerns seems to defy traditional modular boundaries and impede evolution. From OS/360 to Windows NT, systems suffer from unintentional interactions between modules [Lehman and Belady 1985] and require developers to be intimately familiar with implicit patterns of interaction between subsystems [Vogels 1999]. The thesis of this work is that aspect-oriented programming (AOP) can be used to improve evolution in operating system code by improving modularity. Specifically, AOP can alleviate modularity problems associated with concerns that are inherently crosscutting - no single modular decomposition can localize both the crosscutting concern and the concerns it crosscuts. Better modularization of crosscutting concerns requires that their implementation be localized, their interaction with the parts of the system they crosscut be explicit, and their internal structure be clear. By accomplishing these three things, AOP can provide better structural support for evolution. The first part of the thesis provides a case study comparing modularity involving three crosscutting concerns in the original versus aspect-oriented implementation within the FreeBSD operating system [Lehey 1999]. This comparison highlights specific improvements in modularity of both the crosscutting concerns and the concerns that are crosscut, or interacting concerns, in the AOP implementation. The second part of the thesis surveys evolutionary changes the three crosscutting concerns underwent between releases 2.2 (1997), 3.3 (1999) and 4.4 (2001) of FreeBSD, and identifies some of the specific impediments the original implementation poses with respect to evolution. A case study of the impact of these same evolutionary changes on the aspect-oriented implementation highlights improvements in locality of change afforded by the AOP implementation, and the ways in which improvements in modularity persist across the versions. The final part of the thesis presents inferences and generalizations based on the results of the case studies. We infer from the case studies that AOP can be used to improve evolvability of the three crosscutting concerns and their interacting concerns in three versions of FreeBSD, without harming non-interacting concerns. We then generalize these modularity benefits to more concerns, more systems, and more versions, and infer support for our main claim - that aspect-oriented programming can be used to improve evolvability of operating system code by providing better modularity of crosscutting concerns and their interacting concerns, without harming non-interacting concerns.

Automatic Formal Verification for scheduled VLIW code
Feng, Xiushan (Shaun)
URI : http://hdl.handle.net/2429/13896
Degree : Master of Science - MSc
Graduation Date : 2003-05

A hybrid hierarchical request-routing architecture for content internetworking
Gan, Ming (Jennifer)
URI : http://hdl.handle.net/2429/13595
Degree : Master of Science - MSc
Graduation Date : 2003-05

Using MPLS to Support Traffic Engineering and IP QoS
Gao, Fang
Master’s essay available in print : http://bibrrs.library.ubc.ca:7108/vwebv/holdingsInfo?bibId=136420
Degree : Master of Science - MSc
Graduation Date : 2003-05

Adaptive and interactive methods for gathering user preferences in educational games
Gauthier, James
URI : http://hdl.handle.net/2429/14579
Degree : Master of Science - MSc
Graduation Date : 2003-11

Copy-on-write in Mammoth
Gong, Shihao
URI : http://hdl.handle.net/2429/13958
Degree : Master of Science - MSc
Graduation Date : 2003-05

Consistency in Optimistic Replication Systems
Ho, Sunny Ming-Cheung
Master’s essay available in print : http://bibrrs.library.ubc.ca:7108/vwebv/holdingsInfo?bibId=137827
Degree : Master of Science - MSc
Graduation Date : 2003-11

CInDeR Collision and interference detection in real time using graphcis hardware
Knott, David
URI : http://hdl.handle.net/2429/14572
Degree : Master of Science - MSc
Graduation Date : 2003-11

Inference of transcriptional regulation network with gene expression data
Kwon, Tae-Jun Andrew
URI : http://hdl.handle.net/2429/14127
Degree : Master of Science - MSc
Graduation Date : 2003-05

Efficient and Effective Exploratory Mining of Constrained Frequent Sets
Leung, Kai Sang
URI : http://hdl.handle.net/2429/14693
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-05

Data mining refers to the search for implicit, previously unknown, and potentially useful relationships or patterns (such as frequent sets) that might be embedded in data. Most of the existing data mining algorithms do not allow users to express the patterns to be mined according to their intentions, via the use of constraints. Consequently, these unconstrained mining algorithms can yield numerous patterns that are not interesting to users. Moreover, data mining is supposed to be a human-centered and exploratory process, not a one-shot exercise. In this context, we are working on a project with the overall objective of developing a practical human-centered computing environment for the efficient and effective exploratory mining of constrained frequent sets. One critical component of such an environment is the support for the dynamic mining of constrained frequent sets. Constraints enable users to impose a certain focus on the mining process. The term "dynamic" means that, in the middle of the computation, users are able to (i) change (such as tighten or relax) the constraints, and/or (ii) change the support threshold. This permits users to have a decisive influence on subsequent computations. In real-life situations, the available buffer space may be quite limited, thus adding another complication to the problem. In this thesis, we develop an algorithm, called DCF, for Dynamic Constrained Frequent-set computation. This algorithm is enhanced with a few optimizations, exploiting a light-weight structure called a segment support map. Such a structure enables DCF to (i) obtain sharper bounds on the support of patterns (or frequent sets of items), and (ii) better exploit properties of constraints. Furthermore, when handling dynamic changes to constraints, DCF relies on the concept of a delta member generating function, which exploits a special class of constraints—namely, succinct constraints—to generate precisely the sets of items that satisfy the new but not the old constraints. Our experimental results show the effectiveness of these enhancements. Lastly, to show that the exploitation of succinct constraints is not confined to DCF, we develop another algorithm that also supports the dynamic mining of constrained frequent sets, albeit in a tree-based framework.

ECSP: an efficient clustered super-peer architecture for P2P networks
Li, Juan
URI : http://hdl.handle.net/2429/14530
Degree : Master of Science - MSc
Graduation Date : 2003-11

A hybrid Algorithmn for terrain simplification
Li, Xuanying
URI : http://hdl.handle.net/2429/14539
Degree : Master of Science - MSc
Graduation Date : 2003-05

An Interactive 3D Geometric Model Acquisition and Registration System
Liu, Yushuang
URI : http://hdl.handle.net/2429/14176
Degree : Master of Science - MSc
Graduation Date : 2003-05

Iris: an intergrated circuit layout automatic generator
Lu, Yang
URI : http://hdl.handle.net/2429/14573
Degree : Master of Science - MSc
Graduation Date : 2003-11

Probabilistic testing of Boolean functions or, How to test locally ofr a global property
Majewski, Krzysztof Michał (Chris)
URI : http://hdl.handle.net/2429/14328
Degree : Master of Science - MSc
Graduation Date : 2003-11

A pipelined framework for multi-scale image comparison
Martindale, David Morrison
URI : http://hdl.handle.net/2429/14881
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-05

In this thesis we present a pipelined framework and a family of algorithms for determining meaningful differences between two images. The pipeline is structured in a way that makes it easy to use only a portion of the pipeline when that is appropriate, and any module in the pipeline can be replaced in its entirety by a new module that uses a different algorithm, while requiring minimal or no changes to other modules. Many pieces of the pipeline can be used individually. Three key design goals were to facilitate comparison of real images to computer-generated images, to take into account the sensitivity of the human visual system, and to accept pairs of images with arbitrary size differences and moderate misalignment in translation, rotation, and field of view. Most existing approaches fail badly at this task, requiring the two images to be of the same size and perfectly aligned with each other. The pipeline automatically aligns the two images as well as it can in the first four of its five phases. Images are first separated into octave-spaced bands of spatial frequencies, using the wavelet-based technique of Mallat and Zhong to find edges at multiple scales in each of the images. These edges are then matched using a graph-theoretic matching technique in the second phase, a least-squares fit is found for the alignment in the third phase, and the resulting transformation is applied using appropriate resampling in the fourth phase. The final phase of the pipeline computes difference measures for each spatial frequency band and three colour components, weighted according to the human contrast sensitivity function. The same Mallat-Zhong wavelet transform used for edge detection is used as the multi-band filter during comparison. We describe the pipeline and each component in detail, and discuss alternate approaches for each of the phases and generalizations of the framework. The flexibility of the framework is demonstrated by examples. We show how to restructure the data flow to implement an improved iterative multiscale alignment technique, and we analyze a Laplacian-based edge detector that could be used instead of wavelets.

Situated Observation and participation in multiple-agent systems
Montgomery, Jeffrey
URI : http://hdl.handle.net/2429/14611
Degree : Master of Science - MSc
Graduation Date : 2003-11

Automatic acquisition of motion trajectories:  tracking hockey player
Okuma, Kenji
URI : http://hdl.handle.net/2429/14151
Degree : Master of Science - MSc
Graduation Date : 2003-05

High-Level Specification and Automatic Generation of IP Interface Monitors
Oliveira, Marcio Teixeira
URI : http://hdl.handle.net/2429/14580
Degree : Master of Science - MSc
Graduation Date : 2003-11

Network Virtual Memory
Ong, Joon Suan
URI : http://hdl.handle.net/2429/14874
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-11

User-mode access, zero-copy transfer, and sender-managed communication have emerged as essential for improving communication performance in workstation and PC clusters. The goal of these techniques is to provide application-level DAAA to remote memory. Achieving this goal is difficult, however, because the network interface accesses physical rather than virtual memory. As a result, previous systems have confined source and destination data to pages in pinned physical memory. Unfortunately, this approach increases application complexity and reduces memory-management effectiveness. This thesis describes the design and implementation of NetVM, which is a network interface that supports user-mode access, zero-copy transfer and sender-managed communication without pinning source or destination memory. To do this, the network interface maintains a shadow page table, which the host operating system updates whenever it maps or unmaps a page in host memory. The network interface uses this table to briefly lock and translate the virtual address of a page when it accesses that page for DAAA transfer. The operating system is prevented from replacing a page in the short interval that the network interface has locked that page. If a destination page is not resident in memory, the network interface redirects the data to an intermediate system buffer, which the operating system uses to complete the transfer with a single host-to-host memory copy after fetching in the required page. A credit-based flow-control scheme prevents the system buffer from overflowing. Application-level DAAA transfers only data. To support control transfers, NetVM implements a counter-based notification mechanism for applications to issue and detect notifications. The sending application increments an event counter by specifying its identifier in an RDAAA write operation. The receiving application detects this event by busy waiting, block waiting or triggering a user-defined handler whenever the notifying write completes. This range of detection mechanisms allows the application to decide appropriate tradeoffs between reducing signaling latency and reducing processor overhead. NetVM enforces ordered notifications over an out-oforder delivery network by using a sequence window. NetVM supports efficient mutual-exclusion, wait-queue and semaphore synchronization implementations. It augments the network interface with atomic operation primitives, which have low overhead, to provide MCS-lock-inspired scalable and efficient high-level synchronization for applications. As a result, these operations require lower latency and fewer network transactions to complete compared with the traditional implementations. The NetVM prototype is implemented in firmware for the Myrinet LANai-9.2 and integrated with the FreeBSD 4.6 virtual memory system. NetVM's memory-management overhead is low; it adds only less than 5.0% write latency compared to a static pinning approach and has a lower pinning cost compared to a dynamic pinning approach that has up to 94.5% hit rate in the pinnedpage cache. Minimum write latency is 5.56us and maximum throughput is 155.46MB/s, which is 97.2% of the link bandwidth. Transferring control through notification adds between 2.96us and 17.49us to the write operation, depending on the detection mechanism used. Compared to standard low-level atomic operations, NetVM adds only up to 18.2% and 12.6% to application latencies for high-level wait-queue and counting-semaphore operations respectively.

Multilevel Debugging of Parallel Message Passing Programs
Pedersen, Jan Baekgaard
URI : http://hdl.handle.net/2429/15026
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-11

"Errare humanum est" - To err is human (Hieronymus, Epistle 57, 12); this fact has been known throughout time, and inevitably this means that humans writing computer programs are bound to introduce errors. With computers operating in Frankenstein's Igor mode, 'Your wish is my command', executing instructions without questioning their validity, errors introduced by humans are carried out. When adding parallel programming with message passing an error in one process can spread like a virus through message passing to other processes. Much research has been done on debugging sequential programs, and most of these theories and results apply directly to parallel programs, but the set of potential errors dramatically increases in size when introducing parallelism and message passing. Not only can one process fail, but sets of processes can deadlock, computational errors can be propagated from process to process, thus infecting otherwise correct programs. Correct programs can stop working because of the underlying implementation of the message passing system. We propose a framework for debugging parallel message passing programs: a multilevel approach that divides errors into separate groups at various levels from the well known sequential errors, such as stray pointers and array out of bound, to deadlock caused by incorrect message passing code, protocol errors and buffer allocation problems. We show the validity of this approach by developing new debugging techniques and analyses, and by implementing these in Millipede, a prototype multilevel debugger written for C programs that use the PVM message passing system.

Accelerating Reinforcement Learning through Imitation
Price, Robert Roy
URI : http://hdl.handle.net/2429/14937
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-11

Imitation can be viewed as a means of enhancing learning in multiagent environments. It augments an agent's ability to learn useful behaviours by making intelligent use of the knowledge implicit in behaviors demonstrated by cooperative teachers or other more experienced agents. Using reinforcement learning theory, we construct a new, formal framework for imitation that permits agents to combine prior knowledge, learned knowledge and knowledge extracted from observations of other agents. This framework, which we call implicit imitation, uses observations of other agents to provide an observer agent with information about its action capabilities in unexperienced situations. Efficient algorithms are derived from this framework for agents with both similar and dissimilar action capabilities and a series of experiments demonstrate that implicit imitation can dramatically accelerate reinforcement learning in certain cases. Further experiments demonstrate that the framework can handle transfer between agents with different reward structures, learning from multiple mentors, and selecting relevant portions of examples. A Bayesian version of implicit imitation is then derived and several experiments are used to illustrate how it smoothly integrates model extraction with prior knowledge and optimal exploration. Initial work is also presented to illustrate how extensions to implicit imitation can be derived for continuous domains, partially observable environments and multi-agent Markov games. The derivation of algorithms and experimental results are supplemented with an analysis of relevant domain features for imitating agents and some performance metrics for predicting imitation gains are suggested.

Cloth Parameters and Motion Capture
Pritchard, David
URI : http://hdl.handle.net/2429/14517
Degree : Master of Science - MSc
Graduation Date : 2003-11

Designing Game-Based Interactive Mathematics Learning Environments for Children
Song, Zhenyu (Gene)
URI : http://hdl.handle.net/2429/13975
Degree : Master of Science - MSc
Graduation Date : 2003-05

Motion Doodles : A Sketch-based Interface for Character Animation
Thorne, Matthew Edward
URI : http://hdl.handle.net/2429/14521
Degree : Master of Science - MSc
Graduation Date : 2003-11

Essential Software Structure through Implicit Context
Walker, Robert
URI : http://hdl.handle.net/2429/14909
Degree : Doctor of Philosophy - PhD
Graduation Date : 2003-05

Software reuse and evolution are problematic. Modules tend to express a great deal of knowledge about the external modules, large-scale structure, and behaviour of the systems in which they reside. As a result, the reusability of individual modules is decreased as they are too dependent on other modules. Likewise, the evolvability of systems is decreased as they are too dependent on the details of individual modules. However, we must have some dependences between our modules, or they would not be able to operate together. Not all dependences are equally bad, then. Each module can be seen to have a minimal core, an essential structure, beyond which it makes no sense to reduce. This essential structure describes the basic responsibilities of that module, and its expectations of the responsibilities of external modules. The thesis of this dissertation is that expressing the essential structure of our software modules, through the use of implicit context, makes those modules easier to reuse and the systems containing those modules easier to evolve. Implicit context revolves around the notion that we must abandon the need for all modules to be defined with respect to an absolute frame of reference. Instead, modules can be defined relative to a reference frame of convenience. In order for modules to work together, the inconsistencies in their independent world views must be reconciled when they attempt to communicate. Implicit context provides the novel mechanism of contextual dispatch to perform this reconciliation. When any communication passes into or out of a module, that communication may be rerouted, altered, replaced, or discarded altogether, as the situation dictates. This translation process sometimes requires access to information about the communication history of the system; objects previously passed can be retrieved, or the appropriate recipient of a message can be determined. The dissertation describes a prototype tool that supports the application of implicit context to Java source code. The thesis is validated by applying this tool in two case studies: comparing the evolution of an implicit context-based implementation of an FTP server to an object-oriented implementation; and reusing the Outline View of the Eclipse integrated development environment in a different application, even though the Outline View was not designed for such reuse.

Multi-Scale Summaries of Temporal Trajectories
Yang, Ruiyao
URI : http://hdl.handle.net/2429/13996
Degree : Master of Science - MSc
Graduation Date : 2003-05

Predicting source code changes by mining revision history
Ying, Annie Tsui Tsui
URI : http://hdl.handle.net/2429/14491
Degree : Master of Science - MSc
Graduation Date : 2003-11

Direct surface extraction from 3D freehand ultrasound images
Zhang, Youwei
URI : http://hdl.handle.net/2429/14294
Degree : Master of Science - MSc
Graduation Date : 2003-11

Adaptive support for student learning in educational games
Zhao, Xiaohong
URI : http://hdl.handle.net/2429/13648
Degree : Master of Science - MSc
Graduation Date : 2003-05

Quotient Cube and Qc-Tree:  Efficient Summarizations for Semantic OLAP
Zhao, Yan (Maryann)
URI : http://hdl.handle.net/2429/14509
Degree : Master of Science - MSc
Graduation Date : 2003-11

Generalized MDL approach for data summarization
Zhou, Xiaodong
URI : http://hdl.handle.net/2429/13859
Degree : Master of Science - MSc
Graduation Date : 2003-05

An affective student model to assess emotions in an educational game
Zhou, Xiaoming
URI : http://hdl.handle.net/2429/13878
Degree : Master of Science - MSc
Graduation Date : 2003-05



Find us on Twitter

a place of mind, The University of British Columbia

 

ICICS/CS Building 201-2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
Tel: 604-822-3061 | Fax: 604-822-5485
General: help@cs.ubc.ca
Undergrad program: undergrad-info@cs.ubc.ca
Graduate program: grad-info@cs.ubc.ca

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia