🚀 go-pugleaf

		Department of Computer Science
		   James Cook University
		     Technical Reports

  Single copies of Technical Reports are available free of charge by writing
to farrell@coral.cs.jcu.edu.au, or

Department of Computer Science
James Cook University
Townsville 4811
AUSTRALIA

  Multiple copies are available by arrangement.


Technical Report 91/1

AUTHOR: D.R. Sweet

TITLE:  The Use of Linear-time Systolic Algorithms  for  the
solution of
 Toeplitz Problems.

ABSTRACT:

Algorithms  have  been  devised  which  solve,  invert   and
factorize  order-n  Toeplitz  systems  on  O(n)   -  element
systolic linear arrays in O(n) time.  A  systolic  algorithm
for  O(n)  time,  a recent pivoting technique which improves
the numerical performance of Bareiss's Toeplitz solver.   As
a  by-product,  permuted factors of the matrix are produced.
An  extension  of  the  systolic  pivoted  solver  is   then
presented which yields the Gohberg-Semencul decomposition of
the inverse of the Toeplitz matrix, which  can  be  used  to
solve the system efficiently for several right-hand-sides.


Technical Report 91/2

AUTHOR: Siva Misra and Manjari Asawa

TITLE:  ROBINHOOD: Resource Sharing By Time Stealing Between
DOS PCs On A
 LAN

ABSTRACT:

Current data processing centers are proliferated  with  PCs,
located in various zones, and the number of such machines is
growing day by day.   Further,  because  of  advancement  in
communication  technology,  in  many  centers  these PCs are
interconnected by a Local Area Network (LAN).  Often many of
these  PCs  remain  unused,  while  their owners are busy in
doing something else.  Commercial  PC-LAN  architectures  do
not  allow  the full computation power of machines connected
to a local network to be exploited.   They  only  allow  the
sharing  of  permanent  LAN  server  resources,  but not the
processing capabilities of  users'   PCs.   The  distributed
computing   concept  principally  involves  the  sharing  of
processor resources among all users.  We  have  developed  a
distributed  computing  environment  that allows UNIX - like
foreground/background processing on DOS PCs connected to  an
Ethernet local area network.


Technical Report 91/3

AUTHOR: Y. Jiang, J. Cao and G.K. Gupta

TITLE:  Query  Plan  Correction  in   Distributed   Database
Systems

ABSTRACT:

Most existing query optimization algorithms for  distributed
database  systems  formulate  query  execution  plans  using
estimates  of  dynamic  parameters,   such   as   sizes   of
intermediate  results  of  queries.   The  accuracy  of such
estimates can often have a strong impact on the  performance
of the formulated plan.  In this paper, a general method for
dynamically correcting query execution plans that have  been
formulated based on inaccurate estimates is presented.  Some
new  plan  correction  methods  are  also   proposed.    The
performances  of  existing  and  new  query  plan correction
methods  are  then  compared.   The  results  indicate  that
existing  plan correction methods work well when only one or
a small number of estimates used in the formulation  of  the
plan are incorrect, while the methods proposed in this paper
do not exhibit this limitation.


Technical Report 91/4

AUTHOR: Y. Jiang, J. Cao and G.K. Gupta

TITLE:  Dynamic Distributed Query Processing  Through  Query
Migration

ABSTRACT:

Previous work on distributed query  processing  has  focused
either  on  static  formulation  of  optimal query execution
plans or on pre-execution placement of queries in an attempt
to  evenly  distribute the queries among the processors.  In
this paper  we  describe  a  query  migration  approach  and
evaluate  its performance.  The simulation results show that
significant improvement in performance, namely  the  average
response  time,  may  be  obtained  by  using migration as a
dynamic query processing technique.  We also show that query
processing  semantics  can  be  explored  to  develop useful
heuristics for reducing migration overhead and  for  further
improving query processing performance.


Technical Report 91/5

AUTHOR: J. Cao

TITLE:  An Abstract Model of Rollback  Recovery  Control  in
Distributed Systems

ABSTRACT:

This paper develops  an  abstract  model  which  presents  a
method of uniform description of different rollback recovery
control  algorithms  for  distributed  systems.   We   first
developed  a  general definition of the distributed rollback
recovery control problem.   The  concept  of  a  distributed
recovery   control   system   (DRC  system),  consisting  of
distributed recovery control units (DRC units), is  proposed
to model recovery with various control granularities.  Then,
we developed a graph model,  called  dependency  graph,  for
distributed  rollback recovery control algorithms. An Atomic
subgraph is defined as a subgraph induced by a set of  nodes
which  has  no  outgoing  arcs  to other nodes in the graph.
Committing and aborting atomic actions  can  be  modeled  as
identifying atomic subgraphs.  Next, we defined two kinds of
dependency graphs: checkpoint graphs and unit graphs,  based
on  the dependency relation defined by rollback propagation.
We have shown that various  types  of  distributed  recovery
control   algorithms   can   be   classified  based  on  the
identifications of atomic subgraphs  in  these  two  graphs.
Therefore, using the model may allow us to describe existing
algorithms in a uniform way and, more importantly,  to  find
new algorithms.


