1994 Technical Reports | SCS | UW
[Please remove <h1>]
| 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 |