| CS-95-56 | ||||
|---|---|---|---|---|
| Title | Numerical Control Tool Path Generation using Space-Filling Curves and Pixel Models | |||
| Authors | D.P. Dragomatz | |||
| Abstract | Two methods for generating numerical control tool paths have ap- peared recently, one using pixel models, the other using Hilbert curves. The pixel model approach is able to represent many as- pects of path generation, but requires large amounts of storage for physically large objects represented at high accuracy. The Hilbert curve approach uses the local refinement property of Hil- bert space-filling curves to create an adaptive sampling approach that increases the density of path points only where necessary. In this thesis, I propose and implement a hybrid technique that uses elements of each method, retaining the major benefits of both without incurring the storage costs of the pixel model. The scheme supports the creation of both roughing paths and surface machining paths, but is non-optimal for the later. The addition of containment and exclusion zones to the method leads to a promising paradigm for partitioning object geometry into machin- able regions. | |||
| Date | December 1995 | |||
| Comments | Chapter 2 is a 35-page discussion on issues in tool path generation mostly from a computational point of view. Chapter 3 is background material on space-filling curves and pixel models. Chapter 4 describes the approach and shows some sample paths, including photographs of machined parts. Appendix A is a 36-page classified bibliography of papers on various topics related to NC tool path generation. |
|||
| Report | Numerical Control Tool Path Generation using Space-Filling Curves and Pixel Models (PS) | Compressed PostScript: Numerical Control Tool Path Generation using Space-Filling Curves and Pixel Models (PS.Z) |
||
| CS-95-54 | ||||
|---|---|---|---|---|
| Title | Spline Extensions for the MAPLE Plot System | |||
| Authors | Wolfgang Heidrich | |||
| Abstract | Traditionally computer algebra systems use lines and polygons to represent mathematical functions graphically. While these geometric primitives can easily be rendered on conventional raster graphics hardware, a smooth representation using splines would provide a wider range of tradeoffs between image quality and rendering performance. Since modern computer graphics hardware directly supports rendering of spline objects, their use becomes more and more interesting. In this thesis we examine the possibilities for replacing traditional representations of functions and graphs by spline representations. We describe the use of \BSplines\ for interpolation and approximation, and discuss several approaches for generating parameterizations for these tasks. Finally we present some novel results regarding the use of rational splines for curve and surface fitting. |
|||
| Report | Spline Extensions for the MAPLE Plot System (PDF) | Compressed PostScript: Spline Extensions for the MAPLE Plot System (PS.Z) |
||
| CS-95-53 | ||||
|---|---|---|---|---|
| Title | A topological data structure for hierarchical planar subdivisions | |||
| Authors | W. Celes F., L.H. de Figuiredo, M. Gattass, P.C. Carvalho | |||
| Abstract | We introduce HPS, a new topological data structure that efficiently represents hierarchies of planar subdivisions, thus providing direct and efficient support for GIS concepts such as abstract generalizations and multi-scale partitions. Unlike previous ad hoc solutions, HPS provides efficient access to adjacency information for each level and across levels, while storing the complete hierarchy in a single data structure, without duplications. HPS also provides topological operators that ensure global consistency. Like all topological data structures, HPS can be used as a framework onto which geometric and attribute information is placed: HPS explicitly handles attributes consistently with modeling, and naturally supports both topological and geometrical multi-resolution representations. We also discuss how some typical applications in GIS, Digital Cartography, and Finite Element mesh generation can be improved with HPS. Keywords:topological data structures, hierarchical modeling, multi-resolution, multi-scale partitions, Geographic Information Systems |
|||
| Date | December 1995 | |||
| Comments | This paper has been submitted to Algorithmica (special issue on GIS) | |||
| Report | A topological data structure for hierarchical planar subdivisions (PDF) | Compressed PostScript: A topological data structure for hierarchical planar subdivisions (GZIP) |
||
| CS-95-52 | ||||
|---|---|---|---|---|
| Title | Program Understanding: A Constraint Satisfaction Modeling Framework; Understanding as Plan Recognition | |||
| Authors | S. Woods, A. Quilici and Qiang Yang | |||
| Abstract | Different program understanding algorithms often use different representational frameworks and take advantage of numerous heuristic tricks. This situation makes it is difficult to compare these approaches and their performance. This paper addresses this problem by proposing constraint satisfaction as a general framework for describing program understanding algorithms, demonstrating how to tranform a relatively complex existing program understanding algorithm into an instance of a constraint satisfaction problem, and showing how this facilitates better understanding of its performance. Plan recognition is the task of interpreting the actions of agents in the environment, in the context of the knowledge we possess about how action occurs in the world, and why. The recognition task involves constructing a mapping, possibly partial, between an existing repository of plan and domain knowledge and a set of dynamic observations of a subset of the actions taken toward a goal. Program understanding can be viewed as a special case of plan recognition, where the task is to recognize the plans programmers have used in constructing a particular piece of legacy source code. However, program understanding differs from generalized plan recognition in that a complete set of action observations is the basis of goal determination. This paper discusses, in detail, how this difference leads to inadequacies in applying typical plan recognition algorithms to program understanding. Program understanding can instead be viewed as a special case of plan recognition which is particularly amenable to constraint satisfaction techniques. |
|||
| Date | November 1995 | |||
| Report | Program Understanding: A Constraint Satisfaction Modeling Framework; Understanding as Plan Recognition (PDF) | Compressed PostScript: Program Understanding: A Constraint Satisfaction Modeling Framework; Understanding as Plan Recognition (PS.Z) |
||
| CS-95-51 | ||||
|---|---|---|---|---|
| Title | Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques | |||
| Authors | S. Woods and Q. Yang | |||
| Abstract | The process of understanding a source code in a high-level programming language involves complex computation. Given a piece of legacy code and a library of program plan templates, understanding the code corresponds to building mappings from parts of the source code to particular program plans. These mappings could be used to assist an expert in reverse engineering legacy code, to facilitate software reuse, or to assist in the translation of the source into another programming language. In this paper we present a model of program understanding using constraint satisfaction. Within this model we intelligently compose a partial global picture of the source program code by transforming knowledge about the problem domain and the program itself into sets of constraints. We then systematically study different search algorithms and empirically evaluate their performance. One advantage of the constraint satisfaction model is its generality; many previous attempts in program understanding could now be cast under the same spectrum of heuristics, and thus be readily compared. Another advantage is the improvement in search efficiency using various heuristic techniques in constraint satisfaction. | |||
| Date | November 1995 | |||
| Report | Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques (PDF) | Compressed PostScript: Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques (PS.Z) |
||
| CS-95-50 | ||||
|---|---|---|---|---|
| Title | Analysis of Hashing Algorithms and a New Mathematical Transform | |||
| Authors | A. Viola | |||
| Abstract | The main contribution of this report is the introduction of a new mathematical tool that we call the Diagonal Poisson Transform, and its application to the analysis of some linear probing hashing schemes. We also present what appears to be the first exact analysis of a linear probing hashing scheme with buckets of size b. First, we present the Diagonal Poisson Transform. We show its main properties and apply it to solve recurrences, find inversse relations and obtain several generalizations of Abel's summation formula. We follow with the analysis of LCFS hashing with linear probing. It is known that the Robin Hood linear probing algorith minimizes the variance of the cost of successful searches for all linear probing algorithms. We prove that the variance of the LCFS scheme is within lower order terms of this optimum. Finally, we present the first exact analysis of linear probing hashing with buckets of size b. From the generating function for the Robin Hood heuristic, we obtain exact expressions for the cost of successful searches when the table is full. Then, with the help of Singularity Analysis, we find the asymptotic expansion of this cost up to O((bm)-1), where m is the number of buckets. We also give upper and lower bound when the table is not full. We conclude with a new approach to study certain recurrences that involves truncated exponentials. A new family of numbers that satisfies a recurrence resembling that of the Bernoulli numbers is introduced. These numbers may prove helpful in studying recurrences involving truncated generating functions. |
|||
| Date | December 1995 | |||
| Report | Analysis of Hashing Algorithms and a New Mathematical Transform (PDF) | Compressed PostScript: Analysis of Hashing Algorithms and a New Mathematical Transform (PS.Z) |
||
| CS-95-48 | ||||
|---|---|---|---|---|
| Title | Process Spaces | |||
| Authors | R. Negulescu | |||
| Abstract | This paper introduces process spaces, a unified theory of interacting systems. The main new trait, abstract executions, leads to a simple and general set formalism. For concurrent systems (including digital circuits), process spaces apply to diverse correctness concerns and yield a new classification of liveness and progress faults. The resulting studies of different correctness concerns are decoupled and homogeneous (i.e., they do not interfere with each other and they have the same algebraic structure). Applications to other interacting systems, such as electrical networks and dynamical systems, are also possible. Process spaces have many meaningful properties; here, some results from concurrency theory are generalized and simplified, and some new results are found. | |||
| Date | December 1995 | |||
| Report | Process Spaces (PDF) | Compressed PostScript: Process Spaces (PS.Z) |
||
| CS-95-47 | ||||
|---|---|---|---|---|
| Title | Surface intersection using affine arithmetic | |||
| Authors | L.H. de Figueiredo | |||
| Abstract | We describe a variant of a domain decomposition method proposed by Gleicher and Kass for intersecting and trimming parametric surfaces. Instead of using interval arithmetic to guide the decomposition, the variant described here uses affine arithmetic, a tool recently proposed for range analysis. Affine arithmetic is similar to standard interval arithmetic, but takes into account correlations between operands and sub-formulas, generally providing much tighter bounds for the computed quantities. As a consequence, the quadtree domain decompositions are much smaller and the intersection algorithm runs faster. Keywords: surface intersection, trimming surfaces, range analysis, interval analysis, CAGD |
|||
| Date | October 1995 | |||
| Comments | This paper has been submitted to Graphics Interface `96 | |||
| Report | Surface intersection using affine arithmetic (PDF) | Compressed PostScript: Surface intersection using affine arithmetic (GZIP) |
||
| CS-95-46 | ||||
|---|---|---|---|---|
| Title | Transformation of Structured Documents | |||
| Authors | E. Kuikka and M. Penttonen | |||
| Abstract | Structure definitions of documents have been used successfully for inputting and formatting in text processing systems. This report considers transformations between different representations of structured documents and studies possiblities to extend the use of structure definitions to document transformations and to discover algorithmic methods for carrying out transformations. Documents are presented as parse trees for context-free grammars and transformations are made from parse tree to parse tree. First, the report describes differences of manuscript styles demanded by various scientific journals and presents a declarative classification for structure differences between two parse trees. Second, a set of tree transformation methods are described and their suitability for transformations between documents having a structure difference in each defined class is analyzed. For each class several methods may or must be used and only certain kinds of differences can be managed automatically. Finally, instead of designing a system where a method accommodates for all kinds of differences or where different methods are used in various transformations, the report presents a model for a document transformation system that presents a possibility of using various methods according to differences in document representations. The system is divided two modules. In the first one transformations are made automatically and they do not change the hierarchical structure of a document. In the second one transformations are made semiautomatically or nonautomatically and the hierarchical structure changes. Differences between the existing and the required representation of a document are analyzed and methods selected according to the classified differences. | |||
| Date | October 1995 | |||
| Comments | The later version of this report has been submitted to Eletronic Publishing journal. | |||
| Report | Transformation of Structured Documents (PDF) | Compressed PostScript: Transformation of Structured Documents (GZIP) |
||
| CS-95-45 | ||||
|---|---|---|---|---|
| Title | Scenario-Based Analysis of Software Architecture | |||
| Authors | R.N. Kazman, Gregory Abowd, Len Bass and Paul Clements | |||
| Abstract | Software architecture is one of the most important tools for designing and understanding a system, whether that system is in preliminary design, active deployment, or maintenance. Scenarios are important tools for exercising an architecture in order to gain information about a system's fitness with respect to a set of desired quality attributes. This paper presents a set of experiential case studies illustrating the methodological use of scenarios to gain architecture-level understanding and predictive insight into large, real-world systems in various domains. A structured method for scenario-based architectural analysis is presented, using scenarios to analyze architectures with respect to achieving quality attributes. Finally, lessons and morals are presented, drawn from the growing body of experience in applying scenario-based architectural analysis techniques. | |||
| Date | October 1995 | |||
| Report | Scenario-Based Analysis of Software Architecture (PDF) | Compressed PostScript: Scenario-Based Analysis of Software Architecture (GZIP) |
||
| CS-95-44 | ||||
|---|---|---|---|---|
| Title | Depth from Shading as an Attentional Cue in User Surfaces | |||
| Authors | S.L. Loop | |||
| Abstract | When using a computer, we are engaging in a dialogue with the computer. In order to communicate effectively with the computer, we must be aware of the state of the computer. Therefore, we need our attention drawn to particular areas that may indicate the state. When these areas are not found easily, that is these areas are not conspicuous, then we may sacrifice speed and accuracy resulting in potentially disastrous consequences. It has been known for years that colour is very conspicuous: it is easily noticed and attracts attention. For this reason, colour has been used in the interface to group, discriminate and draw attention. Visual texture, normally studied for its segregating and discriminating properties, is also very conspicuous. Another visual attribute that research has shown to be conspicuous is depth conveyed through shape from shading perception: convex and concave objects are easily discriminated. The thee-dimensional look that shape from shading imparts is becoming more popular in interface design due to its concrete, realistic appeal. However, designers are not making use of the functional benefits, that is the conspicuousness, of depth from shading in the design of the interface. A windowing system is a good example of an interface that needs to present conspicuous information to the user so that the user knows the state of the computer. In this case, so it is known which window is active and can receive input. This thesis empirically supports the idea that depth from shading can be used as a conspicuous attribute in a windowing system to indicate the active window. However, as the depth from shading cue is obscured by othe overlapping windows, the conspicuousness of the cue decreases. Some guidelines for maintaining conspicuity of the depth from shading cue are provided. |
|||
| Date | October 1995 | |||
| Comments | The experimental results files before processing are in the 'results.*' files. 'results.E1.*' = experiment 1 'results.E2.*' = experiment 2 'results.E3.*' = experiment 3 |
|||
| Report | E1 (SL), E2 (ED), E2 (FG), E2 (GV), E2 (JB), E2 (JW) | E2 (SL), E2 (SM), E2 (WC), E3 (SL), E3 (WC) | Depth from Shading as an Attentional Cue in User Surfaces (PDF) | Compressed PostScript: Depth from Shading as an Attentional Cue in User Surfaces (PS.Z) |
| CS-95-41 | ||||
|---|---|---|---|---|
| Title | Searching in Constant Time and Minimum Space | |||
| Authors | A. Brodnik | |||
| Abstract |
This report deals with techniques for minimal space representation of a subset of elements from a bounded universe so that various types of searches can be performed in constant time. In particular, we introduce a data structure to represent a subset of N elements of [0, ..., M-1]$ in a number of bits close to the information- theoretic minimum and use the structure to answer membership queries in constant time. Next, we describe a representation of an arbitrary subset of points on an M x M grid such that closest neighbour queries (under L_1 and L_oo) can be performed in constant time. This structure requires M^2 + o(M^2) bits. Finally, under a byte overlap model of memory we present an M+o(M) bit, constant time solution to the dynamic one-dimensional closest neighbour problem (hence, also union-split-find and priority queue problems) on [0, ..., M-1]. |
|||
| Date | September 1995 | |||
| Comments |
|
|||
| Report | Searching in Constant Time and Minimum Space (PDF) | Compressed PostScript: Searching in Constant Time and Minimum Space (PS.Z) |
||
| CS-95-40 | ||||
|---|---|---|---|---|
| Title | Programming Support for Blossoming: The Blossom Classes | |||
| Authors | Wayne Liu | |||
| Abstract | A C++ library has been created to facilitate prototyping of curve and surface modeling techniques. The library provides general-purpose blossoming datatypes to support creation of modeling techniques based on blossoming analysis. The datatypes have efficient operations which are generalizations of important CAGD algorithms, and can be used to implement many algorithms. Most importantly, the library is able to inter-operate with user-supplied datatypes or routines to create complex modeling techniques. | |||
| Comments | - This technical report is based on author's master's thesis. - The code for the library described in this thesis is available by contacting the author. |
|||
| Report | Programming Support for Blossoming: The Blossom Classes (PDF) | Compressed PostScript: Programming Support for Blossoming: The Blossom Classes (PS.Z) |
||
| CS-95-39 | ||||
|---|---|---|---|---|
| Title | A Study of Delays and De-Synchronisation in a Multiple-View Direct Manipulation Task | |||
| Authors | F. Jaubert | |||
| Abstract | Computer graphics are used in increasingly complex situations, often involving multiple dynamic views. This poses the problem of maintaining proper synchronisation among the various views. The effect of de-synchronisation and delays in command-line and single-view graphical environments has been well studied; this thesis aims to do the same with multiple view environments. To that end, an experimental platform is developed, which requires subjects to complete a placement task in a multiple-view representation of a three-dimensional world. Delays are imposed on the different views, and the effect on the subject's performance (in terms of completion time and number of manipulation operations required) is noted. The results show that delays on the view under manipulation have a definite detrimental effect on all subjects; furthermore, certain subjects are affected by delays on other views as well. To conclude, the experiment reveals that the problem of de-synchronisation in a multiple-view environment is a complex one, requiring further research; several new experiments are suggested to help answer the questions posed in this study. | |||
| Date | September 1995 | |||
| Comments | A Master of Mathematics Thesis | |||
| Report | A Study of Delays and De-Synchronisation in a Multiple-View Direct Manipulation Task (PDF) | Compressed PostScript: A Study of Delays and De-Synchronisation in a Multiple-View Direct Manipulation Task (PS.Z) |
||
| CS-95-37 | ||||
|---|---|---|---|---|
| Title | Editable Software Views | |||
| Authors | Michael Hardy | |||
| Abstract | Understanding software is a very expensive component of software development and maintenance. As a result, tools that assist in the process of software understanding play an important part in reducing software development and maintenance costs. As part of this research, the current literature was examined and it was determined, surprisingly, that very little work had been done in developing tools to assist programmers in understanding source code. Many of the tools presented in the literature suffer from one or more drawbacks that limit their usefulness for a software developer or maintainer. To address some of these limitations, an extensible prototype system that presents extrinsic information about a program in editable source code views was designed and developed. The views are created by embellishing the source code using changes in font family, size, and style, text colour, and text elision. This thesis presents the design and implementation of this system. This research represents a step in the development of tools to assist in software understanding, but it is clear that more effort must be directed towards this area of research. | |||
| Report | Editable Software Views (PDF) | Compressed PostScript: Editable Software Views (PS.Z) |
||
| CS-95-35 | ||||
|---|---|---|---|---|
| Title | Improving Depth Perception in 3D Interfaces with Sound | |||
| Authors | S. Mereu | |||
| Abstract | The ability for users to perceive depth in 3D computer interfaces is essential for these applications to be useful. Due to the 2D nature of the display screen, perceiving three dimensions is not always as easy as it is in the real world. Solutions to the lack of depth cues presented are numerous including stereo glasses and head tracking. These solutions, however, are often too expensive for the general user. Sound on the other hand is relatively inexpensive. Experiments have recently been completed in this area and have shown that sound is an effective depth cue. This report discusses the results and makes suggestions on implementing a sound based application. | |||
| Date | August 1995 | |||
| Report | Improving Depth Perception in 3D Interfaces with Sound (PDF) | Compressed PostScript: Improving Depth Perception in 3D Interfaces with Sound (PS.Z) |
||
| CS-95-32 | ||||
|---|---|---|---|---|
| Title | Relative Liveness: From Intuition to Automated Verification | |||
| Authors | R. Negulescu and J.A. Brzozowski | |||
| Abstract | We point out deficiencies of previous treatments of liveness. We define a new liveness condition in two forms: one based on finite trace theory, and the other on automata. We prove the equivalence of these two definitions. We also introduce a safety condition and provide modular and hierarchical verification theorems for both safety and liveness. Finally, we present a verification algorithm for liveness. | |||
| Date | July 1995 | |||
| Comments | An extended summary of this report was presented at the Second Working Conference on Asynchronous Design Methodologies, South Bank University, London, UK, May 1995. | |||
| Report | Relative Liveness: From Intuition to Automated Verification (PDF) | Compressed PostScript: Relative Liveness: From Intuition to Automated Verification (PS.Z) |
||
| CS-95-31 | ||||
|---|---|---|---|---|
| Title | Nonlinear Iteration Methods for High Speed Laminar Compressible Navier-Stokes Equations | |||
| Authors | P.A. Forsyth and H. Jiang | |||
| Abstract | Full Newton nonlinear iteration is compared to use of a defect correction approach (first order Jacobian, second order residual) for solving the steady state compressible flow equations. The Jacobian is constructed numerically, and solved using a PCG type method with block $ILU(k)$ preconditioning. Numerical tests are carried out using the NACA 0012 airfoil, at various free stream Mach numbers and Reynolds numbers. The full Newton approximation is generally more robust and takes less CPU time than the defect correction approach. No particular difficulty was observed in solving the full Newton Jacobian using an $ILU(2)$ ($\simeq 100,000$ unknowns) with CGSTAB acceleration. | |||
| Date | July 1995 | |||
| Report | Nonlinear Iteration Methods for High Speed Laminar Compressible Navier-Stokes Equations (PDF) | Compressed PostScript: Nonlinear Iteration Methods for High Speed Laminar Compressible Navier-Stokes Equations (GZIP) |
||
| CS-95-30 | ||||
|---|---|---|---|---|
| Title | Finding Largest Subtrees and Smallest Supertrees | |||
| Authors | A. Gupta and N. Nishimura | |||
| Abstract | As trees are used in a wide variety of application areas, the comparison of trees arises in many guises. Here we consider two generalizations of classical tree pattern matching, which consists of determining if one tree is isomorphic to a subgraph of another. For the embedding problems of subgraph isomorphism and topological embedding, we present algorithms for determining the largest tree embeddable in two trees T and T' (or a largest subtree) and for constructing the smallest tree in which each of T and T' can be embedded (or a smallest supertree). Both subtrees and supertrees can be used in a variety of different applications. For example, when each of the two trees contains partial information about a data set, such as the evolution of a set of species, the subtree or supertree corresponds to a structuring of the data in a manner consistent with both original trees. The size of a subtree or supertree of two trees can also be used to measure the similarity between two arrangements of data, whether images, documents, or RNA secondary structures. In this paper, we present a general paradigm for sequential and parallel subtree and supertree algorithms for subgraph isomorphism and topological embedding. Our sequential algorithms run in time O(n^{2.5} log n) and our parallel algorithms in time O(log^3 n) on a randomized CREW PRAM using a polynomial number of processors. In addition, we produce better algorithms for these problems when the underlying trees are ordered, that is, when the children of each node have a left-to-right ordering associated with them. In particular, we obtain O(n^2) time sequential algorithms and O(log^3 n) time deterministic parallel algorithms on CREW PRAMs for both embeddings. |
|||
| Date | July 1995 | |||
| Report | Finding Largest Subtrees and Smallest Supertrees (PDF) | Compressed PostScript: Finding Largest Subtrees and Smallest Supertrees (PS.Z) |
||
| CS-95-25 | ||||
|---|---|---|---|---|
| Title | Text/Relational Database Management Systems: Overview and Proposed SQL Extensions | |||
| Authors | G.E. Blake,M.P. Consens, I.J. Davis, P. Kilpelainen, E. Kuikka, P.-A. Larson, T. Snider and F.W. Tompa | |||
| Abstract | Combined text and relational database support is increasingly recognized as an emerging need of industry, spanning applications requiring text fields as parts of their data (e.g., for customer sup- port) to those augmenting primary text resources by conventional rela- tional data (e.g., for publication control). In this paper, we propose extensions to SQL2 that provide flexible and efficient access to struc- tured text described by SGML or other encodings. We also propose an architecture to support a text/relational database management system as a federated database environment, where component databases are accessed via ``agents'': SQL agents that translate standard or extended SQL2 queries into vendor-specific dialects, and text agents that pro- cess text sub-queries on full-text search engines. | |||
| Date | June 1995 | |||
| Comments | Supercedes earlier version published in Proceedings of the ADB'94 Conference. | |||
| Report | Text/Relational Database Management Systems: Overview and Proposed SQL Extensions (PDF) | Compressed PostScript: Text/Relational Database Management Systems: Overview and Proposed SQL Extensions (PS.Z) |
||
| CS-95-24 | ||||
|---|---|---|---|---|
| Title | An Analysis of Polynomial Composition Algorithms | |||
| Authors | S. Mann and W. Liu | |||
| Abstract | An analysis is made of the runtime of a previously published algorithm for polynomial composition. Two new, more efficient algorithms are presented. One of these algorithms is optimal, while the other algorithm is numerically more stable than the optimal one. Additionally, as a generalization of polynomial composition, we show how to compose a multiaffine function with a set of polynomials as an extension to an earlier algorithm for composing two polynomial functions. With this extension, we are able to perform degree raising with composition. |
|||
| Date | June 1995 | |||
| Report | An Analysis of Polynomial Composition Algorithms (PDF) | Compressed PostScript: An Analysis of Polynomial Composition Algorithms (PS.Z) |
||
| CS-95-22 | ||||
|---|---|---|---|---|
| Title | Evaluating Tensor Product and Triangular Bezier Surfaces | |||
| Authors | J. Carriere | |||
| Abstract | Many papers describe techniques for evaluating spline curves and surfaces. While each paper provides some theoretical or empirical evidence with which to compare techniques, there exist few global comparisons. Also, papers describing particular algorithms often provide few details, making implementation of the technique presented difficult or impossible. This report attempts to illuminate the performance relationships between, and implementations of, various methods for rendering spline surfaces. Empirical results are given for bicubic tensor product Bezier surfaces, and for cubic and quartic triangular Bezier surfaces. | |||
| Date | May 1995 | |||
| Report | Evaluating Tensor Product and Triangular Bezier Surfaces (PDF) | Compressed PostScript: Evaluating Tensor Product and Triangular Bezier Surfaces (PS.Z) |
||
| CS-95-20 | ||||
|---|---|---|---|---|
| Title | Walking Streets Faster | |||
| Authors | A. Lopez-Ortiz and S. Schuierer | |||
| Abstract | A fundamental problem in robotics is to compute a path for a robot from its current location to a given goal. In this paper we consider the problem of a robot equipped with an on-board vision system searching for a goal g in an unknown environment. We assume that the robot is originally located at a point $s$ on the boundary of a street polygon. A street is a simple polygon with two distinguished points s and g, which are located on the polygon boundary and the part of the polygon boundary from s to g is weakly visible to the part from g to s and vice versa. Our aim is to minimise the ratio of the length of the path traveled by the robot to the length of the shortest path from s to g. In analogy to on-line algorithms this value is called the competitive ratio. We present a series of strategies all of which follow the same general high level strategy. In the first part we present a class of strategies any of which can be shown to have a competitive ratio of Pi + 1. These strategies are robust under small navigational errors and their analysis is very simple. In the second part we present the strategy Continuous Lad which is based on the heuristic optimality criterion of minimising the Local Absolute Detour. We show an upper bound on the competitive ratio of Continuous Lad of ~2.03. Finally, we also present a hybrid strategy consisting of Continuous Lad and the strategy Move-in-Quadrant. We show that this combination of strategies achieves a competitive ratio of 1.73. This about halves the gap between the known sqrt(2) lower bound for this problem and the previously best known competitive ratio of ~2.05. |
|||
| Date | October 1995 | |||
| Report | Walking Streets Faster (PDF) | Compressed PostScript: Walking Streets Faster (PS.Z) |
||
| CS-95-17 | ||||
|---|---|---|---|---|
| Title | From Data Representation to Data Model: Meta-Semantic Issues in the Evolution of SGML | |||
| Authors | D. Raymond, F.W. Tompa and D. Wood | |||
| Abstract | SGML provides standard representations for documents, but as documents become more fluid, we will need standard semantics for them as well. The ability to manage change is a fundamental capability of any system that supports document semantics. We look at three areas important in change management: equivalence, redundancy, and operators. We show how these areas are implicitly addressed in SGML and SGML-based standards, and argue that more explicit consideration would be useful both for evaluating current standards, and for developing new systems for document semantics. Keywords:document semantics, document update, document data modelling |
|||
| Date | April 1995 | |||
| Report | From Data Representation to Data Model: Meta-Semantic Issues in the Evolution of SGML (PDF) | Compressed PostScript: From Data Representation to Data Model: Meta-Semantic Issues in the Evolution of SGML (PS.Z) |
||
| CS-95-14 | ||||
|---|---|---|---|---|
| Title | The Complexity of Subgraph Isomorphism: Duality Results for Graphs of Bounded Path-and Tree-Width | |||
| Authors | A. Gupta and N. Nishimura | |||
| Abstract | We present a clear demarcation between classes of bounded tree-width graphs for which the subgraph isomorphism problem is NP-complete and those for which it can be solved in polynomial time. In previous work, it has been shown that this problem is solvable in polynomial time if the source graph has either bounded degree or is k-connected, for k the tree-width of the two graphs. As well, it has also been shown that for certain specific connectivity or degree conditions, the problem becomes NP-complete. Here we give a complete characterization of the complexity of this problem on bounded tree-width graphs for all possible connectivity conditions of the two input graphs. Specifically, we show that when the source graph is not k-connected or has more than k vertices of unbounded degree the problem is NP-complete, thus answering an open question of Matousek and Thomas. Many of our reductions are restricted to using a subset of graphs of bounded tree-width, namely graphs of bounded path-width. As a direct result of our constructions, we also show that when the source and target graphs have connectivity less than k or at least one has k vertices of unbounded degree, the subgraph isomorphism problem for bounded path-width graphs is NP-complete. |
|||
| Date | February 1995 | |||
| Report | The Complexity of Subgraph Isomorphism: Duality Results for Graphs of Bounded Path-and Tree-Width (PDF) | Compressed PostScript: The Complexity of Subgraph Isomorphism: Duality Results for Graphs of Bounded Path-and Tree-Width (PS.Z) |
||
| CS-95-12 | ||||
|---|---|---|---|---|
| Title | A Global Search Architecture | |||
| Authors | F.J. Burkowski, G.V. Cormack, C.L.A. Clarke and R.C. Good | |||
| Abstract | Recent advances in communication and storage technology make available vast quantities of on-line information. But this information is of limited use unless it can be searched effectively. Huge scale and heterogeneity of data raise a unique combination of architectural issues that must be addressed to support effective search. These issues occasion the use of multi-user distributed search databases with the following capabilities: efficient structured searching of the contents of files having various schema; continuous availability in spite of failures and maintenance; high-throughput incorporation of a continuous stream of updates, especially the arrival new data and removal of obsolete data. We present an architecture that embodies solutions to specific technical problems that arise in the provision of these capabilities. | |||
| Date | March 1995 | |||
| Report | A Global Search Architecture (PDF) | Compressed PostScript: A Global Search Architecture (PS.Z) |
||
| CS-95-10 | ||||
|---|---|---|---|---|
| Title | A Robust Storage System Architecture | |||
| Authors | R.C. Good, G.V. Cormack, D. Taylor and C.L.A. Clarke | |||
| Abstract | Error-correcting codes allow either incorrect data to be corrected or missing data to be rebuilt. They are frequently used with communications channels to recover data lost through line noise and thus provide a `noise free' bit pipe. Data can also be lost through hardware failure; for instance a disk crash. In case of hardware failure, we want a storage system that has the robustness and tunability of error-correcting codes in order to provide recovery of the lost data. This is especially so when dealing with systems involving a large number of disks as, when taken as a group, they are more error prone than single disks but are a vary practical way of building large data stores. At present, the most common way to provide data recovery is straight duplication (mirroring) or a code able to detect single failures within a tightly coupled array of disks. A new prototype system has been designed and implemented which uses linear error-correcting codes to provide data storage over a loosely coupled distributed storage system. The fault-tolerance of this system can be varied by choosing the amount of redundant information stored. |
|||
| Date | February 1995 | |||
| Report | A Robust Storage System Architecture (PDF) | Compressed PostScript: A Robust Storage System Architecture (PS.Z) |
||
| CS-95-09 | ||||
|---|---|---|---|---|
| Title | Interchanging the Order of Grouping and Join | |||
| Authors | W.P. Yan and P.A. Larson | |||
| Abstract | Assume that we have an SQL query containing joins, a GROUP-BY and possibly a HAVING predicate. The standard way of evaluating this type of query is to first perform the group-by early, that is to push the group-by operation past one or more joins. This may reduce the query processing cost by reducing the amount of data partocipating in joins. The reverse transformation, ie.e, performing joing before group-by, can also be beneficial because the join may greatly reduce the input to the group-by. We formally define the problem, adhering strictly to the semantics of SQL2, and prove necessary and sufficient conditions for deciding when the transformation is valid. In practice, it may be expensive or even impossible to test whether the conditions are satisfied. Therfore, we also present a more practical algorith that tests a simpler, sufficient condition. This algorithm is fast and detects a large subclass of transformable queries. | |||
| Date | February 1995 | |||
| Report | Interchanging the Order of Grouping and Join (PDF) | Compressed PostScript: Interchanging the Order of Grouping and Join (PS.Z) |
||
| CS-95-08 | ||||
|---|---|---|---|---|
| Title | A Calculus for Concurrent Update | |||
| Authors | G.V. Cormack | |||
| Abstract | The distributed operation transform (dOPT) is proposed by Ellis and Gibbs (SIGMOD Record 18:2, 1989) as a lock-free algorithm to ensure the consistency of concurrently updatable distributed objects. dOPT is shown by counterexample to be incorrect. A corrected algorithm is given for a restricted environment based on point-to-point communication. There appears to be no simple correction to dOPT for a general environment based on broadcast communication. | |||
| Date | January 1995 | |||
| Report | A Calculus for Concurrent Update (PDF) | Compressed PostScript: A Calculus for Concurrent Update (PS.Z) |
||
| CS-95-07 | ||||
|---|---|---|---|---|
| Title | On the use of Regular Expressions for Searching Text | |||
| Authors | C.L.A. Clarke and G.V. Cormack | |||
| Abstract | The use of regular expressions to search text is well known and understood as a useful technique. It is then surprising that the standard techniques and tools prove to be of limited use for searching text formatted with SGML or other similar markup languages. Experience with structured text search has caused us to carefully re-examine the current practice. The generally accepted rule of "left-most longest match" is an unfortunate choice and is at the root of the difficulties. We instead propose a rule which is semantically cleaner and is incidentally more simple and efficient to implement. This rule is generally applicable to any text search application. | |||
| Date | February 1995 | |||
| Report | On the use of Regular Expressions for Searching Text (PDF) | Compressed PostScript: On the use of Regular Expressions for Searching Text (PS.Z) |
||
| CS-95-06 | ||||
|---|---|---|---|---|
| Title | A Calculus for Concurrent Update | |||
| Authors | G.V. Cormack | |||
| Abstract | This paper introduces a calculus for concurrent update (CCU) that is used to specify distributed objects. The calculus permits updates to be effected immediately at each site - no central server, locking, token passing, rollback, or other form of serialization is enforced. Notice of each update at each site is transmitted to every other site, where a corresponding update is effected. Unless special provisions are taken, network transmission delay may cause corresponding updates to be effected at different sites in different orders, potentially rendering them meaningless or inconsistent. CCU avoids this eventuality: transformations are applied to corresponding updates as necessary to preserve overall meaning and consistency. CCU derives from the Distributed Operational Transform (dOPT) algorithm proposed by Ellis and Gibbs (ACM SIGMOD Record 18:2, 1989) as a concurrency control mechanism for groupware systems. dOPT introduces the notion of consistency-preserving transformations, and embeds exactly the lightweight CBCAST algorithm published later by Birman, Schiper and Stephenson (ACM TOCS 9:3, 1991). However, Ellis and Gibbs present no method for reasoning about either the overall consistency or meaningfulness of the transforms as applied by dOPT. Indeed, dOPT is incorrect, as demonstrated by a counterexample in which it fails to maintain consistency. |
|||
| Date | January 1995 | |||
| Report | A Calculus for Concurrent Update (PDF) | Compressed PostScript: A Calculus for Concurrent Update (PS.Z) |
||
| CS-95-01 | ||||
|---|---|---|---|---|
| Title | The Grail Papers: Version 2.3 | |||
| Authors | D. Raymond and D. Wood | |||
| Abstract | Grail is a package for computing with finite-state machines and regular expressions, written in C++. Grail supports input and output of textual descriptions of automata and regular expres- sions, conversions between machines and regular expressions, and other operations. Grail can be used as a set of shell-callable processes, a library of functions, or as individual C++ classes. Version 2.3 of Grail supports parameterizable machines and expressions. This collection of papers includes a description of the the his- tory and design of Grail, a user's guide, a programmer's guide. |
|||
| Date | January 1995 | |||
| Report |
Compressed PostScript: |
|||