Technical Report 91/6

AUTHOR: J. Cao and K.C. Wang

TITLE:  Efficient Synchronous Checkpointing  in  Distributed
Systems

ABSTRACT:

In this paper we study the problem of  efficiently  carrying
out  synchronous  checkpointing  in  a  distributed  system.
Synchronous checkpointing algorithms  coordinate  a  set  of
processes  to  take  checkpoints  in  a  way that the set of
checkpoints taken always forms part of a  consistent  global
system  state.   First, we derive worst-case lower bounds on
time and messages for distributed synchronous  checkpointing
algorithms,  assuming that control messages of the same kind
are of equal size independent of the number of processes  in
the system.  Existing synchronous algorithms can be improved
to  achieve  the  worst-case  lower  bounds.   However,  the
improved  algorithm  still exhibits many redundant messages.
By allowing control messages of different sizes, we  present
a  distributed algorithm for synchronous checkpointing which
has a better worst-case complexity and  eliminates  as  many
redundant message as possible in other cases.


Technical Report 91/7

AUTHOR: J. Bell and G.K. Gupta

TITLE:  An Evaluation of Self-Adjusting Binary  Search  Tree
Techniques

ABSTRACT:

Much  has  been  said  in  praise  of  self-adjusting   data
structures, particularly self-adjusting binary search trees.
Self-adjusting trees are most suited to  skewed  key  access
distributions  as  the  techniques attempt to place the most
commonly  accessed  keys  near  the  root   of   the   tree.
Theoretical  bounds  on worst case and amortised performance
(that is, performance over a sequence  of  operations)  have
been  derived  which  compare  well  with  those for optimal
binary  search  trees.   In  this  paper,  we  compare   the
performance of three different techniques for self-adjusting
trees with that of  AVL  and  random  binary  search  trees.
Comparisons  are  made for various tree sizes, levels of key
access frequency  skewness  and  ratios  of  insertions  and
deletions  to  searches.   The results show that, because of
the high cost of maintaining self-adjusting trees, in almost
all  cases  the  AVL tree outperforms all the self-adjusting
trees and in many cases even a random binary search tree has
better  performance,  in  terms of CPU time, than any of the
self-adjusting trees.


Technical Report 91/8

AUTHOR: A.S.M. Sajeev and A.J. Hurst

TITLE:  Programming Persistence In x

ABSTRACT:

Persistence is the concept of preserving  information  in  a
reusable  state  inside  the  computer  system.   Files  and
library subroutines in common computer  systems  embody  the
idea  of  persistence.   What  is unusual about a Persistent
Programming Environment is that persistence is not  confined
to  a  very limited type of objects like files.  Any type of
object which has a temporary existence can have a  permanent
existence   and  vice  versa  in  a  Persistent  Programming
Environment.

This  report  illustrates   the   concept   of   programming
"persistence" through simple examples.  The language used is
x,  a   persistent   programming   language   developed   in
conjunction   with   a   capability   based   multiprocessor
architecture.  In x's object space, the  life  span  of  any
object  is  orthogonal  to  its type.  All objects are first
class.  This enables the creation, preservation and reuse of
all  types of objects - data objects of arbitrary structures
as well as control objects like procedures and  processes  -
in a uniform manner.

The  report  also  discusses  the  principles  involved   in
designing   a   persistent   programming  language  and  the
evolution of persistent programming languages.


Technical Report 91/9

AUTHOR: J. Bell and G.K. Gupta

TITLE:  Implementing Linear Hashing in Main Memory

ABSTRACT:

The dramatic fall in the unit price of main memory has meant
that  main  memory  sizes of 1 gigabyte or more are becoming
economically viable.  It is therefore  feasible  to  have  a
large  database  which  is  entirely  main  memory resident.
Efficient techniques for storing a database in  main  memory
are  likely  to  be  different  to  those used for storing a
database on secondary  storage.   This  paper  examines  the
implementation  and  performance  of  linear hashing in main
memory databases.  We consider the organisation of the table
and  the  keys at each address and the effect of primary and
overflow bucket size on performance.  We  also  introduce  a
new  split  policy particularly suited to use in main memory
which provides  improved  performance  over  existing  split
policies.


