2000 Technical Reports | SCS | UW
[Please remove <h1>]
| CS-2000-22 |
| Title |
Finding Patterns in Biological
Sequences |
| Authors |
B. Brejova, C. DiMarco,
T. Vinar, S.R. Hildalgo, G. Holguin and C. Patten |
| Abstract |
In this report we provide
an overview of known techniques for discovery of patterns of biological
sequences (DNA and proteins). We also provide biological motivation, and
methods of biological verification of such patterns. Finally we list publicly
available tools and databases for pattern discovery.
|
| Date |
December 2000 |
| Report |
|
|
Adobe
PDF |
|
| CS-2000-21 |
| Title |
Efficient Evaluation of
Subdivision Surfaces |
| Authors |
E. Hall |
| Abstract |
New algorithms and data
representations are introduced for the efficient evaluation of subdivision
surfaces. The first algorithm presented uses a data structure based on strips
of quadrilaterals to implicitly define adjacency information for mesh faces
through vertex order. This approach reduces memory requirements by a constant
factor in the average case and allows for a fast evaluation scheme. The
next algorithm extends this idea for use in a hardware evaluation setting.
A simple API and protocol for transmitting quadstrips with adjacency information
to hardware is defined. An online algorithm requiring only small constant
storage for a given recursion depth is then used to subdivide each strip. |
| Date |
December 2000 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-20 |
| Title |
The Verification of Hypermedia Design Composition |
| Authors |
Jing Dong, Paulo S. C. Alencar, Donald D. Cowan |
| Abstract |
Developing large-scale software systems by integrating software
components becomes important practice due to the increasing complexity
and size of these software applications. However, the unexpected interactions
among the components of software systems are often the cause of failure
of component-based systems. The analysis of the properties of the components
and their compositons allows us to detect these interactions and correct
the compositon errors. Discovering composition errors early in the development
process can save considerable effort of fixing them downstream. This
paper introduces a rigorous analysis approach based on model checking
to software design compositon. In particular, the analysis goal is to
verify whether properties related to structural, behavioral and evolutionary
aspects of the design component specifications hold when these components
are integrated. We illustrate our approach with a hypermedia case study,
showing how to represent, instantiate and integrate design components,
and how to find design compositon errors using model checking techniques. |
| Date |
|
| Comments |
|
| Report |
|
|
Adobe
PDF |
|
| CS-2000-19 |
| Title |
Solving Inverse Kinematics
Constraint Problems for Highly Articulated Models |
| Authors |
T.K. Ge |
| Abstract |
Given a goal position for the end effector of a highly articulated model,
the task of finding the angles for each joint in the model to achieve the
goal is an inverse kinematics problem. Redundancy of the degrees of
freedom (DOF) can be used to meet secondary tasks such as obstacle avoidance.
Solutions to redundant inverse kinematic problems are well developed. The most
common technique is to differentiate the nonlinear equations and solve a linear
Jacobian matrix system. The pseudoinverse of the Jacobian can be calculated via
a singular value decomposition (SVD). The general SVD algorithm reduces a given
matrix first to a bidiagonal form then diagonalizes it. The iterative Givens
rotations method can also be used in our case, since the new Jacobian is a
perturbation of previous one. Secondary tasks can be easily added to this matrix
system, but it is nontrivial to generalize this problem to a highly redundant model
in a complex environment in the computer graphics context.
For this thesis, I implemented and compared several SVD techniques; and found that
both general and iterative algorithms are of linear time-complexity when solving a
three-row matrix. I also programmed and compared different methods to avoid one or
multiple obstacles.
|
| Date |
December 2000 |
| Report |
Compressed
MPEG |
|
Adobe
PDF |
|
| CS-2000-18 |
| Authors |
A. An |
| Report |
No Report |
| CS-2000-17 |
| Title |
Linear Reductions of Maximum
Matching |
| Authors |
T.C. Biedl |
| Abstract |
In this paper, we give
linear reductions from maximum matching to maximum matching in a special
graph class, such as 3-regular graphs, or biconnected graphs with maximum
degree 3. We also reduce maximum matching in planar graphs to maximum matching
in triangulations with maximum degree 9. Our results imply that rather than
searching for faster maximum matching algorithms general, one should concentrate
on maximum matching algorithms for these special graph classes. |
| Date |
November 2000 |
| Comments |
The paper will appear
at SODA 2001 (Symposium on Discrete Algorithms), and has been submitted
to SIAM Journal on Computing. |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-16 |
| Authors |
P. Ward and D.J. Taylor |
| Date |
number issued October
4th, 2000 |
| Report |
Only available in printed
format
|
| CS-2000-15 |
| Title |
The Direct Manipulation
of Pasted Surfaces |
| Authors |
M. Ma |
| Abstract |
Surface pasting is a method for creating complex composite surfaces
by adding local detail or feature surfaces to a base surface.
Previous surface pasting editors enabled users to paste, translate,
rotate, and resize feature surfaces, but none allowed users to
directly manipulate a surface in the pasting hierarchy. In this
thesis, I propose a multiresolution direct manipulation technique
that allows the user to pick a point on a surface and move it to a
new location and have the shape of the surface change appropriately.
My method provides a more flexible modelling paradigm for pasted
surfaces by allowing the user to pick both the new location of the
selected point and the granularity of the change that is applied to
the composite surface. |
| Date |
September 2000 |
| Comments |
CS-2000-15.mpg.gz - gzipped
MPEG demonstrating some of the direct manipulation techniques
CS-2000-15.mov.gz - gzipped Quicktime movie demonstrating some of the direct
manipulation techniques |
| Report |
Compressed
MOV |
Compressed
MPEG |
Adobe
PDF |
Compressed
PostScript |
| CS-2000-14 |
| Title |
SMASH: A Next-Generation
API for Programmable Graphics Accelerators |
| Authors |
M. McCool |
| Date |
July 2000 |
| Report |
|
|
Adobe
PDF |
|
| CS-2000-13 |
| Title |
Cross-coloring: improving
the technique by Kolmogorov and Barzdin |
| Authors |
T. Biedl and T. Chan |
| Abstract |
In this paper, we study how to color crosses, i.e., pairs of rows
and columns in a grid, such that any two overlapping crosses have
a different color. We show that this problem can be solved by
computing an edge-coloring in a bipartite graph. Using this result
we reduce significantly the time complexity and the volume bounds
of algorithms for three-dimensional orthogonal graph drawing that
are based on the technique of Kolmogorov and Barzdin. |
| Date |
June 2000 |
| Comments |
The paper has been submitted
to Graph Drawing 2000. |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-12 |
| Title |
Three-Dimensional Orthogonal
Graph Drawing with Optimal Volume |
| Authors |
T.C. Biedl, T. Thiele
and D.R. Wood |
| Abstract |
An orthogonal drawing
of a graph is an embedding of the graph in the rectangular grid, with vertices
represented by axis-aligned boxes, and edges represented by paths in the
grid which only possibly intersect at common endpoints. In this paper, we
study three-dimensional orthogonal drawings and provide lower bounds for
three scenarios: (1) drawings where vertices have bounded aspect ratio,
(2) drawings where the surface of vertices is proportional to their degree,
and (3) drawings without any such restrictions. Then we show that these
lower bounds are asymptotically optimal, by providing constructions that
match the lower bounds in all scenarios within an order of magnitude. |
| Date |
January 2001 |
| Comments |
The paper will appear
at Graph Drawing 2000, and has been submitted to Discrete and Computational
Geometry. |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-11 |
| Title |
Exploiting Functional
Dependence in Query Optimization |
| Authors |
G.N. Paulley |
| Abstract |
Functional dependency
analysis can be applied to various problems in query optimization: selectivity
estimation, estimation of (intermediate) result sizes, order optimization
(in particular sort avoidance), cost estimation, and various problems in
the area of semantic query optimization. Dependency analysis in an ANSI
SQL relational model, however, is made complex due to the existence of null
values, three-valued logic, outer joins, and duplicate rows. In this thesis
we define the notions of strict and lax functional dependencies, strict
and lax equivalence constraints, and null constraints, which capture both
a large set of the constraints implied by ANSI SQL query expressions, including
outer joins, and a useful set of declarative constraints for ANSI SQL base
tables, including unique, table, and referential integrity constraints.
We develop and prove a sound set of inference axioms for this set of combined
constraints, and formalize the set of constraints that hold in the result
of each SQL algebraic operator. We define an extended functional dependency
graph model (FD-graph) to represent these constraints, and present and prove
correct a detailed polynomial-time algorithm to maintain this FD-graph for
each algebraic operator. We illustrate the utility of this analysis with
examples and additional theoretical results from two problem domains in
query optimization: query rewrite optimizations that exploit uniqueness
properties, and order optimization that exploits both functional dependencies
and attribute equivalence. We show that the theory behind these two applications
of dependency analysis is not only useful in relational database systems,
but in non-relational database environments as well. |
| Date |
May 2000 |
| Comments |
This PhD thesis defines
the notions of strict and lax functional dependencies, strict and lax equivalence
constraints, and null constraints in an ANSI SQL context, The thesis develops
and proves a sound set of inference axioms for this set of combined constraints,
and formalizes the set of constraints that hold in the result of each SQL
algebraic operator. Two applications of these derived constraints are explored:
query rewrite optimization and order optimization. |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-10 |
| Title |
Implementation of Some
Triangular Data Fitting Schemes Using Averaging To Get Continuity |
| Authors |
S. Mann |
| Abstract |
In this paper, I describe
the implementation details of some functional, triangular data fitting schemes.
The schemes in question use derivative information to find initial settings
of control points, giving a $C^0$, piecewise polynomial surface with a high
degree of polynomial precision. The interior control points are then modified
to increase the continuity between patches without decreasing the polynomial
precision. In implementing these schemes, I had to address several issues,
including basis conversion for bivariate functions, finding the weights
of control points used to compute derivatives, and the construction of data
sets for testing. In addition, I developed and tested a new scheme that
uses fewer derivatives than the other schemes discussed in this paper. |
| Date |
April 2000 |
| Comments |
|
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-09 |
| Title |
Online Scheduling Revisited |
| Authors |
R. Fleischer and M. Wahn |
| Abstract |
We present a new online
algorithm MR for non-preemptive scheduling of jobs with known processing
times on m identical machines which beats the best previous algorithm for
m>=64. For m approaching infinity its competitive ratio approaches 1+\sqrt{1+\ln
2\over 2}<1.9201. |
| Date |
March 2000 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-08 |
| Title |
Balanced k-Colorings |
| Authors |
T.C. Biedl, E. Cenek,
T.M. Chan, E.D. Demaine, M.L.Demaine, R. Fleischer and M.-W. Wang |
| Abstract |
While discrepancy theory
is normally only studied in the context of 2-colorings, we explore the problem
of k-coloring, for k>=2, a set of vertices to minimize imbalance among a
family of subsets of vertices. The imbalance is the maximum, over all subsets
in the family, of the largest difference between the size of any two color
classes in that subset. The discrepancy is the minimum possible imbalance.
We show that the discrepancy is always at most 4d-3, where d (the ``dimension'')
is the maximum number of subsets containing a common vertex. For 2-colorings,
the bound on the discrepancy is at most max{2d-3,2}. Finally, we prove that
several restricted versions of computing the discrepancy are NP-complete.
|
| Date |
March 2000 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-07 |
| Title |
Simplifying flow networks |
| Authors |
Therese Biedl, Brona Brejova,
Tomas Vinar |
| Abstract |
Maximum flow problems
appear in many practical applications. In this paper, we study how to simplify
a given directed flow network by finding edges that can be removed without
changing the value of the maximum flow. We give a number of approaches which
are increasingly more complex and more time-consuming, but in exchange they
remove more and more edges from the network. |
| Date |
February 2000 |
| Comments |
Will be submitted to MFSC
2000 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-06 |
| Title |
How to Roll a Join: Asynchronous
Incremental View Maintenance |
| Authors |
K.M. Salem, K. Beyer,
B. Lindsay and R. Cochrane |
| Date |
Feb.28/00 |
| Report |
Report not in system |
| CS-2000-05 |
| Title |
Efficient Query Result
Retrieval over the Web |
| Authors |
E.P.F. Chan and K. Ueda |
| Date |
February 2000 |
| Report |
Edward P.F. Chan's website |
| CS-2000-04 |
| Title |
Polygons needing many
flipturns |
| Authors |
T.C. Biedl |
| Abstract |
A flipturn on a polygon
consists of reversing the order of segments inside a pocket of the polygon,
without changing lengths or slopes. Any n-link polygon can be convexified
by performing at most (n-1)! flipturns. A very recent paper showed that
in fact it is convex after at most n(n-1)/2 flipturns. We give here a lower
bound by constructing a polygon such that if pockets are chosen in a bad
way, at least (n-2)^2/4 flipturns are needed to convexify the polygon. |
| Date |
January 2000 |
| Comments |
This paper will probably
be submitted to CCCG 2000. |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-03 |
| Title |
On the q-analogue of Zeilberger's
algorithm to rational functions |
| Authors |
H.Q. Le |
| Abstract |
We consider the applicability
(or terminating condition) of the q-analogue of Zeilberger's algorithm and
give the complete solution to this problem for the case where the original
q-hypergeometric term F(q^n,q^k) is a rational function.
|
| Date |
January 2000 (Revised,
September 17, 2001) |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-2000-02 |
| Authors |
E. Demaine |
| Date |
Number issued, Jan.18/00 |
| Report |
Report not in system |
| CS-2000-01 |
| Title |
Continuity Adjustments
to Triangular Bezier Patches That Retain Polynomial Precision |
| Authors |
S. Mann |
| Abstract |
In this paper, I discuss
a method for increasing the continuity between two polynomial patches by
adjusting their control points. The method described in this paper leaves
the control points unchanged if the patches already meet with the desired
level of continuity. Next I give two $C^0$ degree $n$ polynomial interpolation
schemes that reproduce degree $n$ polynomials, and show how to apply my
continuity increasing scheme to these interpolants without decreasing their
polynomial precision. The second of these interpolants is interesting in
its own right, as it requires less data than other methods. Finally, I apply
my continuity method to Clough-Tocher methods, and create split domain schemes
with top-level polynomial precision.
|
| Date |
January 2000 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |