Technical Reports

The ICICS/CS Reading Room

2000 UBC CS Technical Report Abstracts

TR-2000-01 Stochastic Local Search Methods for Dynamic SAT - an Initial Investigation, February 01, 2000 Holger H. Hoos and Kevin O'Neill, 13 pages

We introduce the dynamic SAT problem, a generalisation of the satisfiability problem in propositional logic which allows changes of a problem over time. DynSAT can be seen as a particular form of a dynamic CSP, but considering results and recent success in solving conventional SAT problems, we believe that the conceptual simplicity of SAT will allow us to more easily devise and investigate high-performing algorithms for DynSAT than for dynamic CSPs. In this article, we motivate the DynSAT problem, discuss various formalisations of it, and investigate stochastic local search (SLS) algorithms for solving it. In particular, we apply SLS algorithms which perform well on conventional SAT problems to dynamic problems and we analyse and characterise their performance empirically; this initial investigation indicates that the performance differences between various algorithms of the well-known WalkSAT family of SAT algorithms generally carry over when applied to DynSAT. We also study different generic approaches of solving DynSAT problems using SLS algorithms and investigate their performance differences when applied to different types of DynSAT problems.

TR-2000-02 R-Simp to PR-Simp: Parallelizing A Model Simplification Algorithm, February 07, 2000 Dmitry Brodsky, 8 pages

As modelling and visualization applications proliferate, there arises a need to simplify large polygonal models at interactive rates. Unfortunately existing polygon mesh simplification algorithms are not well suited for this task because they are either too slow (requiring pre-computation) or produce models that are too poor in quality. Given a multi-processor environment a common approach for obtaining the required performance is to parallelize the algorithm. Many non-trivial issues need to be taken into account when parallelizing a sequential algorithm. We present PR-Simp a parallel model simplification algorithm and the issues involved in parallelizing R-Simp.

TR-2000-04 Enumeration of Equicolourable Trees, February 22, 2000 Nicholas Pippenger, 30 pages

A tree, being a connected acyclic graph, can be bicoloured in two ways, which differ from each other by exchange of the colours. We shall say that a tree is equicolourable if these bicolourings assign the two colours to equal numbers of vertices. Labelled equicoloured trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolourable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolourable is asymptotically just twice the probability that its vertices would be equicoloured if they were assigned colours by independent unbiased coin flips. Our goal in this paper is the enumeration of unlabelled equicolourable trees (that is, trees up to isomorphism), both exactly (in terms of generating functions) and asymptotically. We treat both the rooted and unrooted versions of this problem, and conclude that in either case the probability that a randomly chosen n-vertex unlabelled tree is equicolourable is asymptotically 1.40499... times as large as the probability that it would be equicoloured if its vertices were assigned colours by independent unbiased coin flips.

TR-2000-05 Optimal and Approximate Stochastic Planning using Decision Diagrams, June 10, 2000 Jesse Hoey, Robert St.Aubin, Alan Hu and Craig Boutilier, 35 pages

Structured methods for solving factored Markov decision processes (MDPs) with large state spaces have been proposed recently to allow dynamic programming to be applied without the need for complete state enumeration. We present algebraic decision diagrams (ADDs) as efficient data structures for solving very large MDPs. We describe a new value iteration algorithm for exact dynamic programming, using an ADD input representation of the MDP. We extend this algorithm with an approximate version for generating near-optimal value functions and policies with much lower time and space requirements than the exact version. We demonstrate our methods on a class of large MDPs (up to 34 billion states). We show that significant gains can be had with our optimal value iteration algorithm when compared to tree-structured representations (with up to a thirty-fold reduction in the number of nodes required to represent optimal value functions). We then demonstrate our approximate algorithm and compare results with the optimal ones. Finally, we examine various variable reordering techniques and demonstrate their use within the context of our methods.

TR-2000-06 Using Idle Workstations to Implement Predictive Prefetching, June 12, 2000 Jasmine Y.Q. Wang, Joon Suan Ong, Yvonne Coady and Michael J. Feeley, 8 pages

The benefits of Markov-based predictive prefetching have been largely overshadowed by the overhead required to produce high quality predictions. While both theoretical and simulation results for prediction algorithms appear promising, substantial limitations exist in practice. This outcome can be partially attributed to the fact that practical implementations ultimately make compromises in order to reduce overhead. These compromises limit the level of algorithm complexity, the variety of access patterns, and the granularity of trace data the implementation supports. This paper describes the design and implementation of GMS-3P, an operating-system kernel extension that offloads prediction overhead to idle network nodes. GMS-3P builds on the GMS global memory system, which pages to and from remote workstation memory. In GMS-3P, the target node sends an on-line trace of an application's page faults to an idle node that is running a Markov-based prediction algorithm. The prediction node then uses GMS to prefetch pages to the target node from the memory of other workstations in the network. Our preliminary results show that predictive prefetching can reduce remote-memory page fault time by 60% or more and that by offloading prediction overhead to an idle node, GMS-3P can reduce this improved latency by between 24% and 44%, depending on Markov-model order.

