# [Please remove <h1>]

<1993 | 1995> |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed DVI |

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 on-line update strategy guarantees the consistency of on-disk data structures. Index compression integrates smoothly. | |||

Date | November 1994 | |||

Report | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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, Picture 2, Picture 3 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 colors, 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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

CS-94-23 | ||||
---|---|---|---|---|

Title | Computing the Principal Branch of log-Gamma | |||

Authors | D.E.G. Hare | |||

Abstract | The log-Gammafunction
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 | Adobe PDF | Compressed DVI |

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 coordinate system, we can manipulate the pasted elemetns
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 comppsition 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 surrfaces 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 compoments, such as color, opacity or brightness. |
|||

Date | March 1994 | |||

Report | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

CS-94-02 | ||||
---|---|---|---|---|

Title | On the Solution of Mathematical Modeling for the Belousov-Zhabotinskii Reaction | |||

Authors | X.R. Ji | |||

Date | January 1994 | |||

Report | Adobe PDF | Compressed PostScript |

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: intro, man, programmer, user | Compressed PS:intro, man, programmer, user |

<1993 | 1995> |