1994 technical reports

CS-94-45
Title Sharp Divisions in Complexity of Subgraph Isomorphism for Graphs of Bounded Path- and Tree-Width
Authors A. Gupta and N. Nishimura
Report Updated to CS-94-45
CS-94-43
Title A Fast Las Vegas Algorithm for Computing the Smith Normal Form of a Polynomial Matrix
Authors A. Storjohann and G. Labahn
Abstract A Las Vegas probabilistic algorithm is presented that finds the Smith normal form S over Q[x] of an n x n nonsingular input matrix A over Z[x] . The algorithm requires an expected number of O~(n^3 d (d + n^2 log ||A||)) bit operations (where ||A|| bounds the magnitude of all integer coefficients appearing in A and d bounds the degrees of entries of A ). In practice, the main cost of the computation is obtaining a non-unimodular triangularization of a polynomial matrix of same dimension and with similar size entries as the input matrix. We show how to accomplish this in O~(n^5 d (d + log ||A||) log ||A||) bit operations using standard integer, polynomial and matrix arithmetic. These complexity results improve significantly on previous algorithms in both a theoretical and practical sense.
Date November 13, 1994
Comments Citation: Linear Algebra and Applications (to appear).
Report A Fast Las Vegas Algorithm for Computing the Smith Normal Form of a Polynomial Matrix (PDF) Compressed PostScript:
A Fast Las Vegas Algorithm for Computing the Smith Normal Form of a Polynomial Matrix (PS.Z)
CS-94-42
Title On Verifying a Query Optimizer: A Correctness Proof for a Real-World Query Rewrite Rule
Authors B.Y. Feng
Abstract It is generally accepted that rule-based query optimization is a more flexible approach to supporting high-level query languages. However, current practice involves very limited consideration of the issue of rule validity (or correctness). Consequently, the reliability of rule-based query optimization will tend to diminish as both the expressiveness of query languages and complexity of the underlying data models increase.

This has motivated members of the Advanced Database Systems Laboratory at our institution to develop a refinement calculus that enables a formal specification of rewrite rules used in current relational and object-oriented optimization technology. This essay reports on an experiment to apply this calculus to capture the intentions underlying a rule used in an optimizer for an experimental object-oriented database system, also developed in our laboratory, and then to attempt proving the validity of this rule. Perhaps most significantly, we learned from this experiment:

(1) that our original informal understanding of the intentions underlying the rule was incorrect, and (2) that our first few attempts at a formal specification of this rule were not valid.

We believe that this constitutes clear evidence that the issue of rewrite rule validity for existing query optimization technology has now become crucial in achieving essential levels of reliability in database systems.
Report On Verifying a Query Optimizer: A Correctness Proof for a Real-World Query Rewrite Rule (PDF) Compressed DVI:
On Verifying a Query Optimizer: A Correctness Proof for a Real-World Query Rewrite Rule (DVI.Z)
CS-94-40
Title Fast Inverted Indexes with On-Line Update
Authors C.L.A. Clarke, C.L.A., Cormack, G.V. and Burkowski, F.J.
Abstract We describe data structures and an update strategy for the practical implementation of inverted indexes. The context of our discussion is the construction of a dedicated index engine for a distributed full-text information retrieval system, but the results have wider application. Retrieval operations require a single disk access per query term. The online update strategy guarantees the consistency of on-disk data structures. Index compression integrates smoothly.
Date November 1994
Report Fast Inverted Indexes with On-Line Update (PDF) Compressed PostScript:
Fast Inverted Indexes with On-Line Update (GZIP)
CS-94-39
Title Schema-Independent Retrieval from Heterogeneous Structured Text
Authors C.L.A. Clarke, C.L.A., Cormack, G.V. and Burkowski, F.J.
Abstract We present a query language for searching collections of structured text. Documents within the collection are not required to adhere to a global schema nor are individual documents required to be structured according to any defined schema at all. Nonetheless, queries may directly reference structure across differently formatted documents. We briefly discuss application of the language to multilingual collections, relational databases, text filtering and document analysis.
Date November 1994
Report Schema-Independent Retrieval from Heterogeneous Structured Text (PDF) Compressed PostScript:
Schema-Independent Retrieval from Heterogeneous Structured Text (GZIP)
CS-94-33
Title Using Local Optimization in Surface Fitting
Authors S. Mann
Abstract Local optimization is used to set the free parameters in a triangular surface fitting scheme, resulting in surfaces with better shape. While some of the free parameters can be set to match curvature information, other free parameters are independent of this information.
Date September 1994
Report Picture 1 (TIF), Picture 2 (TIF), Picture 3 (TIF) Using Local Optimization in Surface Fitting (PDF) Compressed PostScript:
Using Local Optimization in Surface Fitting (PS.Z)
CS-94-32
Title Matrix-Nullspace Wavelet Construction
Authors S. Sivalingam
Abstract "Wavelets" have been a very popular topic of conversation in many scientific and engineering gatherrings these days. Some view wavelets as a new basis for representing funcitons, some consider it a technique for time-frequency analysis, and others think of it as a new mathematical subject. All of them are right, since "wavelet theory" is a versatile tool with very rich mathematical content and great potential for applications, such as data compression. On the other hand polynomial spline functions are among the simplest functions for both computational and implementational purposes. Hence, they aer most atttractive for analyzing and constructing wavelet.

