CS Theses & Dissertations 1998
For 1998 graduation dates (in alphabetical order by last name):
Conceptual Modules : Expressing Desired Structure for Software Reengineering
Baniassad, Elisa
URI : http://hdl.handle.net/2429/7611
Degree : Master of Science – MSc
Graduation Date : 1998-05
Supervisor : Dr. Murphy
MobileJ: System support for dynamic application partitioning in the mobile environment
Burian, Geoffrey Lloyd
URI : http://hdl.handle.net/2429/8010
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Hutchinson
Merging Multiple Light Fields
Chiu, ChangChing (Chris)
URI : http://hdl.handle.net/2429/8032
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Fournier
Design and Implementation of a System for Computer-Supported Distance Art Therapy
Cubranic, Davor
Master’s essay available in print : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=112567
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Booth
A Framework for Multi-Notation, Model-Oriented Requirements Analysis
Day, Nancy
URI : http://hdl.handle.net/2429/9479
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-11
Supervisor : Dr. Joyce
This dissertation addresses the problem of how to bring the benefits of formal analysis to the changing world of multi-notation requirements specifications. We show that direct use of the formal operational semantics for notations in higher-order logic produces an extensible, systematic and rigorous approach to solving this problem. Our approach achieves the desired qualities without requiring theorem proving infrastructure. We concentrate on model-oriented notations that use uninterpreted constants to filter non-essential details. A key contribution is the de-coupling of notation from analysis technique. We use type checking to regulate combinations of notations. Specifications are represented using embeddings that package the meaning of the notation with its syntax. We demonstrate our approach using combinations of the following three notations: statecharts, decision tables, and higher-order logic. We introduce a new automatic technique called symbolic functional evaluation (SFE) to evaluate semantic functions outside of a theorem proving environment. SFE produces the meaning of a specification. Direct use of the semantics ensures that the same meaning for a specification is used by all types of analysis. SFE extends the technique of lazy evaluation to handle uninterpreted constants. We focus on the binary decision diagram (BDD)-based analysis techniques of completeness and consistency checking of tables, simulation, and symbolic model checking. To bridge the gap between higher-order logic and automated analysis techniques, we create a toolkit of common techniques, such as Boolean abstraction. We show that information contained in the structure of a specification can be used to supplement BDD-based analysis approaches by producing a more precise abstraction of the specification. The partition of a numeric value specified by entries in a row of a table provides information on how to encode numeric values in a BDD. Our approach is demonstrated by the specification and analysis of two large real-world systems: a separation minima for aircraft and the Aeronautical Telecommunications Network (ATN). In the separation minima example, analysis discovered inconsistencies previously unknown to domain experts. In the ATN example, several errors in the formal-isation process were exposed. In both cases, we achieved the benefits of multiple notations for specification without sacrificing automation in analysis.
Statistical Admission Control for MPEG Streams with Non-overflow Guarantees
Dilek, Rita
URI : http://hdl.handle.net/2429/8393
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Ng
A Discipline of Specification-based test derivation
Donat, Michael
URI : http://hdl.handle.net/2429/8416
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-11
Supervisor : Dr. Joyce
System-level requirements-based testing is an important task in software development, providing evidence that each requirement has been satisfied. There are two major problems with how these tests are derived. First, the notion of coverage is subjective, i.e., there is a lack of objective definitions of coverage criteria. Second, there is a surprising lack of automation in deriving system-level requirements-based tests. Research into solutions for these problems has led to the formulation of the discipline of specification-based test derivation presented in this dissertation: This discipline, which is based on predicate logic, provides a scientific foundation for objective definitions of coverage criteria and algorithms for partially automating test derivation. This dissertation defines some fundamental coverage criteria as examples. A general test frame generation process illustrates a general application of the discipline to a broad range of formal specifications, which can include existential and universal quantification. A refinement of the process can be applied to system-level requirements-based testing. The discipline leverages work invested in compiling the requirements specification. In addition to partially automating the task of verifying that the requirements have been satisfied, the refined process automates the traceability of requirements to test descriptions. Other applications of the discipline of specification-based test derivation include requirements validation and objective measurements for requirements complexity. The discipline can also be used to predict the expected number of tests to be derived, which can then be used for process statistics. The uses of this discipline as a basis for repeatable processes, definitions, and measurements imply that it can form part of software development processes at Capability Maturity Model (CMM) Levels 2 through 5.
Enforcing Crash Failure Semantics in Distributed Systems with Fine-Grained Object Mobility
Duska, Brad
URI : http://hdl.handle.net/2429/8394
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Hutchinson
Flexible Policy Construction by Information Refinement
Horsch, Michael Christopher
URI : http://hdl.handle.net/2429/9484
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-11
Supervisor : Dr. Poole
Decision making under uncertainty addresses the problem of deciding which actions to take in the world, when there is uncertainty about the state of the world, and uncertainty as to the outcome of these actions. A rational approach to making good choices is the principle of maximum expected utility: the decision maker should act so as to maximize the expected benefits of the possible outcomes. The "textbook" approaches to decision analysis typically make the assumption that the computational costs involved are negligible. This assumption is not always appropriate. When computational costs cannot be ignored, a decision maker must be able to choose a trade-off between computational costs and object value. This thesis proposes an approach to decision making called information refinement. It is an iterative, heuristic process which a decision maker can use to build a policy. We present three algorithms which use information refinement to construct policies for decision problems expressed as influence diagrams. The algorithms are intended for situations in which computational costs are not negligible, and are designed to give the decision maker control of the trade-off involved in the decision making process. The first algorithm is an anytime algorithm for single stage decision problems. It constructs a policy by increasing the use of information available to the decision maker. The second algorithm applies the single stage algorithm to multistage decision problems using a fixed allocation of computational resources. The third algorithm is an anytime algorithm for multi-stage decision problems. We show empirically that these algorithms are able to make decisions with high expected value with small computational costs. We provide empirically evidence for our claims, by applying our algorithms to a large number of large decision problems.
Structuring Requirements Specifications
Khanna, Vittu
URI : http://hdl.handle.net/2429/8130
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Tsiknis
A Fault-Tolerant Collaborative Tools Development System
Ko, Miranda Wai Sum
URI : http://hdl.handle.net/2429/8141
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Hutchinson
Representations and Uses of Light Distribution Functions
Lalonde, Paul
URI : http://hdl.handle.net/2429/8633
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-05
Supervisor : Dr. Fournier
At their lowest level, all rendering algorithms depend on models of local illumination to define the interplay of light with the surfaces being rendered. These models depend both on the representations of light scattering at a surface due to reflection and to an equal extent on the representation of light sources and light fields. Both emission and reflection have in common that they describe how light leaves a surface as a function of direction. Reflection also depends on an incident light direction. Emission can depend on the position on the light source. We call the functions representing emission and reflection light distribution functions (LDF's). There are some difficulties to using measured light distribution functions. The data sets are very large - the size of the data grows with the fourth power of the sampling resolution. For example, a bidirectional reflectance distribution function (BRDF) sampled at five degrees angular resolution, which is arguably insufficient to capture highlights and other high frequency effects in the reflection, can easily require one and a half million samples. Once acquired this data requires some form of interpolation to use them. Any compression method used must be efficient, both in space and in the time required to evaluate the function at a point or over a range of points. This dissertation examines a wavelet representation of light distribution functions that addresses these issues. A data structure is presented that allows efficient reconstruction of LDFs for a given set of parameters, making the wavelet representation feasible for rendering tasks. Texture mapping methods that take advantage of our LDF representations are examined, as well as techniques for filtering LDFs, and methods for using wavelet compressed bidirection reflectance distribution functions (BRDFs) and light sources with Monte Carlo path tracing algorithms. The wavelet representation effectively compresses BRDF and emission data while inducing only a small error in the reconstructed signal. The representation can be used to evaluate efficiently some integrals that appear in shading computation which allows fast, accurate computation of local shading. The representation can be used to represent light fields and is used to reconstruct views of environments interactively from a precomputed set of views. The representation of the BRDF also allows the efficient generation of reflected directions for Monte Carlo ray tracing applications. The method can be integrated into many different global illumination algorithms, including ray tracers and wavelet radiosity systems.
Light-Driven Global Illumination with a Wavelet Representation of Light Transport
Lewis, Robert Ralph
URI : http://hdl.handle.net/2429/9529
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-11
Supervisor : Dr. Fournier
This thesis considers the problem of global illumination: the modelling of light as it travels through a scene interacting with the objects contained within the scene. Starting with a description of the problem and a discussion of previous work, we explore a new approach called light-driven global illumination that offers several advantages over its predecessors: a lower asymptotic complexity, a wider range of representable surface interaction phenomena, and an absence of the need for "meshing" - object surface subdivision needed primarily to represent shadows. Light-driven global illumination is intermediate between local and global illumination. Representing light with wavelet basis functions, we are able to treat both the interaction between two surfaces and the interaction of a surface with a radiation field in a source-to-destination model that applies to whole surfaces, not just small elements. We have found this "wavelet radiative transfer" to be a valid way to generate and store complex global light field data as four-dimensional textures for incorporation in local illumination solutions. Wavelets can considerably reduce the otherwise substantial storage and reconstruction problems associated with doing this. We include several examples of this. We also discuss plausible illumination models, which are required to make light-driven global illumination work theoretically. Like wavelet radiative transfer, these models have application in other areas of rendering besides global illumination. Finally, we develop the theory behind light-driven global illumination and apply it successfully to some simple examples. While we find the algorithm to be quite slow compared to other well-known rendering algorithms, we analyze what is needed to make it competitive. In conclusion, we find that representing light with wavelets has a set of advantages that are independent of the comparative inefficiency of the light-driven algorithm.
Synchronization in WebSmart Multimedia Authoring System
Li, Lan
URI : http://hdl.handle.net/2429/7932
Degree : Master of Science – MSc
Graduation Date : 1998-05
Supervisor : Dr. Neufeld
Retrieving Camera Parameters from Real Video Images
Li, Ning
URI : http://hdl.handle.net/2429/8219
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Fournier
Design, Implementation and Evaluation of a Variable bit-rate continuous media file server
Makaroff, Dwight
URI : http://hdl.handle.net/2429/9583
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-11
Supervisor : Dr. Hutchinson
A Continuous Media File Server (CMFS) is a computer system that stores and retrieves data that is intended to be presented to a client application continuously over time. The primary examples of this kind of data are audio and video, although any other type of time-dependent media can be included (closed-caption text, presentation slides, etc). The presentation of these media types must be performed in real-time and with a low latency for user satisfaction. This dissertation describes the design, implementation and performance analysis of a file server for variable-bit-rate (VBR) continuous media. A CMFS has been implemented on a variety of hardware platforms and tested within a high-speed network environment. The server is designed to be used in a heterogeneous environment and is linearly scalable. A significant aspect of the design of the system is the detailed consideration of the variable bit-rate profile of each data stream in performing admission control for the disk and for the network. The disk admission control algorithm simulates reading data blocks early and storing them in memory buffers at the server, achieving read-ahead and smoothing out peaks in the bandwidth requirements of individual streams. The network algorithm attempts to send data early and reserves bandwidth only for the time that it is required. The algorithms are sensitive to the variability in the bandwidth requirements, but can provide system utilization that approaches 100% of the disk bandwidth achievable for medium length video streams in the test hardware environment.
Extending Applications to the Network
Marwood, David
URI : http://hdl.handle.net/2429/8317
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Hutchinson
Efficient Data Mining of Constrained Association Rules
Pang, Chiu Yan (Alex)
URI : http://hdl.handle.net/2429/8197
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Ng
Implementation of Processor Farms on Myrinet Network Interface Cards
Parsa, Marjan
URI : http://hdl.handle.net/2429/8204
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Wagner
Service Migration in a Gigabit Network
Petrus, Margaret
URI : http://hdl.handle.net/2429/8212
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Hutchinson
Interactive Topological Drawing
Scharein, Robert
URI : http://hdl.handle.net/2429/8586
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-05
Supervisors : Dr. Booth, Dr. Little
The research presented here examines topological drawing, a new mode of constructing and interacting with mathematical objects in three-dimensional space. In topological drawing, issues such as adjacency and connectedness, which are topological in nature, take precedence over purely geometric issues. Because the domain of application is mathematics, topological drawing is also concerned with the correct representation and display of these objects on a computer. By correctness we mean that the essential topological features of objects are maintained during interaction. We have chosen to limit the scope of topological drawing to knot theory, a domain that consists essentially of one class of object (embedded circles in three-dimensional space) yet is rich enough to contain a wide variety of difficult problems of research interest. In knot theory, two embedded circles (knots) are considered equivalent if one may be smoothly deformed into the other without any cuts or self-intersections. This notion of equivalence may be thought of as the heart of knot theory. We present methods for the computer construction and interactive manipulation of a wide variety of knots. Many of these constructions would be difficult using standard computeraided drawing methods. Interactive techniques allow for knot simplification under topological constraints from complicated conformations to simpler embeddings. These methods have proven useful in the investigation of the knot equivalence problem. As a further test of its utility, topological drawing has been used for several knot theoretical applications. The first of these involves finding the stick-number of a knot (the fewest number of straight sticks needed to form the knot). A second application is to the relaxation of knots under a physically-based knot energy (the symmetric energy) that we find effectively simplifies knots to configurations approaching their "canonical form". Finally, our methods have proven useful in the visualization of a class of knots that arise in a study of three-manifold topology. These knots often have complex descriptions (for example, as a huge braid word), but may be simplified greatly through the use of interactive topological drawing. Here, an expert user relies on the visualization in order to steer the computation in a direction that will often significantly improve performance.
Interface Style, Flow, and Reflective Cognition: Issues in Designing Interactive Multimedia Mathematics Learning Environments for Children
Sedighian, Kamran
URI : http://hdl.handle.net/2429/8638
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-05
Supervisor : Dr. Klawe
Many children find mathematics boring, irrelevant to their lives, and difficult to understand. These feelings are influenced by many factors. One of these factors is the learning environments in which children encounter mathematics. The National Council of Teachers of Mathematics recommends the use of interactive computer software in children's mathematics education. However, due to unique cognitive and affective needs, designing interactive software for children is complex and challenging. There is need for systematic interdisciplinary research to provide developers of educational software with sound design principles. The purpose of this dissertation is to explore four main interrelated issues: 1. Designers of educational software often use 'Direct Manipulation' and 'Command-Based' interface styles. What role does the user interface play in multimedia mathematics learning environments? How do different interface styles influence learning? 2. Formal understanding of mathematical concepts is important. How should the user interface be designed to support children's learning of explicit, formal mathematical concepts? 3. Reflection is crucial to deep understanding of mathematical concepts. How should a learning environment in general, and the interface in particular, be designed to afford 'reflective cognition'? 4. Designers know little about how to structure tasks to promote the optimal psychological experience of 'flow'. How should a multimedia learning environment be structured to be conducive to experiencing 'flow' in learning? What are some design elements that can make children's learning of mathematics fun and enjoyable? There are few, or no guidelines, for what constitutes effective human-computer interfaces for educational purposes. Due to a lack of proper interface design guidelines, designers of educational software for children often use the interaction styles that were originally designed for productivity tools. Recently, the casual use of such interaction styles for educational purposes has been questioned. This dissertation closely examines the issue of interface design for multimedia mathematics learning environments for children and makes recommendations for a new conception of interface manipulation styles resulting in more effective educational user interfaces. To structure a mathematics activity so that it combines the two elements of fun and formalism and affords reflective cognition is not an easy task. This dissertation examines a model of structuring mathematical activities for children to support their learning. It also examines a number of design features that help make the learning activity more enjoyable. This dissertation makes recommendations on how to design multimedia mathematics learning environments to address children's affective, cognitive, and pedagogical needs. Moreover, this research contributes to an increased understanding of how to design better game-based educational software. A few of the findings of this research are: 1. Interface design in educational software plays a crucial role in how learners interact with the educational content, and consequently how they acquire knowledge and what knowledge they acquire. The results showed significant achievement differences among students who used different interface styles. Interface techniques such as 'scaffolding' and gradual removal of visual feedback can promote reflective cognition and improve learning. 2. Direct manipulation graphical interfaces should be used with care in the context of interactive multimedia mathematics learning environments. The conventional interface design guideline calling for easier interaction and exertion of minimal cognitive load does not necessarily apply to educational environments. 3. By carefully taking into account children's cognitive and affective needs, the design can help children enjoy learning mathematics. 4. Inclusion of background music and visual aesthetics can make a learning activity more enjoyable.
Terrain Surface Simplification based on Surface Features
Shi, Ping
URI : http://hdl.handle.net/2429/8407
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Little
The Possibilities and Limitations of Heterogeneous Process Migration
Smith, Peter
URI : http://hdl.handle.net/2429/8644
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-05
Supervisor : Dr. Hutchinson
Heterogeneous Process Migration is a technique that allows an active program to move between computers of differing architectures. While the program is executing, a migration tool will pause the program, locate the data values within the program's memory, convert them to a suitable format for the destination machine, then reconstruct the program on the destination machine so that it will continue executing correctly. Although a small number of heterogeneous migration mechanisms have been proposed, few of them have been constructed, and none have yet resulted in a mature and efficient implementation. The Tui system has been constructed to provide an efficient migration tool for use on four common architectures within the Unix environment. Implementation lessons were learned while optimizing the Tui system to gain performance. Tui has been used to derive a definition of migratibility. All other migration implementations have assumed that the program must be written in a type-safe language, or in a type-safe subset of a language. Since Tui has been designed to support heterogeneous migration of common languages that are non-type-safe, a survey of non-migratible language features has been undertaken. From this study, a definition for migratibility has been created, a framework for designing a migration tool has been given, and a comparison between migratibility and type-safety has shown that the two concepts are similar, yet different.
An Automatic Collision Response Algorithm
Struben, Sonja Wally
URI : http://hdl.handle.net/2429/8274
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Forsey
Interactive Manipulation of Virtual Folded Paper
Thiel, Joanne Marie
URI : http://hdl.handle.net/2429/8281
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisors : Dr. Klawe, Dr. Fournier
Interpreting Severe Occlusions in Region-Based Stereo Vision
Tucakov, Vladimir
URI : http://hdl.handle.net/2429/7665
Degree : Master of Science – MSc
Graduation Date : 1998-05
Supervisor : Dr. Mackworth
A Dynamically Reconfigurable and Extensible Operating System
Veitch, Alistair
URI : http://hdl.handle.net/2429/9598
Degree : Doctor of Philosophy – PhD
Graduation Date : 1998-11
Supervisor : Dr. Hutchinson
Operating systems are constantly getting more complex in the functionality they support, due to the increasing demands made by modem hardware and software innovations. Basingjhe kernel design on co-operating and modular services incorportating a flexible communications infrastructure with run-time binding makes the operating system dynamically configurable and extensible. These features aid in the management of system complexity, while also resulting in several software engineering and performance benefits. Configurability gives the operating system designer and implementor the freedom to build a large number of components, which can be composed into different configurations depending upon the final system requirements. System components can be built and debugged in a user address space, and then transparently migrated into the kernel address space for performance once they have been demonstrated correct. This removes one of the major obstacles to developing kernel services, that of the necessity to reboot the system after each change to the service code. The system administrator can also reconfigure the system, providing similar advantages, and allowing dynamic system upgrades to be made, reducing system downtime. Extensibility lets new functionality be integrated into the operating system. This can be done on an application specific basis. This enables the development of in-kemel applications in cases where high performance is required, such as for dedicated file servers. It is also possible for applications to interpose specialised kernel services, allowing them to dramatically increase their performance and aggregate system throughput when the default system policies are ill-matched to their behaviour. The Kea operating system has been designed and implemented to be dynamically configurable and extensible. The design of the system features that make these features possible are described. Experimental results are shown that demonstrate that Kea offers comparable performance to a traditional operating system on the same hardware, and that extensibility can be used to increase performance for selected applications.
Proactive Congestion Control at Internet Routers
Wang, Charles Bin
Master’s essay available in print : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=112568
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Neufeld
Safety Verification Conditions for Software-Intensive Critical Systems
Wong, Ken Chee
URI : http://hdl.handle.net/2429/8371
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Joyce
System Architecture of WebSmart - A Web-Oriented Synchronized Multimedia Authoring System
Xu, Yue (Debbie)
URI : http://hdl.handle.net/2429/7973
Degree : Master of Science – MSc
Graduation Date : 1998-05
Supervisor : Dr. Neufeld
A constraint-based approach to real-time cooperative multiagent systems: A soccer-playing robot team
Zhang, Yu
URI : http://hdl.handle.net/2429/8385
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Mackworth
Wavelet Radiosity in Computer Graphics
Ziegler, Philipp
URI : http://hdl.handle.net/2429/8421
Degree : Master of Science – MSc
Graduation Date : 1998-11
Supervisor : Dr. Ascher