Science
Permanent URI for this community
Researchers in the Faculty of Science are involved in an impressive variety of fields – from astrophysics to zoology, nanotechnology to virtual reality, metabolomics to mathematics and much more!
In all cases, our faculty researchers, post-doctoral fellows, and graduate and undergraduate students live up to the highest standards in their disciplines, seeking to expand human knowledge through curiosity, innovation, and discovery.
Browse
Browsing Science by Department "Computer Science"
Now showing 1 - 20 of 1191
Results Per Page
Sort Options
Item Open Access 14th Meeting of the Canadian Number Theory Association(2016-06)The Canadian Number Theory Association (CNTA) was founded in 1987 at the International Number Theory Conference at Laval University (Quebec), for the purpose of enhancing and promoting learning and research in number theory in Canada and beyond. To advance these goals, the CNTA organizes bi-annual conferences that showcase new research in number theory, with the aim of exposing Canadian and international students and researchers to the latest developments in the field. The CNTA meetings are among the largest number theory conferences world-wide. The previous CNTA conferences were held in Banff (1988), Vancouver (1989), Kingston (1991), Halifax (1994), Ottawa (1996), Winnipeg (1999), Montreal (2002), Toronto (2004), Vancouver (2006), Waterloo (2008), Wolfville (2010), Lethbridge (2012) and Ottawa (2014). 2016 returns CNTA — almost — to its 1988 birthplace of Banff. In the year of its 50th birthday, the University of Calgary in Calgary (Alberta, Canada) is pleased to host the 14th meeting of the CNTA. A highlight of this event is a special session honouring our distinguished colleague Richard Guy, in celebration of his 100th birthday which will take place on September 30, 2016. An exceptional scholar and Professor Emeritus at the University of Calgary, Richard’s numerous and outstanding contributions to number theory have had a lasting impact on the field, and his collection of Unsolved Problems in Number Theory in particular has influenced research articles and inspired graduate theses for decades. The CNTA-XIV Organizers wish all conference participants a fruitful and enjoyable time in Calgary!Item Open Access The 2DR-tree: A 2-dimensional spatial access method(2004-05-04) Osborn, Wendy; Barker, KenThis paper presents the 2DR-tree, a novel approach for accessing spatial data. The 2DR-tree uses nodes that are the same dimensionality as the data space. Therefore, all relationships between objects are preserved and different searching strategies such as binary and greedy are supported. The insertion and deletion strategies both use a binary partition of a node to insert an object or update a non-leaf minimum bounding rectangle. A validity test ensures that each node involved in an insertion or deletion preserves the spatial relationships among its objects. A performance evaluation shows the advantages of the 2DR-tree and identifies issues for future consideration.Item Open Access √3 Multiresolution by Local Least Squares: The Diagrammatic Approach(2015-10-19) Bartels, Richard; Mahdavi-Amiri, Ali; Samavati, FaramarzIn [2, 3, 20, 21] the authors explored a construction to produce multiresolutions from given subdivisions. Certain assumptions carried through that work, two of which we wish to challenge: (1) that multiresolutions for irregular meshes have to be constructed on the fly rather than being prepared beforehand and (2) that the connectivity graph of the coarse mesh would have to be a subgraph of the connectivity graph of the fine mesh. Kobbelt's √3 subdivision [11] lets us engage both of these assumptions. With respect to (2), the √3, post-subdivision connectivity graph shares no interior edges with the pre-subdivision connectivity graph. With respect to (1), we observe that subdivision does not produce an arbitrary connectivity graph. Rather, there are local regularities that subdivision imposes on the fine mesh that are exploitable to establish, in advance, the decomposition and reconstruction filters of a multiresolution for an irregular coarse mesh.Item Open Access 3D Sketching and Collaborative Design with Napkin Sketch-The Video(2011-04-19T16:37:51Z) Xin, Min; Sharlin, Ehud; Costa Sousa, MarioThis is a video presentation of our work on Napkin Sketch, a new 3D Sketching and Collaborative Design tool. The video presentation is based on Min Xin's M.Sc. defense talk. Computer-supported 3D design tools have become increasingly popular and abundant because they offer easy editing, efficient content management, extensive sharing, and rich rendering capabilities. However, many of these tools are focused on generating high quality, visually appealing, and detailed models of baked ideas but often seem to fail in effectively supporting the intricate process and environment which help to create and nurture these ideas in the early design stages. Inspired by the simple yet rich interactions afforded by traditional design tools such as pencil, paper, or napkin in supporting the creative process of the early design stages, this thesis attempts to capture their essential qualities like portability, flexibility, fluidity, expressiveness, ambiguity, and sociability in Napkin Sketch, a computer supported tool which enables 3D sketching and collaborative design. Concepts such as tangible interaction and freeform interaction are explored and applied to create a sketching experience which leverages users' innate ability to physically interact with tools, media, and collaborators and provides freedom to suggest ideas and invite changes without having to commit prematurely. The contributions of the thesis are centered around Napkin Sketch which include a hardware platform that enables users to tangibly explore the 3D design space and manipulate the sketching media, a complementary software platform that facilitates the creation of 3D sketches while maintaining the familiar paradigm of sketching on a flat physical surface, a collaborative sketching environment that supports ad hoc co-located collaboration via multiple instances of the system, and three design critiques that provide preliminary assessment of the potential effectiveness of Napkin Sketch as a useful tool for supporting creativity in the early design stages. This video report highlights the main points of the our project.Item Open Access The 3D Tractus: A Three-Dimensional Drawing Board(2005-08-26) Lapides, Paul; Sharlin, Ehud; Costa Sousa, Mario; Streit, LisaWe present the 3D Tractus: a simple and inexpensive system for interaction and exploration of three-dimensional (3D) data. The device is based on a traditional drawing board-like mechanical structure that can be easily moved up and down while its surface height is being tracked using a simple sensor. Users interact with a tablet or tablet PC that rests on the surface while simultaneously changing its height. The result is direct mapping of virtual and physical spaces allowing intuitive 3D interaction and data exploration. The 3D Tractus allows us to investigate novel 3D interaction techniques based on sketching and drawing as well as intuitive visual indicators and GUI layouts. The 3D Tractus' simple design concept can be easily adapted to other tabletop systems and the simple nature of the physical interaction allows the design of various exciting applications. We detail here the design and development of the 3D Tractus hardware and software as well as preliminary evaluation of a 3D drawing and sketching application realized using the new tabletop interface.Item Open Access 3De Interactive Lenses for Visualization in Virtual Environments(2018-10) Mota, Roberta Cabral Ramos; Rocha, Allan; Silva, Julio Daniel; Alim, Usman; Sharlin, EhudWe present 3De lens, a technique for focus+context 3D visualization of multiple geometric representations. Our lens fuses two categories of lenses (3D and Decal) into a single coherent entity, thus enabling flexible use of either one or the two lenses combined depending on the underlying data geometry. In addition, we incorporate our lens into virtual reality as it enables a rich and natural style of direct spatial manipulation for exploratory 3D data analysis. To demonstrate its potential use, we discuss two domain examples in which our lens technique creates customized visualizations of both surfaces and streamlines.Item Open Access A Fast Fourier Transform with Rectangular Output on the BCC and FCC Lattices(2009-05) Alim, Usman R.; Möller, TorstenThis paper discusses the efficient, non-redundant evaluation of a Discrete Fourier Transform on the three dimensional Body-Centered and Face-Centered Cubic lattices. The key idea is to use an axis aligned window to truncate and periodize the sampled function which leads to separable transforms. We exploit the geometry of these lattices and show that by choosing a suitable non-redundant rectangular region in the frequency domain, the transforms can be efficiently evaluated using the Fast Fourier Transform.Item Open Access ABOUT CHARITY(1992-06-01) Fukushima, Tom; Cockett, RobinCharity is a categorical programming language based on distributive categories (in the sense of Schanuel and Lawvere) with strong datatypes (in the sense of Hagino). Distributive categories come with a term logic which can express most standard programs; and they are fundamental to computer science because they permit proof by case analysis and, when strong datatypes are introduced, proof by structural induction. Charity is functional and polymorphic in style, and is strongly normalizing. As a categorical programming language it provides a unique marriage of computer science and mathematical thought. The above aspects are particularly important for the production of verified programs as the naturality of morphisms gives us ``theorems for free'', termination proofs are not required, and mathemathical specifications can be used.Item Open Access ACCELERATING SEARCH IN FUNCTION INDUCTION(1989-11-01) Phan, Thong H.; Witten, Ian HInducing functions from examples is an important requirement in many learning systems. Blind search is the most general approach, but is vastly less efficient than specialized problem-solving methods. This paper presents a new strategy to accelerate search without sacrificing generality. Experiments with numeric functions show several orders of magnitude performance increase over the standard search technique. Two factors account for this improvement. First, the new strategy manipulates functions in groups instead of singly, so that many can be selected or discarded with only one comparison. Second, functional equivalence is handled automatically by the internal organization of search space.Item Open Access An Access Control Model for Facebook-Style Social Network Systems(2010-07-02T20:08:24Z) Anwar, Mohd; Zhao, Zhen; Fong, Philip W.L.Recent years have seen unprecedented growth in the popularity of social network systems, with Facebook being an archetypical example. The access control paradigm behind the privacy preservation mechanism of Facebook is distinctly different from such existing access control paradigms as Discretionary Access Control, Role-Based Access Control, Capability Systems, and TrustManagement Systems. This work takes a first step in deepening the understanding of this access control paradigm, by proposing an access control model that formalizes and generalizes the access control mechanism of Facebook. The model can be instantiated into a family of Facebook-style social network systems, each with a recognizably different access control mechanism, so that Facebook is but one instantiation of the model. We also demonstrate that the model can be instantiated to express policies that are not currently supported by Facebook, and yet these policies possess rich and natural social significance. Among these policies, we formally identify and characterize a special family of policies known as relational policies, which base their authorization decisions on the dynamic relationship between the resource owner and accessor. We believe the family of relational policies is a unique feature of social network systems. An executable encoding of this model has been developed to support experimentation with various instantiation of our access control model. This work thus delineates the design space of access control mechanisms for Facebook-style social network systems, and lays out a formal framework for policy analysis in these systems.Item Open Access Access Control Policy Analysis with a Visualization Tool for Social Network Systems(2011-03-17T16:27:12Z) Fong, Philip; Anwar, MohdUnderstanding privacy implications of access control policies is a complex task for the users of social network systems. Users need tool support to articulate on access scenarios and perform policy analysis. In this work, we develop a prototypical tool for reflective policy assessment (RPA) – a process in which a user examines her profile from the viewpoint of another user in her extended neighborhood in the social graph. Since an unrestricted view of one's extended neighborhood may compromise the privacy of others, our visualization tool approximates the extended neighborhood of a user in such a way that policy assessment can still be conducted in a meaningful manner, while the privacy of other users is preserved. We verify the utility and usability of our tool in a within-subject user study.Item Open Access ACQUIRING GRAPHICAL KNOW-HOW: AN APPRENTICESHIP MODEL(1988-03-01) Maulsby, David L.; Witten, Ian H.This paper studies the acquisition of procedural knowledge, or "know-how", from end-users in the domain of interactive graphics. In order to develop an open-ended system that is not restricted to any particular class of drawings, heavy emphasis is placed on the user interface. Experts (we call them simply "teachers") express procedures constructively, using any of the tools available in the interactive drawing environment. Well-structured procedures, including branches and loops, are inferred using a variety of weak generalization heuristics. The teacher's attention is concentrated on the system's perceptual and inferential shortcomings through a metaphorical apprentice called "Meta-Mouse". Its sensors are predominantly tactile, which forces teachers to make their constructions explicit. Meta-Mouse generalizes action sequences on the fly and eagerly carries out any actions it can predict. Theoretical support for the design comes from two sources: geometric phenomenology, which confirms that powerful problem-solving methods are associated with common-place spatial reasoning; and the fact that Meta-Mouse automatically imposes important "felicity conditions" on the teacher's demonstrations.Item Open Access ACQUISITION OF UNCERTAIN RULES IN A PROBABILISTIC LOGIC(1986-10-01) Cleary, John G.The problem of acquiring uncertain rules from examples is considered. The uncertain rules are expressed using a simple probabilistic logic which obeys all the axioms of propositional logic. By using three truth values (true, false, undefined) a consistent expression of contradictory evidence is obtained. As well the logic is able to express the correlations between rules and to deal both with uncertain rules and with uncertain evidence. It is shown that there is a subclass of such rules where the probabilities of correlations between the rules can be directly computed from examples.Item Open Access Adapting the Locales Framework for Heuristic Evaluation of Groupware(1999-08-11) Greenberg, Saul; Fitzpatrick, Geraldine; Gutwin, Carl; Kaplan, SimonHeuristic evaluation is a rapid, cheap and effective way for identifying usability problems in single user systems. However, current heuristics do not provide guidance for discovering problems specific to groupware usability. In this paper, we take the Locales Framework and restate it as heuristics appropriate for evaluating groupware. These are: 1) Provide locales; 2) Provide awareness within locales; 3) Allow individual views; 4) Allow people to manage and stay aware of their evolving interactions; 5) Provide a way to organize and relate locales to one another. To see if these new heuristics are useful in practise, we used them to inspect the interface of Teamwave Workplace, a commercial groupware product. We were successful at identifying the strengths of Teamwave as well as both major and minor interface problems.Item Open Access Adaptive Partial Snapshots with Logarithmic Step Complexity(2021-06-06) Bashari, Benyamin; Woelfel, PhilippThe standard single-writer snapshot type allows processes to obtain a consistent snapshot of an array of n memory locations, each of which can be updated by one of n processes. In almost all algorithms, a Scan() operation returns a linearizable snapshot of the entire array. Under realistic assumptions, where hardware registers do not have the capacity to store many array entries, this inherently leads to a step complexity of Ω(n). In this paper, we consider an alternative version of the snapshot type, where a Scan() operation stores a consistent snapshot of all n memory locations, but does not return anything. Instead, a process can later observe the value of any component of that snapshot using a separate Observe() operation. This allows us to implement the type from fetch-and-increment and compare-and-swap objects, such that Scan() operations have constant step complexity and Update() and Observe() operations have step complexity O(logn).Item Metadata only ADAPTIVE PERSONALIZED INTERFACES - A QUESTION OF VIABILITY(1984-04-01) Greenberg, Saul; Witten, Ian H.It is widely accepted that interfaces between computers and users should differ to accommodate individual, or group, needs. One method of "personalizing" an interface is to have the system form a limited model of the user and employ it to fashion the dialogue to his needs. Unfortunately, little is known about the effect of adaptation on the man/machine interface. Although obvious advantages accrue from "personalized" interfaces, there are also obvious disadvantages to presenting users with a changing, adapting, and perhaps apparently inconsistent interface. The goal of this work is to determine the viability of an adaptive interface through a human factor pilot study of a simple, specially-designed, interactive computer system. The system uses menu-driven selection to retrieve entries from a large ordered telephone directory. This simple task has several advantages: it is a realistic application area for interactive computers; plausible adaptive modeling methods exist and have been studied theoretically; and previous work has determined the best way to display the menus to users. The results of this empirical study support the use of adaptive user modeling. In the (admittedly highly constrained) example system, a computer interface can indeed adapt successfully to every user. Although it does not necessarily generalize to other user interfaces, the result supplies evidence to refute published objections to adaptive user modeling in general.Item Open Access ADAPTIVE PREDICTIVE TEXT GENERATION AND THE REACTIVE KEYBOARD(1989-01-01) Darragh, John JosephThis thesis discusses the application of predictive text generation to enhance the communication abilities of physically disabled persons. Predictive techniques exploit the statistical redundancies of language to accelerate and amplify user inputs, thereby increasing communication efficiency. Acceleration is achieved by making more likely language elements faster to select, while amplification is accomplished by selection of concatenated elements. Novel adaptive language models are used to enhance versatility and flexibility. Predictive text generation (PTG) is defined, existing PTG systems are surveyed and a framework is developed for classifying and evaluating them. Simulation studies and a user pilot experiment are persented for a particularly significant PTG system called \fIPredict\fR. Experience with Predict led to the Reactive Keyboard concept of PTG. The research results presented highlight design issues common to the two systems. The Reactive Keyboard concept is introduced along with its prediction technique, data structure and two user interface implementations: \fIRK-button\fR and RK-pointer. A clear distinction is made between the system's user interface and the underlying model it employs. A variable-length n-gram language model is presented which adaptively gathers statistics from the user's text input. A number of alternative model structures are discussed and details of a novel, highly compact, data storage technique are given. Context conditioned candidate strings, which are predicted by the model, are ordered according to popularity and displayed for selection on a VDU.Item Open Access ADAPTIVE PREDICTIVE TEXT GENERATION AND THE REACTIVE KEYBOARD(1989-05-01) Darragh, John J.; Witten, Ian H.This paper explores the application of predictive text generation to the human-computer interface. Predictive techniques exploit the statistical redundancy of language to accelerate and amplify user inputs. Acceleration is achieved by making more likely language elements faster to select, while amplification is accomplished by selection of concatenated elements. The language models used are created adaptively, decoupling the prediction mechanism from the application domain and user's vocabulary, and conforming automatically to whatever kind of text is entered. A device called the Reactive Keyboard is described along with two user interface implementations, one for keyboard entry and the other for a mouse/window environment. A clear separation is made between the system's user interface and the underlying model it employs, and the two versions share the same prediction technique and adaptive modeling mechanism. The basic idea is to order context-conditioned candidate strings, which are predicted by the model, according to popularity and display them for selection.Item Open Access ADAPTIVE ROBOT TRAINING EXPLORATIONS IN SENSORLESS MANIPULATION(1990-06-01) Pauli, DavidSeveral different techniques for training robots exist. The simplest and most common is leading or guiding, but this method is limited and inflexible. Textual or explicit programming has enjoyed many advances in the last decade and current research versions of explicit systems are very powerful. But explicit programming is complex and requires the skills of specially trained programmers. Mixed systems attempt to capitalize on the benefits of guiding and programming to simplify the training process. This union is particularly applicable to training sensorless robots in which the robot is used as a measuring device to specify task locations. But existing mixed systems exhibit a poorly designed interface, thus creating problems in the way the programming and guiding processes interact. This thesis presents the design and implementation of a prototypical mixed system that improves not only the programming and guiding components, but also their interface. The improvements are embodied in ART, an Adaptive Robot Trainer. ART's development involved an analysis of mixed systems and assembly tasks that resulted in an effective representation of task state. The representation led to the design of ART's programming language which automates much of the program-guiding interaction. ART's syntax allows the programmer to express assembly operations and object-feature relationships in a natural way while providing the system with the information necessary to maintain task state. The representation also enables guiding error corrections, flexibility in the guiding protocol, and the generation of meaningful messages to prompt operator actions.Item Metadata only ADAPTIVE TEXT COMPRESSION TO ENHANCE A MODEM(1983-10-01) Darragh, John J.; Witten, Ian H.; Cleary, John G.The design of a coding system is described and evaluated in the context of a computer-to-terminal modem connection. Unlike other compression problems, it is hard to characterise the kinds of information that may require processing. For this reason the system uses an adaptive Markov model, in conjuction with arithmetic coding. The compression performance improves with available memory. Two techniques for storing the Markov model are described. Experimental results are reported for a variety of sample texts. It is shown that effective line speeds can be at least doubled, and in some cases tripled, using less than 64 Kbytes of memory.