TR-2000-07 Eliminating Cycles in Composed Class Hierarchies, July 8, 2000 Robert J. Walker, 13 pages

Multiple class hierarchies can be used each to represent a separate requirement or design concern. To yield a working system, these disparate hierarchies must be composed in a semantically meaningful way. However, cycles can arise in the composed inheritance graph that restrict the space of composable hierarchies. This work presents an approach to eliminating these cycles by means of separating the type hierarchy from the implementation hierarchy; separate solutions are provided for languages permitting multiple inheritance, such as C++, and those permitting only interfaces, such as Java. The resulting acyclic class hierarchy will maintain the significant constraints imposed by the original, separate hierarchies, such as type-safety.

TR-2000-08 Determination of Intensity Thresholds via Shape Gradients, August 01, 2000 Roger Tam and Alain Fournier, 9 pages

medical imaging, segmentation, shape representation, shape measurement, thresholding, Union of Circles objects in an image provide high-level information that is essential for many image processing tasks. Accurate analysis of medical images is often dependent upon an appropriate greyscale thresholding of the image for reliable feature extraction. The determination of object thresholds can be a time-consuming task because the thresholds can vary greatly depending upon the quality and type of image. Thus, an efficient method for determining suitable thresholds is highly desirable. This paper presents a method that uses shape information to accurately determine the intensity ranges of objects present in a greyscale image. The technique introduced is based on the computation of the \emph{shape gradient}, a numerical value for the difference in shape. In this case, the difference in shape is caused by the change in threshold value applied to the image. The use of this gradient allows us to determine significant shape change \emph{events} in the evolution of object forms as the threshold varies. The gradient is computed using \emph{Union of Circles} matching, a method previously shown to be effective in computing shape differences. We show the results of applying this method to artificially computed images and to real medical images. The quality of these results shows that the method is potentially viable in practical applications.

TR-2000-09 Efficient Mapping of Software System Traces to Architectural Views, July 07, 2000 Robert J. Walker, Gail C. Murphy, Jeffrey Steinbok and Martin P. Robillard, 9 pages

Information about a software system's execution can help a developer with many tasks, including software testing, performance tuning, and program understanding. In almost all cases, this dynamic information is reported in terms of source-level constructs, such as procedures and methods. For some software engineering tasks, source-level information is not optimal because there is a wide gap between the information presented (i.e., procedures) and the concepts of interest to the software developer (i.e., subsystems). One way to close this gap is to allow developers to investigate the execution information in terms of a higher-level, typically architectural, view. In this paper, we present a straightforward encoding technique for dynamic trace information that makes it tractable and efficient to manipulate a trace from a variety of different architecture-level viewpoints. We also describe how this encoding technique has been used to support the development of two tools: a visualization tool and a path query tool. We present this technique to enable the development of additional tools that manipulate dynamic information at a higher-level than source.

TR-2000-10 The Rectilinear Crossing Number of K_10 is 62, August 10, 2000 Alex Brodsky, Stephane Durocher and Ellen Gethner, 19 pages

A drawing of a graph G in the plane is said to be a rectilinear drawing of G if the edges are required to be line segments (as opposed to Jordan curves). We assume no three vertices are collinear. The rectilinear crossing number of G is the fewest number of edge crossings attainable over all rectilinear drawings of G. Thanks to Richard Guy, exact values of the rectilinear crossing number of K_n, the complete graph on n vertices, for n = 3,...,9, are known (Guy 1972, White and Beineke 1978). Since 1971, thanks to the work of David Singer, the rectilinear crossing number of K_10 has been known to be either 61 or 62, a deceptively innocent and tantalizing statement. The difficulty of determining the correct value is evidenced by the fact that Singer's result has withstood the test of time. In this paper we use a purely combinatorial argument to show that the rectilinear crossing number of K_10 is 62. Moreover, using this result, we improve an asymptotic lower bound for a related problem. Finally, we close with some new and old open questions that were provoked, in part, by the results of this paper, and by the tangled history of the problem itself.

TR-2000-11 Toward the Rectilinear Crossing Number of K_n: New Drawings, Upper Bounds, and Asymptotics, September 14, 2000 Alex Brodsky, Stephane Durocher and Ellen Gethner, 13 pages

Scheinerman and Wilf (1994) assert that `an important open problem in the study of graph embeddings is to determine the rectilinear crossing number of the complete graph K_n.' A rectilinear drawing of K_n is an arrangement of n vertices in the plane, every pair of which is connected by an edge that is a line segment. We assume that no three vertices are collinear, and that no three edges intersect in a point unless that point is an endpoint of all three. The rectilinear crossing number of K_n is the fewest number of edge crossings attainable over all rectilinear drawings of K_n. For each n we construct a rectilinear drawing of K_n that has the fewest number of edge crossings and the best asymptotics known to date. Moreover, we give some alternative infinite families of drawings of K_n with good asymptotics. Finally, we mention some old and new open problems.

If you have any questions or comments regarding this page please send mail to