| CS-96-46 | ||||
|---|---|---|---|---|
| Title | Colour and Reflectance in Image Synthesis | |||
| Authors | T. Pflaum | |||
| Abstract |
In
recent
years
substantial
research
has
been
done
on
physically
based
image
synthesis,
which
includes
the
algorithms
used
to
create
synthetic
images
using
models
and
algorithms
based
on
the
underlying
physics
of
light.
The
work
presented
in
this
thesis
focuses
on
two
particular
aspects
of
image
synthesis
that
have
not
gained
much
attention
in
the
past:
how
to
represent
colour
and
how
to
describe
the
reflection
of
light
by
surfaces. A simulation system is presented that takes a model of the micro structure of a surface and creates a representation of the bidirectional reflectance function (BRDF) of a surface having that micro structure. In addition, a technique is presented that creates a colour space, used for rendering, that is adapted to the surface colours actually appearing in the scene. | |||
| Date | December 1996 | |||
| Report | Colour and Reflectance in Image Synthesis (PDF) |
Compressed
PostScript: Colour and Reflectance in Image Synthesis (PS.Z) | ||
| CS-96-45 | ||||
|---|---|---|---|---|
| Title | A Simple, General and Efficient Implementation of Geometric Operators and Predicates | |||
| Authors | E. Chan and J.N.H. Ng | |||
| Abstract | Shape and location of objects in a spatial database are commonly represented by geometric data such as points, lines and regions. Numerous geometric operators and predicates have been proposed for spatial database systems. Existing work on their implementation concentrate on individual operators and predicates. This approach makes the realization of geometric operators and predicates in a spatial database system difficult since they are diverse and their implementation in general are complex. In this paper, we present a simple plane-sweep algorithm that can be easily modified to realizeefficiently a set of frequently used line-region and region-region geometric operators and predicates. The design of this unified algorithm is based on the observation that the covering of elementary regions along the sweep line are updated locally and the implementation of these operators and predicates differ only with the output actions at an intersection point. Any geometric operator or predicate, the output of which can be determined by examing incident edges and covering information at intersection pints, can be implemented easily with the algorithm. To demonstrate its generality, extendibility, simplicity and efficiency, we concentrate on several popular geometric operators and predicates. All these operators and predicates can be realized in O((N+1) logN) time in the worst case, where N is the number of edges in the operands and I is the number of intersection pairs. The proposed algorithms is fully implemented in C++ and is tested on a Sun workstation. Although the paper focuses on operators and predicates involving at most two regions, this algorithm can be generalized nicely to r regions, where r>2. We describe what changes are needed to make to the basic algorithm to accommodate this generalization. | |||
| Date | November 1996 | |||
| Report | A Simple, General and Efficient Implementation of Geometric Operators and Predicates (PS) | |||
| CS-96-44 | ||||
|---|---|---|---|---|
| Title | Querying and Visualization of Geometric Data | |||
| Authors | E. Chan and J.M.T. Wong | |||
| Abstract | This paper describes the retrieval, browsing and visualization of data for a spatial database system developed at the University of Waterloo. The prototype, called QL/G, suppports geometric data types like general regions, lines and points as built-in data types. A Graphical User Inter- face (GUI), written in X/Motif and a persistent version of C++, is provided for users as an effective tool for querying and visualizing data retrieved. The interface is simple, user-friendly and flexible, and provides the necessary functionality identified in existing literature for geographic applications. | |||
| Date | November 1996 | |||
| Report | Querying and Visualization of Geometric Data (PS) | |||
| CS-96-43 | ||||
|---|---|---|---|---|
| Title | The GUI For A Spatial Database Management System | |||
| Authors | E. Chan, J.M.T. Wong, P.Y. Abbott and S. Tan | |||
| Abstract | This paper documents the functionality provided by a spatial database management system (SDBMS) developed at the University of Waterloo. The prototype,called QL/G, supports data types. The functionality is described through the Graphical User Interface (GUI) provided by the system. The user interface component is an especially important part of a SDBMS. In particular, a SDBMS should provide a convenient front-end for definition, entry, visualization and manipulation of spatial data. The system should also address the complex issue of spatial processing and analysis. The GUI of QL/G is designed with the above objective in mind. The interface is simple, user-friendly and flexible, and yet provides the user with the necessary functionality identified in existing literature for geographic applications. | |||
| Date | November 1996 | |||
| Report | The GUI For A Spatial Database Management System (PS) | |||
| CS-96-42 | ||||
|---|---|---|---|---|
| Title | Symbolic Computation Group Annual Report 1996 | |||
| Authors | Symbolic Computation Group | |||
| Abstract |
The
Symbolic
Computation
Group
has
as
its
primary
goal
the
research
and
development
of
algorithms
for
computer
algebra,
including
both
symbolic
computation
and
hybrid
symbolic-numeric
computation.
The
algorithms
developed
are
incorporated
into
the
Maple
computer
algebra
system. Particular areas of research and development which have been targeted during the past year include symbolic integration, computing solutions of ordinary and partial differential equations (both symbolically and numerically), extended-precision numerical evaluation of special functions, facilities for handling piecewise functions, pattern matching, matrix computations, and tensor computations. | |||
| Date | November 1996 | |||
| Report | Symbolic Computation Group Annual Report 1996 (PDF) |
Compressed
PostScript: Symbolic Computation Group Annual Report 1996 (PS.Z) | ||
| CS-96-40 | ||||
|---|---|---|---|---|
| Title | Grammars++ for Modelling Information in Text | |||
| Authors | A. Salminen and F.Wm. Tompa | |||
| Abstract |
Grammars
provide
a
convenient
means
to
describe
the
set
of
valid
strings
in
a
language,
and
thus
they
seem
natural
for
describing
the
set
of
valid
instances
in
a
text
database.
It
is
well-known
that
a
given
language
can
be
described
by
many
grammars,
and
similarly
text
database
designers
have
a
choice
of
grammar
for
specifying
valid
documents.
This
flexibility
can
be
exploited
to
provide
information
modelling
capability
by
designing
productions
in
the
grammar
to
represent
entities
and
relationships
of
interest
to
the
database
applications.
Additional
constraints
can
be
specified
by
attaching
predicates
to
selected
non-terminals
in
the
grammar. In this paper, we formalize and illustrate the use of extended grammars for text databases. When used for database definition, grammars can provide the functionality that users have come to expect of database schemas. Extended grammars can also be used to specify database manipulation, including query, update, view definition, and index specification. | |||
| Date | November 1996 | |||
| Report | Grammars++ for Modelling Information in Text (PDF) |
Compressed
PostScript: Grammars++ for Modelling Information in Text (PS.Z) | ||
| CS-96-39 | ||||
|---|---|---|---|---|
| Title | The Management of Data, Events, and Information Presentation for Network Management | |||
| Authors | M. Hasan | |||
| Abstract |
The
purpose
of
a
network
management
(NM)
system
is
to
monitor
and
control
a
network.
Monitoring
and
control
functions
entail
deal-
ing
with
large
volumes
of
data,
events,
and
the
presentation
of
relevant
information
on
a
management
station.
The
management
of
data,
events,
and
information
presentation
pose
a
major
research
and
development
challenge.
In
this
thesis
we
focus
on
data
and
events
management
and
information
presentation
issues
of
an
NM
system.
Existing
NM
systems
either
use
traditional
da-
tabase
systems
which
are
not
well
suited
for
a
NM
system
or
they
lack
intelligent
event
and
information
presentation
management
frameworks.
None
of
the
systems
provide
a
unified
framework
for
managing
data,
events
and
information
presentation
tasks
on
an
NM
station. We believe that the complexities of network management posed by the issues mentioned above can be reduced substantially by ex- ploiting, enhancing and combining the features of new generation database systems, such as, active temporal and database visu- alization systems. An active database system where active behaviors are specified as Event-Condition-Action (ECA) rules is a suitable framework for NM data and events management. The Hy+ database visualization system with its sophisticated abstrac- tion and visualization capabilities is well-suited to meet the requirements of NM information presentation. By viewing the network as a conceptual global database, the network management functions can be specified as declarative database manipulation operations and Event-Condition-Action (ECA) rules. But the facilities provided by existing active database systems are not enough for an NM system. For example, NM events manage- ment requires sophisticated systems for event correlation based on domain knowledge on the events and other relationships, such as, structural and temporal relationships between events. A number of existing active temporal database systems provide sup- port for a composite event specification language (CESL) (used in the E part of an ECA rule) that allows one to relate events in the temporal dimension. But these languages lack features that otherwise are required by certain applications. In this thesis we propose a CESL, called CEDAR that extends the powers of existing languages. CEDAR allows a user to specify various event management functionalities in the NM domain, which otherwise is difficult or impossible to specify in existing languages. An implementation model of the language operators using Colored Petri Nets is also proposed. We also propose a model of a network management database system that incor- porates CEDAR with an active database system, and various other features required by NM functionalities, such as, event defini- tion, sampling or polling, etc. The resulting system is in- tegrated with the Hy+ database visualization system. The deductive capability provided by the Hy+ system further enhances the power of data and events management, and information presen- tation capabilities. | |||
| Report | Table of Contents (PDF) | The Management of Data, Events, and Information Presentation for Network Management (PDF) |
Compressed
PostScript: The Management of Data, Events, and Information Presentation for Network Management (PS.Z) | |
| CS-96-38 | ||||
|---|---|---|---|---|
| Title | Distributed Scientific Data Processing Using the DBC | |||
| Authors | J. Duff, K. Salem and M. Livny | |||
| Abstract | The Distributed Batch Controller (DBC) supports scientific batch data processing. The DBC distributes batch jobs to one or more pools of workstations and monitors and controls their execution. The pools themselves may be geographically distributed, and need not be dedicated to processing batch jobs. We describe the use of the DBC in a large scientific data processing application, namely the generation of atmospheric temperature and humidity profiles from satellite data. This application shows that the DBC can be an effective platform for distributed batch processing. It also highlights several design and implementation issues that arise in distributed data processing systems. | |||
| Date | November 1996 | |||
| Report | Distributed Scientific Data Processing Using the DBC (PDF) |
Compressed
PostScript: Distributed Scientific Data Processing Using the DBC (PS.Z) | ||
| CS-96-36 | ||||
|---|---|---|---|---|
| Title | Application of a Stochastic Grammatical Inference Method to Text Structure | |||
| Authors | M. Young-Lai | |||
| Abstract | For a document collection where structural elements are identified with markup, it is sometimes necessary to retrospectively construct a grammar that constrains element nesting and ordering. An approach to this problem is described based on a grammatical inference method that generates stochastic finite automata. Improvements are made to the algorithm based on experiments with data from the Oxford English Dictionary. The problems of understanding results and interactively adjusting the algorithm's parameters are also considered. | |||
| Date | October 1996 | |||
| Comments | This technical report is a reprint of my Master's thesis. | |||
| Report | Application of a Stochastic Grammatical Inference Method to Text Structure (PDF) |
Compressed
PostScript: Application of a Stochastic Grammatical Inference Method to Text Structure (GZIP) | ||
| CS-96-35 | ||||
|---|---|---|---|---|
| Title | Designing Subdivision Surfaces through Control Mesh Refinement | |||
| Authors | H. Sheikh | |||
| Abstract |
I
present
a
technique
for
designing
subdivision
surfaces
through
the
repeated
process
of
refining
the
control
mesh
of
the
surface.
The
refinement
is
performed
using
the
surfaces
subdivision
algorithm.
An
abstract
structure
for
subdivision
surfaces
is
developed
that
involves
the
control
mesh
and
the
subdivision
algorithm.
This
structure
is
used
to
build
a
generic
editor
that
assists
in
the
design
of
surfaces
represented
by
classes
of
control
meshes
and
subdivision
algorithms. The theory of subdivision surfaces, in particular, tensor product cardinal splines and box splines is described in detail. From the theory, subdivision algorithms for these surfaces are constructed and then used to create Refiners. The concept of trimming these surfaces is also introduced to aid in rendering of the surface. Several C++ spline classes used in the implementation are described. The subdivision surface editor uses these classes and Open Inventor to provide a prototype 3D surface design, manipulation and editing environment. | |||
| Date | September 1996 | |||
| Comments | My thesis supervisor was Richard Bartelswho is probably the best person to get in touch with regarding current progress with the thesis. | |||
| Report | Designing Subdivision Surfaces through Control Mesh Refinement (PDF) |
Compressed
PostScript: Designing Subdivision Surfaces through Control Mesh Refinement (PS.Z) | ||
| CS-96-34 | ||||
|---|---|---|---|---|
| Title | Using Inverted Lists to Match Structured Text | |||
| Authors | S. Li | |||
| Abstract |
Inverted
files
have
long
been
used
as
an
effective
way
to
implement
secondary
key
retrieval
in
traditional
database
systems.
For
information
retrieval
systems,
postings
lists
use
a
similar
inverted
file
structure
to
accommodate
the
special
characteristics
of
text
data. This thesis explores extensions to these ideas for structured text databases, especially concerning direct containment of structures. Two kinds of data structures are presented, and for each structure, six basic operations are described and analyzed. Two complex forms of query expressions concerning hierarchical and lateral relationships between text structures are also examined. Examples are presented to demonstrate the effect on performance of each data structure. | |||
| Date | September 1996 | |||
| Comments | This report is a reprint of a thesis that embodies the results of research done in partial fulfillment of the requirements for the degree of Master of Mathematics in Computer Science at the University of Waterloo. | |||
| Report | Using Inverted Lists to Match Structured Text (PDF) |
Compressed
PostScript: Using Inverted Lists to Match Structured Text (PS.Z) | ||
| CS-96-33 | ||||
|---|---|---|---|---|
| Title | A Method of Program understanding Using Constraint Satisfaction for Software Reverse-Engineering | |||
| Authors | S. Woods | |||
| Abstract |
The
process
of
understanding
a
source
code
in
a
high-level
programming
language
is
a
complex
cognitive
task.
The
provision
of
helpful
decision
aid
subsystems
would
be
of
great
benefit
to
software
maintainers.
Given
a
library
of
program
plan
templates,
generating
a
partial
understanding
of
a
piece
of
software
source
code
can
be
shown
to
correspond
to
the
construction
of
mappings
between
segments
of
the
source
code
and
particular
program
plans
represented
in
a
library
of
domain
source
programs
(plans).
These
mappings
can
be
used
as
part
of
the
larger
task
of
reverse
engineering
source
code,
to
facilitate
many
software
engineering
tasks
such
as
software
reuse,
and
for
program
maintenance. We present a novel model of program understanding using constraint satisfaction. The model composes a partial global picture of source program code by transforming knowledge about the problem domain and the program structure into constraints. These constraints facilitate the efficient construction of mappings between code and library knowledge. Under this representational framework, earlier heuristic approaches to program understanding may be unified, contrasted, and compared. We describe an empirical study which demonstrates the feasibility of our model in the program understanding subtask of partial local explanation. In addition, we incorporate this local model into the larger task of combining these local explanations into a coherent global picture of the code. While many heuristic global models are possible, we describe an encompassing structure and demonstrate, through a careful depiction of the algorithm and several domain examples, how constraint satisfaction offers a rich paradigm for the larger task of reverse engineering source code, to exploiting both library and program structural constraint information. One primary advantage of the constraint satisfaction paradigm (CSP) is its generality; many previous program understanding efforts can be more easily compared. Another advantage is the improvement in search efficiency using various heuristic techniques in CSP. | |||
| Date | September 1996 | |||
| Report | A Method of Program understanding Using Constraint Satisfaction for Software Reverse-Engineering (PDF) |
Compressed
PostScript: A Method of Program understanding Using Constraint Satisfaction for Software Reverse-Engineering (PS.Z) | ||
| CS-96-32 | ||||
|---|---|---|---|---|
| Title | World Space User Interface for Surface Pasting | |||
| Authors | L.K.Y. Chan | |||
| Abstract | Surface pasting is a composition method that applies B-spline surfaces, called features, to any number of other B-spline surfaces, called base surfaces, in order to add details on the base surfaces. The locations as well as the size of the features are determined by transformations of feature domains. By modifying the domain layout of pasted surfaces, we can manipulate the appearances of features interactively in a Domain Space User Interface. However, this domain user interface is inadequate because the user cannot interact with the three-dimensional model directly. In this thesis, I propose a World Space User Interface that attempts to map three-dimensional user actions to two-dimensional domain operations and aims at providing a more intuitive and efficient modelling interface for surface pasting. | |||
| Date | September 1996 | |||
| Report | World Space User Interface for Surface Pasting (PDF) |
Compressed
PostScript: World Space User Interface for Surface Pasting (PS.Z) | ||
| CS-96-31 | ||||
|---|---|---|---|---|
| Title | Query Based Stemming | |||
| Authors | E. Tudhope | |||
| Abstract | In information retrieval the relevancy of a document to a particular query is based on a comparison of the terms appearing in the query with the terms appearing in the document. Morphological variants of words (i.e. locate, locates, located, locating) often carry the same or similar meaning. Such terms should be considered equivalent for information retrieval purposes. Stemming is a simple application of natural language processing that is commonly applied at index time to reduce morphological variants to a common root form. This report first examines several approaches to stemming. Some of the problems associated with the use of stemming as a query expansion technique are then discussed. The construction of equivalence classes of words for stemming at query time is presented as a possible alternative method to address some of these problems. | |||
| Date | September 1996 | |||
| Report | Appendix | Query Based Stemming (PDF) |
Compressed
PostScript: Query Based Stemming (PS.Z) | |
| CS-96-30 | ||||
|---|---|---|---|---|
| Title | Finding the Loneliest Point | |||
| Authors | K.Y.Yeung | |||
| Abstract |
We
study
the
following
problem
which
finds
application
in
solving
equations.
Given
a
Euclidean
domain,
there
are
two
operations,
INSERT
and
ISOLATE.
INSERT
adds
points
to
the
domain.
ISOLATE
returns
a
point
in
the
domain
which
is
satisfactorily
far
from
the
points
already
inserted
in
the
domain. The objective is to perform INSERT and ISOLATE in constant amortized time per operation, linear space and a constant worst case ratio. Worst case ratio measures how far the answer from ISOLATE differs from the best possible answer. We concentrate on the case with a two dimensional domain. The basic approach is to divide the domain into geometric shapes and build a hierarchy of that shape. We have studied the three regular polygons that tile a given two dimensional domain: squares, hexagons and triangles. It turns out that the worst case ratio is smaller when the domain is divided into hexagons than when the domain is divided into squares, the worst case ratio for squares is in turn smaller than that of the triangles. We have also explored other techniques to improve the worst case ratio while keeping constant amortized running time per operation and linear space. We have explored overlapping, embedding (or diamonds), and multiple grids. The worst case ratio can be improved further when these techniques are combined. We have also shown that the square technique can be extended to cubes in a three dimensional domain. | |||
| Date | August 1996 | |||
| Report | Finding the Loneliest Point (PDF) |
Compressed
PostScript: Finding the Loneliest Point (PS.Z) | ||
| CS-96-29 | ||||
|---|---|---|---|---|
| Title | Algorithms from Blossoms | |||
| Authors | S. Mann | |||
| Abstract | Blossoming is a theoretical technique that been used to develop new CAGD theory. However, once we have developed this theory, we need to devise algorithms to implement it. In this paper, I will discuss converting blossoming equations into code, noting techniques that can be used to develop efficient algorithms. These techniques are illustrated by considering the operations of basis conversion and polynomial composition. | |||
| Date | October 1996 | |||
| Report | Algorithms from Blossoms (PDF) |
Compressed
PostScript: Algorithms from Blossoms (PS.Z) | ||
| CS-96-28 | ||||
|---|---|---|---|---|
| Title | Robust Numberical Methods for PDE Models of Asian Options | |||
| Authors | R. Zvan, P.A. Forsyth and K. Vetzal | |||
| Abstract | We explore the pricing of Asian options by numerically solving the associated partial differential equations. We demonstrate that numerical PDE techniques commonly used in finance for standard options are inaccurate in the case of Asian options and illustrate modifications which alleviate this problem. In particular, the usual methods generally produce solutions containing spurious oscillations. We adapt flux limiting techniques originally developed in the field of computational fluid dynamics in order to rapidly obtain accurate solutions. We show that flux limiting methods are total variation diminishing (and hence fre eof spurious oscillations) for non-conservative PDEs such as those typically encountered in finance, for fully explicit, and fully and partically implicit schemes. We also modify the van Leer flux limiter so tht the second-order variation diminishing property is preserved for non-uniform grid spacing. | |||
| Date | September 1996 | |||
| Report | Robust Numberical Methods for PDE Models of Asian Options (PDF) |
Compressed
PostScript: Robust Numberical Methods for PDE Models of Asian Options (PS.Z) | ||
| CS-96-27 | ||||
|---|---|---|---|---|
| Title | Aposteriori Error Estimation for CFD | |||
| Authors | B. van Straalen | |||
| Abstract | A technique for numerically estimating the discretization error in upwind based finite volume fluid flow simulation was developed. The technique is based on residual estimation, followed by solving the global error equation over the computational domain. One and two dimensional analysis of the error estimation process was performed for a simple homogeneous advection-diffusion equation. The technique was then extended to encompass the laminar Navier-Stokes equations. The effectiveness of the technique was investigated for flow over a two dimensional backward-facing step. The results show promise for future implementations of effective and practical error estimation. | |||
| Date | July 1996 | |||
| Report | Aposteriori Error Estimation for CFD (PDF) |
Compressed
PostScript: Aposteriori Error Estimation for CFD (PS.Z) | ||
| CS-96-25 | ||||
|---|---|---|---|---|
| Title | On Line Target Searching in Bounded and Unbounded Domains | |||
| Authors | A. Lopez-Ortiz | |||
| Abstract |
In
this
work
we
study
the
problem
of
a
robot
searching
for
a
target
on
bounded
and
unbounded
domains,
specifically
in
one
and
two
dimensions.
We
present
some
relevant
results
in
the
field,
and
within
this
framework,
the
contributions
of
this
work.
We
show
that
one-sided
searches
on
the
real
line
have
an
average
competitive
ratio
of
9
and
we
apply
this
result
for
the
case
of
known
destination
searches
on
G-street
polygons.
For
this
class
of
polygons
we
also
show
that
the
best
known
upper
bound
of
sqrt(82)
is
indeed
optimal
for
the
case
of
unknown
destination
searches.
For
orthogonal
street
polygons
we
prove
that
knowing
the
location
of
the
destination
does
not
reduce
the
competitive
ratio. We present the first robust algorithm for searches inside street polygons under navigational errors, as well as for other important classes of impaired robots such as robots lacking triangulation and depth measurement mechanisms. In particular, we propose a \pi+1-competitive strategy which is robust under navigational error, and equally efficient for oblivious robots. We also present an 1.92-competitive strategy which does not require depth perception from the robot. We also give the best-known strategy for searching inside street polygons, at a competitive ratio of 1.76. This significantly improves over the best previously known ratio of 2.8. We give the first non-trivial lower bound for searching and walking into the kernel of a polygon. We provide upper and lower bounds for searching for a target inside street polygons. These results are the first constant competitive ratio strategies inside a class of polygons which is independent of the location of the start and target points. We also prove negative results regarding the optimality of several well-known family of strategies for searching inside simple polygons. In particular we show that Kleinberg's strategy is 2.6-competitive, and that continuous bisector, which is in many respects a good strategy, is at least 1.68-competitive. Lastly we show that any strategy which does not respond to the absence of new extreme points has a competitive ratio strictly larger than sqrt(2). | |||
| Date | July 1996 | |||
| Report | On Line Target Searching in Bounded and Unbounded Domains (PDF) |
Compressed
PostScript: On Line Target Searching in Bounded and Unbounded Domains (PS.Z) | ||
| CS-96-24 | ||||
|---|---|---|---|---|
| Title | Double-Blind Scores of an Object-Oriented Modeling Survey | |||
| Authors | R.S.C. Yiu | |||
| Date | June 1996 | |||
| Report | Double-Blind Scores of an Object-Oriented Modeling Survey (PDF) |
Compressed
PostScript: Double-Blind Scores of an Object-Oriented Modeling Survey (GZIP) | ||
| CS-96-23 | ||||
|---|---|---|---|---|
| Title | Optimal adaptive polygonal approximation of parametric surfaces | |||
| Authors | L. Velho and L.H. de Figueiredo | |||
| Date | July 1996 | |||
| Report | Only available in printed format | |||
| CS-96-22 | ||||
|---|---|---|---|---|
| Title | Spline-Based Tools for Conventional and Reflective Image Reproduction | |||
| Authors | I.E. Bell | |||
| Date | May 1996 | |||
| Report | Only available in printed format | |||
| CS-96-21 | ||||
|---|---|---|---|---|
| Title | Length of Finite Pierce Series: Theoretical Analysis and Numerical Computations | |||
| Authors | V. Keselj | |||
| Abstract |
Any real number x from the interval (0,1] can be represented as
a unique Pierce series
1 1 1
-- - --- + ---- - ...
q1 q1*q2 q1*q2*q3
where {q1, q2, q3, ...} is an increasing sequence of positive
integers. The series is finite if and only if the number x is
rational. This paper discusses the length of the series and the
final results are a new upper bound (Theorem 2) and a new lower
bound (Theorem 3) on the length.
The numerical computations concerning the length are done by
computer and the algorithms used and results are presented. The
numerical results are an extension to the tables previously
published.
| |||
| Date | September 1996 | |||
| Report | Length of Finite Pierce Series: Theoretical Analysis and Numerical Computations (PDF) |
Compressed
PostScript: Length of Finite Pierce Series: Theoretical Analysis and Numerical Computations (PS.Z) | ||
| CS-96-20 | ||||
|---|---|---|---|---|
| Title | The Empirical Derivation of a Design Space and Design Rules for Software Architecture | |||
| Authors | K. Reddy | |||
| Abstract | The empirical derivation of a design space and design rules for software architecture is presented. The research presented in this paper represents and effort to begin capturing what is known by experienced designers about designing for non-functional qualities, such as performance, portability, reusability etc., in a rigorous, statistically validated fashion. The design space and design rules are codified by synthesizing information collected by the administration of a survey to experienced designers of large scale systems. They capture the relationships between six unit operations which are structure transforming mechanisms ubiquitous in software design, and eleven non-functional qualities. Their use enables design for non-functional qualities to occur at an earlier development stage than current practice. The creation, administration and analysis of the survey is presented along with the resultant design space and design rules. | |||
| Date | May 1996 | |||
| Report | Only available in printed format | |||
| CS-96-18 | ||||
|---|---|---|---|---|
| Title | Data Transfer Using Controlled Compression | |||
| Authors | A.Y.D. Cheung | |||
| Abstract | In a scenario in which a large amount of data is to be transferred from one site to another, it is desirable to optimize the throughput of data transfer. There are two transmission options. One option is to compress the data before the transfer, and to decompress them at the receiving site. The other option is to send the data without doing any compression. Ideally, we would like to choose the option that accomplishes the transfer as quickly as possible. This choice is complicated by many factors such as the load of the machines, and the degree of traffic congestion of the network. These factors affect the transmission rate differently depending on whether or not we use compression. This thesis proposes and evaluates two algorithms for automatically determining whether compression should be used. One algorithm is based on sampling past performance with and without compression. The other directly exploits feedback from the network. These algorithms have been implemented and evaluated under different conditions. The evaluation shows that both algorithms can pick the correct mode of data transfer to use in different environments. The algorithm based on network feedback is more complicated and requires tuning to perform well. | |||
| Date | April 1996 | |||
| Report | Data Transfer Using Controlled Compression (PDF) |
Compressed
PostScript: Data Transfer Using Controlled Compression (PS.Z) | ||
| CS-96-17 | ||||
|---|---|---|---|---|
| Title | The DBC: Processing Scientific Data Over the Internet | |||
| Authors | C. Chen, K. Salem and M. Livny | |||
| Abstract | We present the Distributed Batch Controller (DBC), a system built to support batch processing of large scientific datasets. The DBC implements a federation of autonomous workstation pools, which may be widely-distributed. Individual batch jobs are executed using idle workstations in these pools. Input data are staged to the pool before processing begins. We describe the architecture and implementation of the DBC, and present the results of experiments in which it is used to perform image compression. | |||
| Date | March 1996 | |||
| Report | The DBC: Processing Scientific Data Over the Internet (PDF) |
Compressed
PostScript: The DBC: Processing Scientific Data Over the Internet (PS.Z) | ||
| CS-96-15 | ||||
|---|---|---|---|---|
| Title | Overview of GSM: The Global System for Mobile Communications | |||
| Authors | J. Scourias | |||
| Date | March 1996 | |||
| Report | Overview of GSM: The Global System for Mobile Communications (PDF) |
Compressed
PostScript: Overview of GSM: The Global System for Mobile Communications (PS.Z) | ||
| CS-96-14 | ||||
|---|---|---|---|---|
| Title | A Normal Form for Function Rings of Piecewise Functions | |||
| Authors | M.von Mohrenschildt | |||
| Abstract | Computer algebra systems often have to deal with piecewise defined functions, for example, the absolute value function. We present a new approach to this kind of problem. This paper provides a normal form for function rings containing piecewise functions. We give a compiled rule system to compute the normal form of a function. With a normal form, we can decide equality in our function ring. In this ring, we can define supremum and infimum of two functions. In fact we show that the function ring is a compiled lattice. We present a method to solve equalities and inequalities in this function ring. | |||
| Date | March 1996 | |||
| Comments | This paper has been submitted to ISSAC'96. | |||
| Report | A Normal Form for Function Rings of Piecewise Functions (PDF) |
Compressed
PostScript: A Normal Form for Function Rings of Piecewise Functions (PS.Z) | ||
| CS-96-13 | ||||
|---|---|---|---|---|
| Title | Some improvements of a lemma of Rosenfeld | |||
| Authors | F. Boulier | |||
| Abstract |
We
give
two
improvements
of
a
lemma
of
Rosenfeld
which
permit
us
to
optimize
some
algorithms
in
differential
algebra:
we
prove
the
lemma
with
stronger
hypotheses
and
we
demonstrate
an
analogue
of
Buchberger's
second
criterion,
which
avoids
non
necessary
reductions
for
detecting
coherent
sets
of
differential
polynomials.
We
try
also
to
clarify
the
relations
between
the
theorems
in
differential
algebra
and
some
more
widely
known
results
in
the
Groebner
bases
theory. Keywords: Differential algebra. Rewrite systems. Polynomial differential equations. Rosenfeld's lemma. | |||
| Date | April 1996 | |||
| Comments | Submitted to IMACS'96 | |||
| Report | Some improvements of a lemma of Rosenfeld (PDF) | |||
| CS-96-12 | ||||
|---|---|---|---|---|
| Title | A Multicollaborative Push-Caching HTTP Protocol for the WWW | |||
| Authors | Alex Lopez-Ortiz | |||
| Abstract | We propose a caching protocol designed to automatically mirror heavily accessed WWW pages in a distributed and temporal fashion. The proposed caching mechanism differs from proxy type mechanisms in that it caches according to load pattern at the server side, instead of access patterns at the client-side LAN, in a Demand-based Document Dissemination (DDD) system fashion. This type of server initiated caching scheme has been termed push-caching. As well, the proposed caching scheme incorporates topological caching functions. The proposed protocol is orthogonal to other extensions to the HTTP protocol and other caching schemes already in use. | |||
| Date | October 1996 | |||
| Report | A Multicollaborative Push-Caching HTTP Protocol for the WWW (PDF) |
Compressed
PostScript: A Multicollaborative Push-Caching HTTP Protocol for the WWW (PS.Z) | ||
| CS-96-09 | ||||
|---|---|---|---|---|
| Title | Tabular Abstraction, Editing and Formatting | |||
| Authors | X. Yang | |||
| Abstract | This dissertation investigates the composition of high-quality tables with the use of electronic tools. A generic model is designed to support the different stages of tabular composition, including the editing of logical structure, the specification of layout structure, and the formatting of concrete tables. The model separates table's logical structure from its layout structure, which consists of tabular topology and typographic style. The notion of an abstract table, which describes the logical relationships among tabular items, is formally defined and a set of logical operations is proposed to manipulate tables based on these logical relationships. An abstract table can be visualized through a layout structure specified by a set of topological rules, which determine the relative placement of t abular items in two dimensions, and a set of style rules, which determine the final appearance of different items. The absolute placement of a concrete table can be automatically generated by applying a layout specification to an abstract table. An NP-complete problem arises in the formatting process that uses automatic line breaking and determines the physical dimension of a table to satisfy user-specified size constraints. An algorithm has been designed to solve the formatting problem in polynomial time for typical tables. Based on the tabular model, a prototype tabular composition system has been implemented in a UNIX, X Windows environment. This prototype provides an interactive interface to edit the logical structure, the topology and the styles of tables. It allows us to manipulate tables based on the logical relationships of tabular items, regardless of where the items are placed in the layout structure, and is capable of presenting a table in different topologies and styles so that we can select a high-quality layout structure. | |||
| Date | January 1996 | |||
| Report | Tabular Abstraction, Editing and Formatting (PDF) |
Compressed
PostScript: Tabular Abstraction, Editing and Formatting (PS.Z) | ||
| CS-96-07 | ||||
|---|---|---|---|---|
| Title | The Use of a Combined Text/Relational Database System to Support Document Management | |||
| Authors | K.Y. Ng | |||
| Abstract |
In
this
thesis,
we
study
the
problem
of
representing
and
manipulating
a
document
to
facilitate
browsing,
editing,
string/content
searches
and
document
assembly.
| |||
| Date | January 1996 | |||
| Report | The Use of a Combined Text/Relational Database System to Support Document Management (PDF) |
Compressed
PostScript: The Use of a Combined Text/Relational Database System to Support Document Management (PS.Z) | ||
| CS-96-04 | ||||
|---|---|---|---|---|
| Title | Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices | |||
| Authors | A. Storjohann and G. Labahn | |||
| Abstract | This paper presents a new algorithm for computing the Hermite normal form H of an n x m rank m integral matrix A together with a unimodular pre-multiplier matrix U such that UA=H . Our algorithm requires O~(m^(\theta-1) n M(m log ||A||)) bit operations to produce both H and a candidate for U . Here, ||A|| =\max_{ij} |A_{ij}| , M(t) bit operations are sufficient to multiply two t-bit integers, and \theta is the exponent for matrix multiplication over rings: two m x m matrices over a ring R can be multiplied in O(m^\theta) ring operations from R . The previously fastest algorithm of Hafner & McCurley requires O~(m^2 n M(m log ||A||)) bit operations to produce H , but does not produce a candidate for U . Previous methods require on the order of O~(n^3 M(m log ||A||)) bit operations to produce a candidate for U -- our algorithm improves on this significantly in both a theoretical and practical sense. | |||
| Date | January 1996 | |||
| Comments | This paper has been submitted to ISSAC'96. | |||
| Report | Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices (PDF) |
Compressed
PostScript: Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices (PS.Z) | ||
| CS-96-03 | ||||
|---|---|---|---|---|
| Title | Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices | |||
| Authors | A. Storjohann | |||
| Abstract | We present new algorithms for computing Smith normal forms of matrices over the integers and over the integers modulo N . For the case of matrices over Z/(N) , we present an algorithm that computes the Smith form S of an n x m matrix A over Z/(N) in only O(n^\theta m) operations from Z/(N) . Here, \theta is the exponent for matrix multiplication over rings: two n x n matrices over a ring R can be multiplied in O(n^\theta) operations from R . We apply our algorithm for matrices over Z/(N) to get an algorithm for computing the Smith form S of an n x m matrix A over Z in O~(n^(\theta-1) m M(n log ||A||)) bit operations (where ||A|| = max |A_{i,j}| and M(t) bounds the cost of multiplying two t-bit integers). These complexity results improve significantly on the complexity of previously best known Smith form algorithms (both deterministic and probabilistic) which guarantee correctness. | |||
| Date | January 1996 | |||
| Comments | This paper has been submitted to ISSAC'96. | |||
| Report | Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices (PDF) |
Compressed
PostScript: Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices (PS.Z) | ||