This thesis explorees a simple, general tool for constructing wavelets from "box splines," which are natural generalization of B-splines. This tool involves use of inner product, a matrix transformation, an associated homogeneous system of equations and the determination of null space. This tool is applicable for both univariate and multivariate settings.
Date September 1994
Report Matrix-Nullspace Wavelet Construction (PDF) Compressed PostScript:
Matrix-Nullspace Wavelet Construction (PS.Z)
CS-94-30
Title An Algebra for Structure Text Search and A Framework for its Implementation
Authors C.L.A. Clarke, G.V. Cormack, and F. Burkowski
Abstract A query algebra is presented that expresses searches on structured text. In addition to traditional full-text boolean queries that search a pre-defined collection of documents, the algebra permits queries that harness document structure. The algebra manipulates arbitrary intervals of text, which are recognized in the text from implicit or explicit markup. The algebra has seven operators, which combine intervals to yield new ones: containing, not containing, contained in, not contained in, one of, both of, followed by. The ultimate result of a query is the set of intervals that satisfy it.

An implementation framework is given based on four primitive access functions. Each access function finds the solution to a query nearest to a given position in the database. Recursive definitions for the seven operators are given in terms of these access functions. Search time is at worst proportional to the time required to solve the elementary terms in the query. Inverted indices yield search times that compare favourably to those for full-text boolean searches.
Date September 1994
Report An Algebra for Structure Text Search and A Framework for its Implementation (PDF) Compressed PostScript:
An Algebra for Structure Text Search and A Framework for its Implementation (GZIP)
CS-94-28
Title Fitting Data of Arbitrary Dimension with B-Splines and Applications to Colour Calibration
Authors B. Hickey
Abstract A fitting system for multidimensional printer gamut data was produced. The resultant B-Spline hyper-volume provides a functional definition of the printer's output capabilities. Additional system features determine the closest point on a fitted hyper-surface to a point on its exterior. This permits the optimal reproduction of all colours, including those not precisely attainable by an output device. Visualization is used to determine fit quality based on characteristics such as shape and point interpolation. This fit provides a solution to the problem of producing the best printer output of a screen image.
Date August 1994
Report Fitting Data of Arbitrary Dimension with B-Splines and Applications to Colour Calibration (PDF) Compressed PostScript:
Fitting Data of Arbitrary Dimension with B-Splines and Applications to Colour Calibration (GZIP)
CS-94-27
Title Spatial Template: Recognition, Learning, Complexity and Implementation
Authors S. Woods
Abstract This report details three aspects of work-in-progress involving the automatic or interactive recogintion of spatial templates using constraint satisfaction techniques. The first section discusses the incorporation of information about template models acquired through interactive search for template instances into updated models; a preliminary study the complexity of the spatial template recognition problem and determination of key problem aspects which may most immediately affect this complexity; and an evaluation of the applicability of certain recent attempts to apply a general constraint satisfaction strategy to real problems to the task of recognizing spatial template instances.
Date August 1994
Report Spatial Template: Recognition, Learning, Complexity and Implementation (PDF) Compressed PostScript:
Spatial Template: Recognition, Learning, Complexity and Implementation (GZIP)
CS-94-23
Title Computing the Principal Branch of log-Gamma
Authors D.E.G. Hare
Abstract The log-Gamma function is an important special function of mathematicsm and its principal branch is required in many applications. We develop here the mathematics required to evaluate the principal branch to arbitrary precision, including a new bound for the error iun Stirling's asumptotic series. We conclude with a discussion of the implementation of the princial branch of the log-Gamma funciton in the Maple symboluc algebra sustem, starting with version V Release 3.
Date May 1994
Report Computing the Principal Branch of log-Gamma (PDF) Compressed DVI:
Computing the Principal Branch of log-Gamma (DVI.Z)
CS-94-13
Title Feature Oriented Composition of B-Spline Surfaces
Authors C. Barghiel
Abstract Detailed features are added to composite spline surfaces in a mutil-layered fashion by means of an efficient displacement scheme. The feature orientation is arbitrary, and the underlying domains may be partially overlapping and non-linearly transformed. By mapping only the control vertices, defined as displacement vectors in a diffuse co-ordinate system, we can manipulate the pasted elements in real-time, independently or as a whole.