Technical Report 92/1

AUTHOR: S. Aeberhard, D. Coomans and O. de Vel

TITLE:  Extensions to Regularised Discriminant Analysis

ABSTRACT:

Regularised Discriminant Analysis has proven to  be  a  most
effective   classifier   for   problems   where  traditional
classifiers fail because of a lack  of  sufficient  training
samples,  as is often the case in high dimensional settings.
However,  it  has  been  shown  that  the  model   selection
procedure  of Regularised Discriminant Analysis, determining
the  degree  of  regularisation,   has   some   deficiencies
associated  with  it.  We propose a modified model selection
procedure based on a new appreciation function.  By means of
an  extensive  simulation  it  was  shown that the new model
selection procedure performs better than the  original  one.
We  also  propose  that  one  of  the  control parameters of
Regularised Discriminant Analysis  be  allowed  to  take  on
negative  values.   This  extension  leads  to  an  improved
performance  in  certain  situations.    The   results   are
confirmed using two chemical data sets.


Technical Report 92/2

AUTHOR: D.A. Spuler and G.K. Gupta

TITLE:  An Empirical Study of Nearly Optimal  Binary  Search
Trees and Split Trees

ABSTRACT:

Given a set of keys and relative frequencies  of  successful
and  unsuccessful  searches,  it  is  possible  to  build an
optimal binary search tree using  an  algorithm  that  costs
O(n2)  time  and  space.   This  algorithm  is not efficient
enough in many circumstances  and  then  one  must  look  at
building  a  nearly  optimal  tree more cheaply.  This paper
uses an empirical study to evaluate a number  of  algorithms
that  have  been proposed for building nearly optimal binary
search trees.  The split tree, introduced by  Sheil  (1978),
is  discussed and a number of algorithms for building nearly
optimal split trees are  also  evaluated.   In  addition,  a
simple variant of the split tree is presented (which we call
a "modified split tree") and  a  number  of  algorithms  for
constructing   nearly   optimal  modified  split  trees  are
included in the empirical study.  The  modified  split  tree
does not require any keys to be stored twice (as is the case
with split trees) and has limited space wastage.  A model of
search  cost  of  binary  search  and  split  trees  is also
discussed.


Technical Report 92/3

AUTHOR: D.A. Spuler

TITLE:  The Best Algorithm for  Searching  a  Binary  Search
Tree

ABSTRACT:

A binary search tree is a very commonly used data structure,
and  yet  the  most  commonly  used  search algorithm is not
necessarily the most efficient.  It is best in terms  of  3-
way  comparisons,  but  in most high level languages a 3-way
comparison costs as much as two 2-way comparisons.   A  fast
tree  search  algorithm  using  2-way  comparisons which was
devised  by  Andersson  is  examined  and   improved   using
transfer-driven loop unrolling.  The performance of a number
of search algorithms for binary  search  trees  is  examined
theoretically  based on various models of the relative costs
of 2-way and 3-way comparisons.


Technical Report 92/4

AUTHOR: D.A. Spuler

TITLE:  The Optimal  Binary  Search  Tree  for  Anderssons's
Search Algorithm

ABSTRACT:

Andersson [1991] has presented a search algorithm for binary
search  trees  that  uses  only  two-way  key comparisons by
deferring equality comparisons until the leaves are reached.
The  use  of  a  different  search  algorithm means that the
optimal tree for the traditional search algorithm, which has
been shown to be computable in O(n2) time by Knuth [1971] is
not optimal in terms  of  the  different  search  algorithm.
This  paper  shows  that  the optimal binary search tree for
Andersson's search algorithm can be simply computed  in  O(n
log  n)  time using existing algorithms for the special case
of zero successful access frequencies, such as the Hu-Tucker
algorithm.


Technical Report 92/5

AUTHOR: D.A. Spuler

TITLE:  Two-Way Comparison Search Trees A Generalization  of
Binary Search Trees and Split Trees

ABSTRACT:

A generalization of binary search  trees  and  binary  split
trees  is  developed  that  takes  advantage  of two-way key
comparisons - the  two-way  comparison  tree.   The  two-way
comparison  tree  is  shown  to  have little use for dynamic
situations, but to be an improvement over the optimal binary
search  tree  and  the  optimal binary split tree for static
data sets.  An O9n0 time and space  algorithm  is  presented
for construction of the optimal two-way comparison tree when
access probabilities are equal;   the  construction  of  the
optimal  tree  for more general probabilities is shown to be
more difficult and unlikely to cost less then O(n4).
===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu