| 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: | ||