The procedure, known as pasting, is more than a refinement instrument. It makes possible the rendering of a surface composition selectively, and this expedites the rendering process. It can be used to model surfaces by interactively changing displacement, control vertices, or the domain layout. Base surfaces may serve as sliding paths for pasted clusters whose shape and motion are determined by the underlying topography, resulting in an organic motion effect. Pasting also applies to higher-dimension entities, which may incorporate non-geometric components, such as colour, opacity or brightness.
Date March 1994
Report Feature Oriented Composition of B-Spline Surfaces (PDF) Compressed PostScript:
Feature Oriented Composition of B-Spline Surfaces (PS.Z)
CS-94-11
Title Transaction Scheduling in Dynamic Composite Multidatabase Systems
Authors D.P. Bradshaw, P.-A. Larson and J. Slonim
Abstract Multidatabase systems based on a single monolithic multidatabase server are not realistic. Their performance and administration do not scale with increases in the radius of service or the number of component databases under their control. We propose that a composite multidatabase architecture that consists of multiple, possibly heterogeneous, peer multidatabase servers distributed on a communications network is inevitable. Global transactions should be able to span multiple multidatabase servers, sometimes forcing multidatabase servers to act as component database systems. Particular focus is given to the problem of guaranteeing the correct execution of interleaving global transactions across multiple multidatabase systems. Correctness is based on global serializability. Three algorithms for maintaining global serializ- ability through transaction ordering during dynamic multidatabase composition are proposed. We examine the restrictions of these algorithms and the scalability of their performance.

Keywords:multidatabase composition, serializability, concur- rency control, rigorous scheduling, timestamp ordering.
Date March 1994
Report Transaction Scheduling in Dynamic Composite Multidatabase Systems (PDF) Compressed PostScript:
Transaction Scheduling in Dynamic Composite Multidatabase Systems (PS.Z)
CS-94-10
Title Parallel Program and Asynchronous Circuit Design
Authors J.C. Ebergen, J. Segers and I. Benko
Abstract Asynchronous circuit design is a beautiful application area for any formalism that can reason about parallelism. By means of two small, but challenging, exercises we illustrate the similarities and differences between parallel program and asynchronous circuit design. The exercises are simple to state and have many solutions, which are sometimes surprisingly efficient. They all illustrate many aspects of asynchronous circuit design. For each exercise we present several solutions, which are analyzed with respect to delay assumptions, safety, progress, and performance issues. We also mention some open problems.
Date May 1994
Comments These notes are a revision of the lectures presented at the BANFF VII Workshop on Asynchronous Hardware Design, August 28 - Sept. 3, 1993. The proceedings of this workshop is due to appear later in 1994.
Report Parallel Program and Asynchronous Circuit Design (PDF) Compressed PostScript:
Parallel Program and Asynchronous Circuit Design (PS.Z)
CS-94-09
Title Modelling Qualitative and Quantitative Timing Properties of Real-Time Systems in the Z Notation
Authors R.Iorgulescu, J.M. Atlee and C.J.P. Lucena
Date February 1994
Report Only available in printed format
CS-94-03
Title Some Numerical Results on Algorithms for Sturm-Liouville Problems
Authors X.R. Ji
Abstract For the numerical solution of Sturm-Liouville eigenvalue problems, finite difference methods and Prüfer methods are two kinds of popular methods. However, the conditions under which each method is more efficient are not obvious. The experimental results reported in this paper show: (1) The relative efficiency of the methods depend on the desited accuracy; (2) Finite difference methods, with correction techniques, remain effective even for eigenvalues with higher oscillation number.
Date January 1994
Report Some Numerical Results on Algorithms for Sturm-Liouville Problems (PDF) Compressed DVI:
Some Numerical Results on Algorithms for Sturm-Liouville Problems (DVI.Z)
CS-94-02
Title On the Solution of Mathematical Modeling for the Belousov-Zhabotinskii Reaction
Authors X.R. Ji
Date January 1994
Report On the Solution of Mathematical Modeling for the Belousov-Zhabotinskii Reaction (PDF) Compressed DVI:
On the Solution of Mathematical Modeling for the Belousov-Zhabotinskii Reaction (DVI.Z)
CS-94-01
Title The Grail Papers
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.0 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, and the man pages for each of Grail's filters.
Date March 1994
Report

Adobe PDF:

Compressed PostScript: